B+ 树与页结构源码深挖

2026-11-01

面试问到「MySQL 索引底层」,最高阶的回答是把「B+ 树」和「InnoDB 页结构」两层讲透。本文从磁盘 IO 讲到页分裂,逐层拆解。


一、为什么索引要用树

考察点:从磁盘 IO 理解索引的本质。

数据存在磁盘上,数据库的性能瓶颈是磁盘 IO(一次 IO 约 10ms 级)。索引的目标是用最少的 IO 次数定位数据。

  • 磁盘读取以**页(Page)**为单位,一次 IO 读一页,而不是读一条记录。
  • 如果按顺序全表扫描,10 亿行要 IO 无数次;如果组织成树,查一条记录只需「树高」次 IO。

核心结论:索引选型的本质是降低树高、减少磁盘 IO 次数。

graph LR
    A[磁盘] -->|1次IO读1页| B[内存 Buffer Pool]
    B --> C[定位目标记录]
    style A fill:#e8f4fd

二、为什么是 B+ 树

考察点:与 B 树、二叉树、红黑树、哈希对比。

结构问题
二叉树/红黑树每个节点存一个 key,树高 = log₂N,百万数据树高约 20,IO 次数多
哈希等值 O(1),但不支持范围、排序,且有碰撞
B 树非叶子节点也存数据,单页存不了多少 key,树变高
B+ 树非叶子只存 key,叶子存全部数据且有序链表相连

B+ 树三大优势:

  1. 树矮:非叶子节点只存 key,扇出(fanout)大,树高更低。
  2. 叶子有序链表:支持高效范围查询和排序。
  3. 查询稳定:每次都是树高次 IO,等值/范围都高效。

三、B+ 树的结构

graph TD
    ROOT["根页(内节点)<br/>只存 key + 子页指针"]
    ROOT --> N1["内节点页<br/>key + 指针"]
    ROOT --> N2["内节点页<br/>key + 指针"]
    N1 --> L1["叶子页 ⇄"]
    N1 --> L2["叶子页 ⇄"]
    N2 --> L3["叶子页 ⇄"]
    N2 --> L4["叶子页 ⇄"]
    style ROOT fill:#e8f4fd
    style N1 fill:#fff3cd
    style N2 fill:#fff3cd
    style L1 fill:#e6f7e6
    style L2 fill:#e6f7e6
    style L3 fill:#e6f7e6
    style L4 fill:#e6f7e6
  • 非叶子节点(内节点):只存索引 key 和子节点指针,不存数据。
  • 叶子节点:存全部数据(主键索引存整行,二级索引存主键),并用双向链表串联,支持范围扫描。
  • 阶数(扇出):一个节点最多能有多少个子节点,由「页大小 / key+指针大小」决定。

四、InnoDB 页结构详解

考察点:页是 InnoDB 磁盘管理的最小单位,默认 16KB。

一个 16KB 的页内部结构如下:

graph TD
    FH["File Header (38B)<br/>页号/前后页指针/页类型"]
    PH["Page Header (56B)<br/>槽数/记录数/空闲偏移"]
    IS["Infimum + Supremum<br/>最小/最大虚拟记录"]
    UR["User Records<br/>用户记录(单向链表)"]
    FS["Free Space<br/>空闲空间"]
    PD["Page Directory<br/>页目录(槽数组)"]
    FT["File Trailer (8B)<br/>校验和 + LSN"]
    style UR fill:#e6f7e6
    style PD fill:#fff3cd

各区域作用:

区域作用
File Header页号、页类型、上一页/下一页指针(构成叶子链表)
Page Header槽数量、记录数、空闲空间偏移等统计信息
Infimum/Supremum页内最小/最大虚拟记录,界定记录范围
User Records真实数据记录,通过 next_record 按主键顺序串成链表
Free Space尚未使用的空间,插入记录时从这里分配
Page Directory槽(Slot)数组,用于页内二分查找
File Trailer校验和 + LSN,保证页完整性和崩溃恢复

五、记录在页内如何组织

考察点:行格式 Compact + 记录头 + 页目录。

以 Compact 行格式为例,一条记录的存储结构:

graph LR
    A["变长字段长度列表"] --> B["NULL 值列表(位图)"]
    B --> C["记录头(5B)"]
    C --> D["隐藏列<br/>trx_id + roll_pointer"]
    D --> E["业务列数据"]
    style C fill:#fff3cd

**记录头(5 字节)**关键字段:

  • next_record(2 字节):指向下一条记录的相对偏移,串成单向链表。
  • n_owned(4 bit):该记录在页目录中「拥有」几条记录。
  • record_type:0 普通、1 非叶子、2 Infimum、3 Supremum。
  • deleted_flag:删除标记(InnoDB 删除是逻辑删除)。

页目录(Page Directory):把页内记录分组,每组的「最大记录」作为一个槽(Slot),槽按顺序排列。查找时先通过槽二分定位组,再在组内顺序查找。

graph TD
    PD["Page Directory 槽数组"]
    PD -->|槽0| G1["组1 记录"]
    PD -->|槽1| G2["组2 记录"]
    PD -->|槽2| G3["组3 记录"]
    style PD fill:#fff3cd

这就是「页内查找」为什么不是纯顺序:先用页目录二分缩小范围,再顺序扫小组。


六、B+ 树如何用页实现

考察点:B+ 树的节点 = 页,指针 = 页号。

  • 每个 B+ 树节点对应一个页,页的类型区分「根/内节点/叶子」。
  • 内节点页里存的是「key + 子节点页号」。
  • 叶子页通过 File Header 里的 FIL_PAGE_PREV/NEXT 指针串成双向链表。
  • 一棵 B+ 树 = 一组用「页号」互相引用的页。
graph LR
    R["根页(页号1)"] -->|页号指针| I["内节点页(页号2)"]
    R -->|页号指针| I2["内节点页(页号3)"]
    I -->|页号指针| L["叶子页(页号4)"]
    L -.双向链表.-> L2["叶子页(页号5)"]
    style L fill:#e6f7e6
    style L2 fill:#e6f7e6

七、一次查找的完整过程

考察点:SELECT * FROM t WHERE id = 100 到底发生了什么。

sequenceDiagram
    participant B as Buffer Pool
    participant R as 根页
    participant N as 内节点页
    participant L as 叶子页
    B->>R: 1. 加载根页, 页内二分找子页
    R-->>B: 定位到内节点页号
    B->>N: 2. 加载内节点页, 二分找子页
    N-->>B: 定位到叶子页号
    B->>L: 3. 加载叶子页, 页目录二分定位
    L-->>B: 4. 找到记录, 返回
  • 三层 B+ 树查一条记录 = 3 次磁盘 IO(根→内节点→叶子)。
  • 每层进入页后,用 Page Directory 二分查找。

八、页分裂与页合并

考察点:数据插入导致的结构变化,也是「自增主键」问题的根源。

页分裂:叶子页写满后,插入新记录时:

  1. 申请一个新页。
  2. 把原页约一半记录移到新页。
  3. 在父节点插入新页的索引项(key + 页号)。
graph TD
    A["页A(满)<br/>1..100"] -->|分裂| B["页A<br/>1..50"]
    A --> C["页B(新)<br/>51..100"]
    P["父节点新增索引项"] --> B
    P --> C
    style C fill:#fff3cd
  • 页分裂导致数据移动、产生碎片、可能递归分裂父节点,代价高。
  • 页合并:删除导致页太空时,相邻页合并,回收空间。

九、为什么页大小是 16KB

考察点:页大小的权衡。

  • 历史原因:早期机械硬盘/SSD 的扇区和文件系统块大小多为 4KB,16KB 是其整数倍,对齐 IO 效率高。
  • 太小:页多,树变高,IO 次数多。
  • 太大:一次 IO 读入太多无用数据,内存浪费,页分裂代价大。
  • 可调(innodb_page_size),但默认 16KB 是长期实践的最优平衡。

十、一棵 B+ 树能存多少数据

考察点:扇出(fanout)计算,面试常让估算。

以主键索引为例(假设主键 bigint 8 字节,指针 6 字节):

  1. 非叶子节点每条索引项 ≈ 8 + 6 = 14 字节,加上页目录等开销,一页约存 1000 条索引项(扇出 ≈ 1000)。
  2. 假设一行数据 1KB,叶子页(16KB)去掉头部约存 15 行。
  3. 三层 B+ 树:1000 × 1000 × 15 ≈ 1500 万行。
  4. 两层:1000 × 15 = 1.5 万行。

工程经验:三层 B+ 树能支撑约 2000 万行数据,所以「千万级数据查主键」只要 3 次 IO,非常快。


十一、为什么推荐自增主键

考察点:聚集索引 + 顺序插入 + 页分裂 + 二级索引。

  1. 顺序插入,避免页分裂:自增主键永远插入到最右叶子页,页分裂少、无碎片。
  2. 非自增主键(如 UUID)随机插入:频繁触发页分裂、产生碎片、插入变慢。
  3. 二级索引叶子存主键:主键越小(如 int/bigint 而非 UUID),二级索引越小,省空间、查询快。
graph LR
    A["自增主键"] --> B["顺序插入最右页<br/>无页分裂"]
    C["UUID 随机主键"] --> D["随机插入<br/>频繁页分裂+碎片"]
    style B fill:#e6f7e6
    style D fill:#fce4e4

十二、范围查询为什么快

考察点:叶子双向链表的价值。

SELECT * FROM t WHERE id BETWEEN 100 AND 200;
  1. 先走 B+ 树定位到 id=100 的叶子页(3 次 IO)。
  2. 叶子页内通过 next_record 链表顺序读取。
  3. 到页尾通过 FIL_PAGE_NEXT 跳到下一个叶子页,继续读,直到 200。

因为叶子页是双向有序链表,范围查询只需「定位起点 + 顺序扫描」,不用反复回溯树。


十三、面试话术总结

面试官问「讲一下 InnoDB 的索引底层」,按这个层次答:

  1. 为什么 B+ 树:磁盘 IO 是瓶颈,要降低树高;非叶子只存 key 扇出大、树矮;叶子有序链表支持范围查询。

  2. 页结构:InnoDB 以 16KB 页为单位管理磁盘,页 = B+ 树节点。页内包含 File Header(含前后页指针)、Page Header、Infimum/Supremum、User Records、Page Directory、File Trailer。

  3. 页内查找:记录用 next_record 串成单向链表,页目录按「组」建槽,查找时先二分定位组再顺序扫。

  4. 一次查找:根页 → 内节点页 → 叶子页,三层树约 3 次 IO,页内二分。

  5. 页分裂:页满插入触发分裂,父节点加索引项,是性能抖动的主要来源。

  6. 为什么自增主键:顺序插入避免页分裂,且主键小则二级索引小。

  7. 能存多少:三层 B+ 树约 2000 万行,所以千万级主键查询只要 3 次 IO。