B+ 树与页结构源码深挖
面试问到「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+ 树三大优势:
- 树矮:非叶子节点只存 key,扇出(fanout)大,树高更低。
- 叶子有序链表:支持高效范围查询和排序。
- 查询稳定:每次都是树高次 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 二分查找。
八、页分裂与页合并
考察点:数据插入导致的结构变化,也是「自增主键」问题的根源。
页分裂:叶子页写满后,插入新记录时:
- 申请一个新页。
- 把原页约一半记录移到新页。
- 在父节点插入新页的索引项(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 字节):
- 非叶子节点每条索引项 ≈ 8 + 6 = 14 字节,加上页目录等开销,一页约存 1000 条索引项(扇出 ≈ 1000)。
- 假设一行数据 1KB,叶子页(16KB)去掉头部约存 15 行。
- 三层 B+ 树:
1000 × 1000 × 15 ≈ 1500 万行。 - 两层:
1000 × 15 = 1.5 万行。
工程经验:三层 B+ 树能支撑约 2000 万行数据,所以「千万级数据查主键」只要 3 次 IO,非常快。
十一、为什么推荐自增主键
考察点:聚集索引 + 顺序插入 + 页分裂 + 二级索引。
- 顺序插入,避免页分裂:自增主键永远插入到最右叶子页,页分裂少、无碎片。
- 非自增主键(如 UUID)随机插入:频繁触发页分裂、产生碎片、插入变慢。
- 二级索引叶子存主键:主键越小(如 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;- 先走 B+ 树定位到 id=100 的叶子页(3 次 IO)。
- 叶子页内通过 next_record 链表顺序读取。
- 到页尾通过
FIL_PAGE_NEXT跳到下一个叶子页,继续读,直到 200。
因为叶子页是双向有序链表,范围查询只需「定位起点 + 顺序扫描」,不用反复回溯树。
十三、面试话术总结
面试官问「讲一下 InnoDB 的索引底层」,按这个层次答:
为什么 B+ 树:磁盘 IO 是瓶颈,要降低树高;非叶子只存 key 扇出大、树矮;叶子有序链表支持范围查询。
页结构:InnoDB 以 16KB 页为单位管理磁盘,页 = B+ 树节点。页内包含 File Header(含前后页指针)、Page Header、Infimum/Supremum、User Records、Page Directory、File Trailer。
页内查找:记录用 next_record 串成单向链表,页目录按「组」建槽,查找时先二分定位组再顺序扫。
一次查找:根页 → 内节点页 → 叶子页,三层树约 3 次 IO,页内二分。
页分裂:页满插入触发分裂,父节点加索引项,是性能抖动的主要来源。
为什么自增主键:顺序插入避免页分裂,且主键小则二级索引小。
能存多少:三层 B+ 树约 2000 万行,所以千万级主键查询只要 3 次 IO。