引言
MySQL的InnoDB引擎使用B+树作为索引的数据结构。理解B+树是掌握索引优化的基础。
一、从二叉树到B+树的演进
1.1 二叉查找树（BST）
10
/ \
5 15
/ \ / \
3 7 12 20
问题：可能退化为链表，查询O(n)
1.2 平衡二叉树（AVL）
通过旋转保持平衡，查询O(log n)。
问题：
- 每个节点只存1个元素
- 树高度大：100万数据需要20层
- 磁盘IO次数多（每层一次IO）
1.3 B树
[10, 20, 30]
/ | | \
[1,5] [12,15] [22,25] [35,40]
特点：
- 多路：每个节点存多个元素
- 所有节点都存数据
- 降低树高度
问题：
- 非叶子节点也存数据，占用空间
- 范围查询需要中序遍历
1.4 B+树
非叶子节点（只存索引）：
[10, 20, 30]
/ | | \
/ | | \
叶子节点（存数据+索引）：
[1,5,8] → [10,12,15] → [20,22,25] → [30,35,40]
↑ 双向链表 ↑
特点：
- 非叶子节点只存索引
- 所有数据在叶子节点
- 叶子节点形成有序链表
二、B+树的核心特性
2.1 多路平衡
- 每个节点可存储多个键值
- InnoDB：16KB页，约1200个指针
- 3层B+树可存：1200 × 1200 × 1200 ≈ 17亿条记录
2.2 所有数据在叶子节点
非叶子节点：[5, 10, 15]（只存索引，不存数据）
↓
叶子节点：[1→data, 5→data, 8→data]（存完整数据）
优势：
- 非叶子节点更小，一次IO读更多索引
- 降低树高度
2.3 叶子节点链表
[1,2,3] ⇄ [5,6,7] ⇄ [10,11,12] ⇄ [15,16,17]
优势：
- 范围查询快（顺序扫描链表）
- 全表扫描快
三、为什么MySQL选择B+树？
3.1 vs 二叉树
100万数据：
- 二叉树：高度20，需要20次磁盘IO
- B+树：高度3，需要3次磁盘IO
3.2 vs 哈希
-- 哈希：等值查询快
WHERE id = 100; -- O(1)
-- 范围查询慢
WHERE id BETWEEN 100 AND 200; -- 无序，需要全扫描
-- B+树：范围查询快（有序）
WHERE id BETWEEN 100 AND 200; -- 顺序扫描
3.3 vs B树
| 对比项 | B树 | B+树 |
|---|---|---|
| 数据存储 | 所有节点 | 只在叶子节点 |
| 非叶子节点 | 存数据+索引 | 只存索引 |
| 一次IO读取 | 少 | 多 |
| 范围查询 | 中序遍历 | 叶子链表 |
| 全表扫描 | 慢 | 快 |
四、B+树的查询过程
4.1 单值查询
SELECT * FROM users WHERE id = 15;
查询过程：
- 从根节点开始：[5, 10, 15, 20]
- 15在[15, 20]区间，走第3个指针
- 到达叶子节点：[15→data]
- 返回数据
IO次数：3次（3层树）
4.2 范围查询
SELECT * FROM users WHERE id BETWEEN 10 AND 20;
查询过程：
- 找到起始位置（id=10）
- 沿着叶子节点链表顺序扫描
- 直到id=20
IO次数：3次（定位） + N次（扫描N个数据页）
五、B+树的插入和删除
5.1 插入
INSERT INTO users (id, name) VALUES (12, '张三');
过程：
- 找到叶子节点位置
- 插入数据
- 如果节点满，触发页分裂
页分裂：
- 节点满时，分裂为两个节点
- 中间键提升到父节点
- 影响性能
5.2 删除
DELETE FROM users WHERE id = 12;
过程：
- 找到数据位置
- 删除数据
- 如果节点过空，触发页合并
六、B+树高度分析
6.1 计算公式
层数 = ceil(log_扇出(记录数))
扇出 ≈ 页大小 / (键大小 + 指针大小)
≈ 16KB / (8B + 6B)
≈ 1200
6.2 容量估算
1层：1200条
2层：1200 × 1200 = 144万条
3层：1200 × 1200 × 1200 = 17亿条
结论：3层B+树足够存储千万到亿级数据。
七、实战分析
7.1 查看索引信息
-- 查看表的索引
SHOW INDEX FROM users;
-- 查看索引统计信息
SELECT
index_name,
stat_name,
stat_value
FROM mysql.innodb_index_stats
WHERE table_name = 'users';
7.2 估算索引高度
-- 计算表的索引高度（近似）
SELECT
CEIL(LOG(1200, COUNT(*))) AS estimated_height
FROM users;
八、总结
核心要点
- B+树特点：多路、平衡、叶子节点链表
- 优势：降低树高度、减少IO、范围查询快
- 容量：3层可存17亿数据
- 查询：等值O(log n)、范围扫描链表
- 维护：插入/删除可能触发页分裂/合并
记忆口诀
B+树多路又平衡，叶子节点存数据项，
非叶只存索引值，链表连接顺序访。
三层可存十亿量，磁盘IO三次访，
范围查询特别快，MySQL选它有道理。
本文字数：约2,300字 难度等级：⭐⭐⭐⭐（索引进阶）