MySQL 中的 B+ 树与索引 —— 结构、插入删除与数据页

一、为什么需要 B 树 / B+ 树？

• 数据库数据量很大，无法全部放进内存，查询必然涉及磁盘 I/O。
• 若用有序数组做索引：查找快（二分），但插入/删除要移动大量元素，代价高。
• 若用二叉搜索树（BST）：在内存里可行，但若树高很大，一次查找要多次磁盘访问（每层可能在不同页），且 BST 可能退化成链。
• 多路平衡树（B 树 / B+ 树）在同一结点内存放多个 key，树高低、扇出大，一次磁盘读能比较很多 key，适合做磁盘上的索引。

下面先讲 B 树，再讲 B+ 树（MySQL InnoDB 实际使用的形式），然后结合 数据页、聚簇索引、二级索引 说明在 MySQL 中的落地。

---

二、B 树（B-Tree）结构

2.1 定义与性质

• B 树是一棵多路平衡搜索树，每个结点可包含多个 key 和多个子结点指针。
• 常见约定（以 m 阶 B 树为例）：
  • 根结点：子结点数 ∈ [2, m]，key 数 = 子结点数 − 1。
  • 非根非叶：子结点数 ∈ [⌈m/2⌉, m]，key 数 = 子结点数 − 1。
  • 叶子在同一层（平衡）。
• key 与数据：在经典 B 树中，每个 key 可以携带数据（或数据指针），即 key 既参与路由，也可能出现在内部结点。

下面用上下结构表示一棵 3 阶 B 树的示意（每个非根结点 key 数 ∈ [1, 2]，子结点数 ∈ [2, 3]）：

                    [ 50 ]                    ← 根（1 个 key，2 个子指针）
                   /      \
            [ 20, 35 ]   [ 70, 85 ]          ← 内部结点（key 与数据可共存）
           /   |    \    /   |    \
        [10] [25] [40] [60] [75] [90]       ← 叶子（同一层）

用流程图表示同一棵 B 树的层次关系（自上而下）：

flowchart TB
    subgraph root["根"]
        R[50]
    end
    subgraph inner["内部结点"]
        A[20, 35]
        B[70, 85]
    end
    subgraph leaf["叶子"]
        L1[10]
        L2[25]
        L3[40]
        L4[60]
        L5[75]
        L6[90]
    end
    R --> A
    R --> B
    A --> L1
    A --> L2
    A --> L3
    B --> L4
    B --> L5
    B --> L6

• 查找：从根开始，按 key 比较进入某一子树，直到叶子或命中。
• B 树的 key 可以同时出现在内部结点和叶子，且叶子之间一般不做链表串联。

---

三、B+ 树（B+ Tree）结构

3.1 与 B 树的区别

维度	B 树	B+ 树（InnoDB 使用）
数据存放	可分布在所有结点（key 所在即数据所在）	仅叶子结点存数据（或完整记录/主键），内部结点只存 key + 子指针，用于路由
叶子层	叶子互不链接	叶子层按 key 顺序形成双向链表，便于范围扫描
内部结点	存 key（可能带数据）	只存 key 的副本，用于二分查找下一层；不存完整行数据
查找	可能在内部结点命中并返回	等值命中一定在叶子；范围查询顺叶子链表扫

3.2 上下结构示意（3 阶 B+ 树）

内部结点只做路由；叶子存数据并串成链表：

                    [ 50 ]                    ← 根（仅 key，2 个子指针）
                   /      \
            [ 20, 35 ]   [ 70, 85 ]          ← 内部层（仅 key）
           /   |    \    /   |    \
    ┌─────┬─────┬─────┬─────┬─────┬─────┐
    │10,a │25,b │40,c │60,d │75,e │90,f │    ← 叶子层（key + 数据），双向链表
    └──┬──┴──┬──┴──┬──┴──┬──┴──┬──┴──┬──┘
       └─────┴─────┴─────┴─────┴─────┘

B+ 树层次与叶子链表（自上而下 + 叶子层串联）：

flowchart TB
    subgraph root["根"]
        R[50]
    end
    subgraph inner["内部层"]
        I1[20, 35]
        I2[70, 85]
    end
    subgraph leaf["叶子层-双向链表"]
        direction LR
        L1[10,a]
        L2[25,b]
        L3[40,c]
        L4[60,d]
        L5[75,e]
        L6[90,f]
    end
    R --> I1
    R --> I2
    I1 --> L1
    I1 --> L2
    I1 --> L3
    I2 --> L4
    I2 --> L5
    I2 --> L6
    L1 <--> L2
    L2 <--> L3
    L3 <--> L4
    L4 <--> L5
    L5 <--> L6

• 等值查 40：根 → 左子 [20,35] → 进入 40 所在叶子，在叶子得到数据。
• 范围查 [25, 75]：先落到 25 所在叶子，再沿叶子链表向右扫到 75。

---

四、B 树 / B+ 树的插入：多场景

约定：以 m 阶 为例，结点 key 数上限为 m−1，超过则分裂。

4.1 场景 1：叶子未满，直接插入（B+ 树）

初始（3 阶，key 数 ≤ 2）：

         [ 30 ]
        /      \
   [10,20]   [40,50]

插入 25：落在左叶子 [10,20]，未满，直接插入。

         [ 30 ]
        /      \
   [10,20,25]  [40,50]

4.2 场景 2：叶子已满，分裂（B+ 树）

在 [10,20,25] 中再插入 22，key 数变为 4 > 2，需要分裂。取中间 key（如 22）上推到父结点，左右各成新结点。

步骤 1：插入 22 后叶子为 [10,20,25,22]，排序为 [10,20,22,25]，已满（3 阶最多 2 个 key 则此处假设上限为 3，为叙述方便按 2 个 key 上限则 4 个需分裂）：

         [ 30 ]
        /      \
   [10,20,25,22]  [40,50]     ← 左叶子 4 个 key，超出上限

步骤 2：取中间 key（22 或 25，视实现而定）上推，原叶子分裂为两页：

         [ 22, 30 ]            ← 父结点新增 key 22
        /    |     \
  [10,20] [22,25] [40,50]      ← 左叶分裂为 [10,20] 与 [22,25]

分裂后：

         [ 22, 30 ]
        /    |     \
  [10,20] [22,25] [40,50]

4.3 场景 3：分裂向上传播，根分裂（B+ 树）

若父结点 [22, 30] 也满了（3 阶最多 2 个 key），再插入导致父结点分裂，中间 key 上推并可能产生新根：

例如插入导致 [22,30] 变成 [22,30,35]，分裂为 [22] 与 [35]，30 上推为新根：

              [ 30 ]           ← 新根
             /      \
        [ 22 ]      [ 35 ]
       /     \     /     \
  [10,20] [22,25] [40,50] ...

4.4 场景 4：B 树内部结点满时的分裂

B 树中若内部结点也满了，插入导致分裂时，同样把中间 key 上推到父结点，原结点分裂成两个；若父结点也满则继续上推，直至根分裂并产生新根。

例如 3 阶 B 树，根 [50] 已有两子；左子 [20,35] 满，再插入导致分裂：

分裂前:     [ 50 ]
           /      \
      [20,35]   [70,85]     ← 左子满

分裂后:     [ 35, 50 ]       ← 中间 key 35 上推（或 20，视实现）
          /    |      \
      [20]  [35]  [70,85]

4.5 插入小结

• B 树 / B+ 树：未满则直接插入；满则分裂，中间 key 上推，可能连锁到根并让树高 +1。
• B 树 key 可在任意结点；B+ 树数据只在叶子，内部结点只存 key 副本。

---

五、B 树 / B+ 树的删除：多场景

约定：非根结点 key 数至少为 ⌈m/2⌉ − 1（3 阶则为 1），低于则需借位或合并。

5.1 场景 1：叶子 key 数删除后仍满足下限，直接删（B+ 树）

         [ 22, 30 ]
        /    |     \
  [10,20] [22,25] [40,50]

删除 25：叶子 [22,25] 变为 [22]，key 数 1，仍 ≥ 1，直接删除即可。

5.2 场景 2：向兄弟借 key（B+ 树）

删除 22 后，[22,25] 变成 [25]，若该结点 key 数低于下限，且左兄弟 [10,20] 有多余 key，则父结点下压一个 key，兄弟借出一个。

步骤 1：删除 22 后，叶子 [25] 只有 1 个 key（3 阶下限为 1，若下限为 ⌈m/2⌉−1=1 则刚好达标；若实现要求至少 2 个则不足）：

         [ 22, 30 ]
        /    |     \
  [10,20]  [25]   [40,50]    ← 中间叶子 [25] 不足，左兄弟 [10,20] 可借

步骤 2：从左兄弟借一个 key：父中的 22 下压到当前结点，左兄弟的 20 上移到父（或：左兄弟最大 key 20 移到父，父中 22 下移到当前结点），保证有序：

         [ 20, 30 ]
        /    |     \
  [10]  [20,25]  [40,50]     ← 借位后 [20,25] 有 2 个 key，满足下限

（具体实现中可以是：父结点某个 key 下移到被删结点，兄弟一个 key 上移到父，保证顺序与数量。）

5.3 场景 3：与兄弟合并（B+ 树）

若兄弟也刚好只有最少 key，无法借，则与兄弟合并，并删除父结点中对应分隔 key，可能导致父结点 key 数不足，继续向上合并或借位：

合并前:
         [ 30 ]
        /      \
  [10]  [25]  [40,50]        ← 左、中叶子都只有 1 个 key

合并 [10] 与 [25]，并去掉父中的 30（或下压到合并结点）:
         [ 30 ]
        /      \
  [10,25]    [40,50]

若根只剩一个 key 且两子合并，则根被新合并结点替代，树高减 1。

5.4 内部结点 key 的删除（B 树 / B+ 树）

• 若被删 key 在内部结点：用其前驱或后继（在叶子中）替换该 key，再在叶子中删除前驱/后继，转化为叶子删除问题。
• B+ 树中内部结点只存 key 副本，实际删除的仍是叶子中的唯一副本。

5.5 删除小结

场景	做法
删除后结点 key 数仍 ≥ 下限	直接删
删除后不足，兄弟 key 数 > 下限	向兄弟借一个 key（父下压/兄弟上移）
删除后不足，兄弟也刚好下限	与兄弟合并，父中对应 key 删除，可能向上继续合并
被删 key 在内部结点	用叶子中的前驱/后继替换，再删叶子中的 key

---

六、MySQL 数据页（Data Page）

InnoDB 以页为磁盘 I/O 单位，默认 16KB。B+ 树的一个结点通常对应一页：即一个内部结点或一个叶子结点占用一页（或一页内可放多个小结点，取决于 key 与指针长度）；这样一次磁盘 I/O 读入一整页，就能在内存中完成该结点内的 key 比较并决定进入哪个子页，从而控制树高和 I/O 次数。

6.1 页的类型（概览）

类型	说明
数据页（Index 页 / 叶子页）	存 B+ 树叶子层：主键 + 完整行记录（聚簇索引）或二级索引 key + 主键
索引页（非叶子）	存 B+ 树内部层：key + 子页号（或页内偏移）
Undo 页、系统页等	事务、系统元数据用

6.2 数据页结构（简化）

一个 16KB 的数据页 大致由以下部分组成（自上而下）：

+------------------+
| File Header      |  文件头：页号、前后页指针、校验和等
+------------------+
| Page Header      |  页头：本页记录数、首条/末条偏移、槽数等
+------------------+
| Infimum + Supremum| 虚拟最小/最大记录（链表头尾）
+------------------+
| User Records     | 实际行记录（紧凑排列）
+------------------+
| Free Space       | 未使用空间
+------------------+
| Page Directory   | 槽（Slot）：对记录做近似二分查找
+------------------+
| File Trailer     | 文件尾：校验和
+------------------+

• User Records：在聚簇索引叶子页中存的是完整行（主键 + 所有列）；在二级索引叶子页中存的是索引列 + 主键。
• Page Directory：把页内记录按槽分组，通过槽快速定位某条记录，减少顺序扫描。
• Infimum / Supremum：所有记录都在 [Infimum, Supremum] 之间，便于链表遍历与边界判断。

数据页结构示意（自上而下，约 16KB）：

flowchart TB
    subgraph page["数据页 16KB"]
        direction TB
        P1[File Header]
        P2[Page Header]
        P3[Infimum + Supremum]
        P4[User Records]
        P5[Free Space]
        P6[Page Directory]
        P7[File Trailer]
    end
    P1 --> P2 --> P3 --> P4 --> P5 --> P6 --> P7

6.3 行记录格式（InnoDB）

• Compact / Dynamic：变长列（如 VARCHAR）只存实际长度，NULL 用位图标识，减少空间。
• 行溢出：单行超过约 8KB 时，多余部分放到溢出页，本行只保留前缀 + 溢出页指针。

数据页是 B+ 树叶子和内部结点在磁盘上的载体，理解页有助于理解“一次 I/O 读多少 key/行”。

---

七、MySQL 索引：B+ 树主键索引（聚簇索引）

7.1 聚簇索引即“表数据所在的 B+ 树”

• InnoDB 中，主键 唯一确定一棵 B+ 树，这棵树的叶子结点里放完整行数据（即“数据即索引、索引即数据”），这就是聚簇索引（Clustered Index）。
• 若建表时指定了主键，则用主键建这棵 B+ 树；若未指定，InnoDB 会生成隐藏的 row_id 作为主键建聚簇索引。

7.2 上下结构示意（主键 B+ 树）

假设表 T(id PK, a, b)，id 为 1,2,3,4,5…，每页最多放 2 条行记录（仅为示意）：

                    [ 3 ]                     ← 根（仅 id，路由用）
                   /     \
              [ 1, 2 ]   [ 4, 5 ]            ← 内部层（仅主键）
             /   |   \   /   |   \
    ┌────────┬────────┬────────┬────────┐
    │ id=1   │ id=2   │ id=3   │ id=4,5 │    ← 叶子：主键 + 完整行 (id,a,b)
    │ a,b    │ a,b    │ a,b    │ ...    │
    └───┬────┴───┬────┴───┬────┴───┬────┘
        └────────┴────────┴────────┘
                 叶子双向链表

• 按主键等值查：从根按 id 比较进入子树，最终在叶子找到唯一一行。
• 按主键范围查：在叶子找到起始 id 所在页，沿叶子链表向右扫即可，顺序 I/O 友好。

聚簇索引与表数据的关系（一棵树、叶子即行数据）：

flowchart TB
    subgraph cluster["聚簇索引 B+ 树"]
        direction TB
        R[根: 主键]
        I[内部: 主键]
        L[叶子: 主键 + 完整行]
    end
    R --> I --> L
    L --> data[(表数据 = 叶子中的行)]

7.3 聚簇索引的特点

• 叶子 = 数据页，存完整行，因此按主键查不会回表。
• 一张表只有一棵聚簇索引（因为行数据只有一份物理顺序）。
• 主键顺序与磁盘上行的大致顺序一致，范围查询、主键自增插入都较友好。

---

八、MySQL 索引：二级索引（Secondary Index）

8.1 二级索引是另一棵 B+ 树

• 每个二级索引对应一棵独立的 B+ 树。
• 这棵树的 key 是索引列（可多列），叶子中不存完整行，只存 索引列 + 主键；若查询需要其它列，必须再拿主键去聚簇索引查一次，即回表。

8.2 上下结构示意（二级索引 B+ 树）

表 T(id PK, a, b)，在列 a 上建索引 idx_a：

二级索引树（按 a 排序）:
                    [ a=mid ]
                   /         \
           [ a=小 ]           [ a=大 ]
          /   |    \         /   |    \
    ┌────────┬────────┬────────┬────────┐
    │ a,id   │ a,id   │ a,id   │ a,id   │    ← 叶子：只存 (a, id)
    └───┬────┴───┬────┴───┬────┴───┬────┘
        └────────┴────────┴────────┘

• 查 WHERE a = 100：在 idx_a 的 B+ 树里找到 a=100 的叶子，得到 (a=100, id=?)
• 若 SELECT 的列不止 a 和 id，则需要用得到的 id 到聚簇索引再查一次，取完整行。

二级索引与回表（先走二级索引 B+ 树，再按主键走聚簇索引）：

flowchart LR
    subgraph idx["二级索引 B+ 树"]
        A[按索引列 a 查找]
        B[叶子: a + 主键 id]
    end
    subgraph cluster["聚簇索引 B+ 树"]
        C[按主键 id 查找]
        D[叶子: 完整行]
    end
    A --> B
    B -->|回表| C
    C --> D

8.3 覆盖索引与回表

• 覆盖索引：要输出的列全部在二级索引的 key 或叶子中（例如只查 a 和 id），则不需要回表。
• 回表：需要 b 等未在二级索引中的列时，用叶子里的主键 id 到聚簇索引查完整行，多一次（或多次）B+ 树查找。

8.4 联合索引与最左前缀

• 联合索引 (a, b, c)：B+ 树按 (a, b, c) 字典序排序。
• 查询能用到索引前缀的条件（如 a、a and b、a and b and c）才能高效走索引；只查 b 或 c 无法利用该棵 B+ 树的顺序。

---

九、小结

主题	要点
B 树	多路平衡，key 可带数据，可分布在任意结点
B+ 树	内部结点只做路由，叶子存数据并串成链表，适合范围扫描；InnoDB 使用
插入	未满直接插；满则分裂，中间 key 上推，可能连锁到根
删除	直接删；不足则借位或与兄弟合并，可能树高减 1
数据页	16KB 单位，含页头、User Records、Page Directory 等，叶子/内部结点以页为单位
聚簇索引	主键 B+ 树，叶子 = 完整行，一张表一棵
二级索引	索引列 B+ 树，叶子 = 索引列 + 主键，需回表取完整行（除非覆盖）

理解 B+ 树的结构与插入删除过程，再结合数据页和聚簇/二级索引，就能更清楚 MySQL 如何通过 B+ 树和页组织数据与索引，从而写出更合理的表结构与查询。