下面系统性讲一下 B+ 树索引，这是数据库、文件系统中最核心的索引结构之一。
一、什么是 B+ 树索引？
B+ 树（B+ Tree） 是一种多路平衡查找树，专门为磁盘/外存访问优化设计的索引结构。
特点一句话概括：
所有数据都在叶子节点，内部节点只存键用于导航；叶子节点通过链表相连，支持高效范围查询。
二、B+ 树的结构
一棵典型的 B+ 树：
[ 20 | 40 ]
/ \
[10|20] [30|40]
/ | \ / | \
[1,3,5][12,15][18,19][25,28][35,38][45,50]
1. 节点类型
| 节点类型 | 存储内容 | 作用 |
|---|---|---|
| 根节点 | key + 指针 | 查询入口 |
| 内部节点 | key + 子节点指针 | 路由导航 |
| 叶子节点 | key + data（或主键） | 真正存放数据 |
2. 关键特性
- ✅ 多路（m 叉）：一个节点可有多于两个孩子
- ✅ 平衡：所有叶子节点在同一层
- ✅ 有序：节点内 key 按大小排序
- ✅ 叶子节点链表：方便范围扫描
- ✅ 内部节点不存真实数据
三、为什么数据库偏爱 B+ 树？
1. 减少磁盘 I/O（最重要）
磁盘读取是按 页（Page，通常 4KB/16KB） 来的：
- 二叉树：高度高 → I/O 次数多
- B+ 树：高度低（通常 3～4 层） → 一次查询只需 3～4 次磁盘 I/O
假设：
- 阶数 m = 100
- 3 层 B+ 树可存：
100^3 ≈ 100 万条记录
2. 非常适合范围查询
叶子节点之间有双向/单向链表：
SELECT * FROM orders WHERE id BETWEEN 100 AND 200;
✅ 定位到 100
✅ 顺着链表一路扫到 200
相比 B 树、哈希索引优势巨大。
3. 查询稳定（O(log n)）
无论查哪条数据，路径长度都一样（树高固定）。
四、B+ 树 vs B 树 vs 哈希索引
| 特性 | B+ 树 | B 树 | 哈希索引 |
|---|---|---|---|
| 数据位置 | 仅叶子节点 | 各层都有 | Key → Value |
| 范围查询 | ✅ 极好 | ⚠️ 一般 | ❌ 不支持 |
| 磁盘友好 | ✅ | ✅ | ❌ |
| 查询复杂度 | O(log n) | O(log n) | O(1) |
| 顺序扫描 | ✅ | ❌ | ❌ |
| 数据库使用 | ✅ 主流 | ⚠️ 少 | ⚠️ 特定场景 |
👉 InnoDB 聚簇索引 = B+ 树
五、B+ 树在数据库中的实际应用
1. InnoDB 聚簇索引（Clustered Index）
- 主键即索引
- B+ 树的 叶子节点存整行数据
- 一张表 只有一个聚簇索引
叶子节点：
[ id=1 | name="Tom" | age=18 ]
[ id=2 | name="Jerry" | age=20 ]
2. 二级索引（Secondary Index）
- 叶子节点存：索引列 + 主键值
- 回表：通过主键再去聚簇索引查整行数据
二级索引（name）：
[name="Tom" | id=1]
→ 再查聚簇索引 id=1
六、B+ 树的插入与分裂（简化版）
- 找到目标叶子节点
- 插入 key
- 若节点满了：
- 分裂成两个节点
- 中间 key 上提到父节点
- 若根节点分裂 → 树高 +1（很少发生）
✅ 始终保持平衡
七、B+ 树的删除与合并
- 删除 key
- 若节点过空：
- 与兄弟节点合并
- 或借一个 key
- 极端情况：树高降低
八、常见面试/实战考点
1. 为什么 B+ 树比红黑树更适合数据库？
- 红黑树是二叉树 → 高度高 → I/O 多
- B+ 树是多路树 → 高度低 → 磁盘友好
2. B+ 树一般多高？
- 通常 3～4 层
- 千万级数据也能 3 次 I/O 搞定
3. 为什么 MySQL 不用哈希索引做默认？
- 不支持范围查询
- 无法排序
- 冲突处理复杂
九、一句话总结
B+ 树是一种为磁盘设计的多路平衡查找树，所有数据集中在叶子节点，通过层级控制和链表连接，实现了高效的单点查询和卓越的范围查询能力，是现代数据库索引的事实标准。