为什么 B+ 树而不是 B 树
问题引出
MySQL 的 InnoDB 引擎使用 B+树 作为索引结构，而不是 B 树、二叉树、哈希表。这是面试高频题，核心在于理解 B+树针对 磁盘 IO 特性 做的优化。
B 树 vs B+树 结构对比
graph TD
subgraph B树
B1[节点A<br/>key: 10 20<br/>data: 行数据<br/>children: 3] --> B2[节点B<br/>key: 5<br/>data: 行数据]
B1 --> B3[节点C<br/>key: 15<br/>data: 行数据]
B1 --> B4[节点D<br/>key: 25 30<br/>data: 行数据]
end
subgraph B+树
P1[非叶子节点<br/>key: 10 20<br/>只有索引<br/>无数据] --> P2[非叶子节点<br/>key: 5<br/>只有索引]
P1 --> P3[非叶子节点<br/>key: 15]
P1 --> P4[非叶子节点<br/>key: 25 30]
P2 --> L1[叶子节点<br/>key: 1 3 5<br/>data: 完整行]
P3 --> L2[叶子节点<br/>key: 10 15<br/>data: 完整行]
P4 --> L3[叶子节点<br/>key: 20 25 30<br/>data: 完整行]
end
核心区别
| 特性 | B 树 | B+树 |
|---|---|---|
| 数据存储位置 | 所有节点都存数据 | 仅叶子节点存数据 |
| 非叶子节点 | 存储 key + data | 仅存储 key（路由） |
| 叶子节点结构 | 没有链表 | ✅ 双向链表连接 |
| 范围查询效率 | 需要中序遍历 | ✅ 链表顺序扫描 |
| 单点查询 | 可能在中途就找到 | 必须走到叶子节点 |
| 每个节点存储的 key 数 | 少 | ✅ 多得多 |
为什么 B+树更适合磁盘 IO
关键因素一：扇出更高，树更矮
graph TD
subgraph B树节点[16KB页]
BT[B树<br/>key 8B + data 1KB ≈ 16个key]
end
subgraph B+树节点[16KB页]
BPT[B+树<br/>key 8B + 指针6B ≈ 1170个key]
end
B+树的非叶子节点只存 key 不存 data，同样的 16KB 页可以存储更多的 key，扇出（fan-out）更大。
对于 1000 万行数据：
| 结构 | 树高 |
|---|---|
| 二叉树 | ~24 层 |
| 平衡二叉树 | ~24 层 |
| B 树 | ~4 层 |
| B+树 | ~3 层 |
B+树比 B 树矮一层，意味着少一次磁盘 IO。
关键因素二：范围查询效率
-- 范围查询是数据库的常见操作
SELECT * FROM user WHERE id BETWEEN 10 AND 1000;
B 树：需要中序遍历，在父节点和子节点之间反复跳转。
graph LR
A[B树范围查询] --> B[找到10
向上找父节点]
B --> C[回到中间节点
再到下一个子节点]
C --> D[反复上下跳跃
效率极低]
B+树：找到起始叶子节点后，顺着链表向后遍历。
graph LR
A[B+树范围查询] --> B[找到10所在叶子节点]
B --> C[链表向后遍历<br/>→ 20 → 30 → ... → 1000]
C --> D[一次线性扫描<br/>效率极高]
关键因素三：磁盘预读友好
sequenceDiagram
participant Disk as 磁盘
participant BP as Buffer Pool
BP->>Disk: 读取一个页（B+树节点）
Disk-->>BP: 返回一整个16KB页
Note over BP,Disk: 一个页里包含1170个key<br/>一次IO解决1170个分支判断
B+树的一个节点正好对应一个数据页（16KB），一次磁盘 IO 加载整个页，充分利用了磁盘预读特性和空间局部性原理。
为什么不用哈希表（补充）
虽然哈希表单点查询 O(1) 更快：
-- 哈希索引无法处理
SELECT * FROM user WHERE id > 10; -- 范围查询 ❌
SELECT * FROM user ORDER BY id; -- 排序 ❌
SELECT MAX(id) FROM user; -- 聚合函数 ❌
SELECT * FROM user WHERE name LIKE '张%'; -- 模糊匹配 ❌
B+树是有序结构，上述全部支持。
面试要点
- 核心原因一：非叶子节点只存 key → 扇出高 → 树更矮 → IO 更少
- 核心原因二：叶子节点双向链表 → 范围查询/排序极高效
- 核心原因三：节点大小=数据页 → 磁盘预读友好
- 对比哈希：B+树除了单点查询，还支持范围/排序/模糊匹配
一句话总结：B+树是为磁盘 IO 定制的数据结构——树矮（少读盘）、叶子链表（范围快）、节点=页（预读友好）。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
暂无评论内容