3.1.7 B+ Tree

B+ 树是 MySQL InnoDB 存储引擎的核心索引结构，所有用户表的数据和索引都组织在 B+ 树中。它是 B 树的变体，专为磁盘 I/O 和范围查询优化而设计。下面将深度剖析 InnoDB 中 B+ 树的定义、物理实现、操作细节及性能优化。

🌲 一、B+ 树的定义与性质

B+ 树是一种多路平衡搜索树，具有以下关键特征（与 B 树对比）：

性质：

• 一棵 m 阶 B+ 树，内部节点最多有 m-1 个键，最少有 ⌈m/2⌉-1 个键（根节点除外）。
• 所有叶子节点在同一层，保证绝对平衡。
• 叶子节点包含所有键及对应的数据（聚簇索引存整行，二级索引存主键值）。

🏗️ 二、InnoDB 中 B+ 树的实现：索引组织表

InnoDB 使用 索引组织表（Index Organized Table, IOT），即表数据按主键顺序以 B+ 树形式存储。

1. 聚簇索引 (Clustered Index)

• 以主键为索引键构建的 B+ 树。
• 叶子节点直接存储该行的全部列值。
• 逻辑上，表就是一个聚簇索引。
• 若未定义主键，InnoDB 会选择第一个唯一非空索引；若无，则自动生成 6 字节隐藏列 row_id 作为聚簇索引。

2. 二级索引 (Secondary Index)

• 以非主键列（或组合）构建的 B+ 树。
• 叶子节点存储索引键值 + 对应主键值。
• 通过二级索引查询需要回表：先找到主键，再到聚簇索引中查找整行。
• 如果索引覆盖所有查询列，则无需回表，称为覆盖索引。

结构示意图：

#mermaid-svg-HwmiiAU6CJfYfoHE{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-HwmiiAU6CJfYfoHE .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-HwmiiAU6CJfYfoHE .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-HwmiiAU6CJfYfoHE .error-icon{fill:#552222;}#mermaid-svg-HwmiiAU6CJfYfoHE .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-HwmiiAU6CJfYfoHE .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-HwmiiAU6CJfYfoHE .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-HwmiiAU6CJfYfoHE .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-HwmiiAU6CJfYfoHE .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-HwmiiAU6CJfYfoHE .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-HwmiiAU6CJfYfoHE .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-HwmiiAU6CJfYfoHE .marker{fill:#333333;stroke:#333333;}#mermaid-svg-HwmiiAU6CJfYfoHE .marker.cross{stroke:#333333;}#mermaid-svg-HwmiiAU6CJfYfoHE svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-HwmiiAU6CJfYfoHE p{margin:0;}#mermaid-svg-HwmiiAU6CJfYfoHE .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-HwmiiAU6CJfYfoHE .cluster-label text{fill:#333;}#mermaid-svg-HwmiiAU6CJfYfoHE .cluster-label span{color:#333;}#mermaid-svg-HwmiiAU6CJfYfoHE .cluster-label span p{background-color:transparent;}#mermaid-svg-HwmiiAU6CJfYfoHE .label text,#mermaid-svg-HwmiiAU6CJfYfoHE span{fill:#333;color:#333;}#mermaid-svg-HwmiiAU6CJfYfoHE .node rect,#mermaid-svg-HwmiiAU6CJfYfoHE .node circle,#mermaid-svg-HwmiiAU6CJfYfoHE .node ellipse,#mermaid-svg-HwmiiAU6CJfYfoHE .node polygon,#mermaid-svg-HwmiiAU6CJfYfoHE .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-HwmiiAU6CJfYfoHE .rough-node .label text,#mermaid-svg-HwmiiAU6CJfYfoHE .node .label text,#mermaid-svg-HwmiiAU6CJfYfoHE .image-shape .label,#mermaid-svg-HwmiiAU6CJfYfoHE .icon-shape .label{text-anchor:middle;}#mermaid-svg-HwmiiAU6CJfYfoHE .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-HwmiiAU6CJfYfoHE .rough-node .label,#mermaid-svg-HwmiiAU6CJfYfoHE .node .label,#mermaid-svg-HwmiiAU6CJfYfoHE .image-shape .label,#mermaid-svg-HwmiiAU6CJfYfoHE .icon-shape .label{text-align:center;}#mermaid-svg-HwmiiAU6CJfYfoHE .node.clickable{cursor:pointer;}#mermaid-svg-HwmiiAU6CJfYfoHE .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-HwmiiAU6CJfYfoHE .arrowheadPath{fill:#333333;}#mermaid-svg-HwmiiAU6CJfYfoHE .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-HwmiiAU6CJfYfoHE .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-HwmiiAU6CJfYfoHE .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-HwmiiAU6CJfYfoHE .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-HwmiiAU6CJfYfoHE .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-HwmiiAU6CJfYfoHE .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-HwmiiAU6CJfYfoHE .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-HwmiiAU6CJfYfoHE .cluster text{fill:#333;}#mermaid-svg-HwmiiAU6CJfYfoHE .cluster span{color:#333;}#mermaid-svg-HwmiiAU6CJfYfoHE div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-HwmiiAU6CJfYfoHE .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-HwmiiAU6CJfYfoHE rect.text{fill:none;stroke-width:0;}#mermaid-svg-HwmiiAU6CJfYfoHE .icon-shape,#mermaid-svg-HwmiiAU6CJfYfoHE .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-HwmiiAU6CJfYfoHE .icon-shape p,#mermaid-svg-HwmiiAU6CJfYfoHE .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-HwmiiAU6CJfYfoHE .icon-shape .label rect,#mermaid-svg-HwmiiAU6CJfYfoHE .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-HwmiiAU6CJfYfoHE .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-HwmiiAU6CJfYfoHE .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-HwmiiAU6CJfYfoHE :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}