B 树和 B+ 树
一、为什么需要 B 树：从二叉树说起
1.1 二叉树在数据库中的困境
普通的二叉查找树（BST）理论上有 O(log n) 的查找效率，但在数据库中几乎无法使用：
问题一：二叉树太高了
假设 1000 万条数据：
- 二叉树高度 ≈ log₂(10⁷) ≈ 23 层
- 每访问一层 = 一次磁盘 IO
- 一次磁盘 IO ≈ 10ms（机械硬盘寻道）
- 一次查找 = 23 × 10ms = 230ms
问题二：数据存在磁盘上，不是内存里
- 内存访问：纳秒级
- 磁盘 IO：毫秒级（差距百万倍）
- 树越高 → IO 次数越多 → 查询越慢📌 核心矛盾：数据在磁盘上，每次 IO 都极其昂贵。所以数据库索引的目标是让树变得"矮胖"——用最少的 IO 次数完成查找。
1.2 从二叉树到多叉树
二叉树：每个节点只有 2 个子节点 → 树很高 → IO 次数多
多叉树：每个节点有 M 个子节点 → 树很矮 → IO 次数少B 树和 B+ 树都是多路平衡查找树，共同拥有平衡树的两个核心性质：
📌 共同结构特点：每个节点中，小的数据在左边，大的数据在右边，拥有 O(log n) 的二分查找效率。
二、B 树（B-Tree）详解
2.1 B 树的结构
[ 30 | 60 ] ← 根节点（包含数据和索引）
/ | \
/ | \
[ 10 | 20 ] [ 40 | 50 ] [ 70 | 80 | 90 ] ← 中间节点（也包含数据）
/ | \ / | \ / | | \
叶子... 叶子... 叶子... 叶子... 叶子...... 叶子节点（也包含数据）B 树的 4 个核心特点：
|
特点 |
说明 |
|---|---|
|
所有节点都存储数据 |
根节点、中间节点、叶子节点——每个节点既存索引 Key 也存完整数据行 |
|
多路平衡 |
每个节点最多 M 个子节点（M 为阶数），所有叶子节点在同一层 |
|
节点内有序 |
每个节点内的 Key 从小到大排序，支持二分查找 |
|
子树范围约束 |
对于节点中相邻的两个 Key（K₁ < K₂），它们之间的子树中的所有 Key 满足 K₁ < key < K₂ |
2.2 B 树的查找过程
查找 key = 45：
1. 从根节点 [30|60] 开始
30 < 45 < 60 → 走到中间子树
2. 在 [40|50] 中查找
40 < 45 < 50 → 走到中间子树
3. 在叶子节点中找到 45 → 直接返回该节点中存储的数据
共 3 次 IO2.3 B 树的优缺点
|
优点 |
缺点 |
|---|---|
|
每个节点都存数据，有时查找可以提前在中间节点结束，IO 次数可能比 B+ 树少 |
中间节点存数据 → 每个节点能存的索引数量变少 → 树更高 |
|
结构更简单，没有叶子节点链表 |
不支持高效范围查询（需要中序遍历回溯，跨层 IO 很多） |
|
|
叶子节点没有链表，排序和范围查找需要额外 IO |
三、B+ 树（B+Tree）详解
3.1 B+ 树的三大核心特征
[ 30 | 60 ] ← 非叶子节点（只存索引，不存数据）
/ | \
/ | \
[ 10 | 20 ] [ 40 | 50 ] [ 70 | 80 | 90 ] ← 非叶子节点（只存索引）
/ | \ / | \ / | | \
叶子... 叶子... 叶子... 叶子... 叶子......叶子... ← 叶子节点（存索引+完整数据）
│ │
└──────────── 双向链表连接 ────────────────────────────┘特征一：非叶子节点只存索引，不存数据
B 树中间节点：[ Key₁ | Data₁ | Key₂ | Data₂ | Key₃ | Data₃ ]
↑ 每个 Key 都带着完整数据行，占空间大
一个 16KB 的页（InnoDB 默认页大小）存不了几个 Key
B+树中间节点：[ Key₁ | Key₂ | Key₃ | Key₄ | Key₅ | ... ]
↑ 只存索引值，不存数据，占空间极小
同样 16KB 的页，能存几百上千个 Key📌 这意味着同样高度的 B+ 树能存储的数据量远大于 B 树。高度相同 → IO 次数相同 → B+ 树单次 IO 能囊括更多数据。
特征二：叶子节点之间用双向链表连接
叶子层：[10|data] ⇄ [20|data] ⇄ [30|data] ⇄ [40|data] ⇄ [50|data] ⇄ [60|data] ...
↑ ↑
head tail这对范围查询是巨大的优势：
-- 查找 id > 10 AND id < 20
-- B+ 树：先找到 id=11 的叶子节点 → 顺着双向链表往后遍历 → 直到 id=20 停止
-- 沿途所有数据直接拿到，不需要回溯到父节点特征三：所有叶子节点存储完整数据，并且按 Key 有序排列
叶子节点本身就是天然排好序的全量数据。
3.2 B+ 树的查找过程
精确查找 key = 45：
1. 根节点 [30|60] → 30 < 45 < 60 → 走中间子树
2. 中间节点 [40|50] → 40 < 45 < 50 → 走中间子树
3. 叶子节点找到 45 → 返回数据
范围查找 key 在 15-35：
1. 找到 key=15 在叶子层的位置
2. 顺着双向链表向右遍历
3. 依次取出 15、20、25、30、35 的数据
4. 直到 key > 35 停止
整个过程不需要回溯父节点，沿着链表走就行四、B 树 vs B+ 树：为什么 MySQL 选择 B+ 树
4.1 核心对比表
|
对比维度 |
B 树 |
B+ 树 |
|---|---|---|
|
数据存储位置 |
所有节点都存数据 |
只有叶子节点存数据 |
|
非叶子节点内容 |
索引 Key + 完整数据行 |
只存索引 Key |
|
单节点能存的索引数 |
少（被数据占空间） |
多（省空间，可存更多 Key） |
|
同样高度存储量 |
少 |
多（能多好几个数量级） |
|
范围查询 |
慢（需中序遍历，不断跨越层级） |
快（叶子节点双向链表直接遍历） |
|
排序效率 |
需额外排序 |
叶子天然有序，无需额外排序 |
|
单条精确查找 |
有时更快（中间节点命中即返回） |
必须到叶子节点（多一次 IO） |
|
全表扫描 |
需遍历所有层 |
只需遍历叶子层链表 |
|
磁盘 IO 利用率 |
低（数据混杂，有效索引少） |
高（每页全是索引，一次 IO 收益更大） |
4.2 为什么 B+ 树的"多一次 IO"可以接受
B 树精确查找某个 key：
可能在根节点或中间节点就命中 → 提前返回 → 比如 2 次 IO
B+ 树精确查找：
必须走到底（叶子层） → 固定 3-4 次 IO
看起来 B 树更优？实际上：
- B+ 树的高度基本固定为 3-4 层（千万级数据 = 3 层），多 1 次 IO 的代价极小
- B+ 树在中间节点命中是小概率事件（内存缓存使得根和中间节点常驻 Buffer Pool）
- B+ 树带来的范围查询性能提升远远超过精确查找的微小损失
- 实际业务中，范围查询非常常见（
WHERE id > ?,ORDER BY,BETWEEN）
4.3 一句话总结
📌 B+ 树同样高度存的数据比 B 树多得多（非叶子不存数据）；B+ 树支持高效范围查找和排序（叶子双向链表 + 天然有序）。B 树唯一的优势是偶尔精确查找能少一次 IO，但业务中范围查询远比单条精确查找常见。
五、为什么 B+ 树 3 层就能存千万级数据
5.1 数学计算
假设条件（InnoDB 默认）：
- 页大小：16KB = 16384 字节
- 主键类型：BIGINT = 8 字节
- 指针大小：6 字节（InnoDB 页号）
- 每个索引条目 = 8 + 6 = 14 字节
- 每页非叶子节点可存索引数：16384 / 14 ≈ 1170 个
假设每行数据 1KB（页内存储）：
- 每页叶子节点可存数据行：16384 / 1024 ≈ 16 行
三层 B+ 树存储量：
- 第 1 层（根节点）： 1 页 × 1170 个索引 = 1170 个指针
- 第 2 层（中间节点）： 1170 页 × 1170 个索引 = 1,368,900 个指针
- 第 3 层（叶子节点）：1,368,900 页 × 16 行数据 ≈ 2100 万行
结论：3 层 B+ 树 ≈ 2000 万行数据，4 层可达数百亿行。5.2 直观理解
为什么 3 层能存这么多？关键是 "非叶子节点只存索引，不存数据"
一个 16KB 的页：
┌────────────────────────────┐
│ B 树非叶子节点 │
│ [Key|Data|Key|Data|Key...] │ ← 数据占大量空间，一页只能存几十个 Key
│ 一页可能只存 50-100 个索引 │
└────────────────────────────┘
┌────────────────────────────┐
│ B+ 树非叶子节点 │
│ [Key|Key|Key|Key|Key...] │ ← 纯索引，一页能存 1170 个 Key
│ 一页存 1170 个索引 │
└────────────────────────────┘5.3 性能实测参考
|
数据量 |
B+ 树层数 |
每次查询 IO 次数 |
查询耗时参考 |
|---|---|---|---|
|
10 万 |
2 层 |
2 次 |
< 50ms |
|
500 万 |
3 层 |
3 次 |
< 100ms |
|
1000 万 |
3 层 |
3 次 |
约 1 秒 |
|
2000 万 |
3-4 层 |
3-4 次 |
明显变慢，需要优化 |
|
5000 万+ |
4 层 |
4 次 |
必须分库分表 |
📌 千万级别数据通常在 1 秒左右，但到两千万时 SQL 执行时间会明显变长——因为 Buffer Pool 无法全部缓存，磁盘 IO 增多。
六、B+ 树的插入操作
6.1 插入的核心规则
B+ 树插入遵循以下规则：
- 新数据始终插入到叶子节点
- 叶子节点未满：直接插入，保持有序
- 叶子节点已满：分裂——把中位数提升到父节点，原节点一分为二
- 父节点递归满载：向上级联分裂，极端情况分裂到根节点
6.2 插入过程图解
初始状态（假设每个节点最多 3 个 Key）：
叶子[10, 20] ← 有 2 个 Key，还能存
插入 15：
叶子[10, 15, 20] ← 刚好 3 个，没满 ✓
插入 25：
叶子[10, 15, 20, 25] ← 4 个，超了！要分裂！
│
分裂成两个：
[10, 15] [20, 25]
↑ ↑
└── 将 20 提升到父节点 ──┘
父节点 [20]
/ \
[10,15] [20,25]6.3 级联分裂
如果父节点也满了：
父节点 [20, 40, 60] 已经 3 个 Key，再收一个子节点指针 80 → 4 个，也超了！
父节点分裂：
中位 Key=40 提升到祖父节点
父节点一分为二：[20] 和 [60, 80]
如果祖父节点也满了 → 继续向上分裂 → 一直到根节点
根节点也满了 → 创建一个新的根，树高 +1
这就是 B+ 树长高的唯一方式。📌 面试重点：B+ 树的插入始终在叶子节点。节点满则分裂，分裂可能向上级联。根节点分裂是树增高的唯一原因。
七、MySQL 其他索引类型
7.1 Hash 索引
|
特性 |
Hash 索引 |
B+ 树索引 |
|---|---|---|
|
查找方式 |
哈希计算，O(1) |
二分查找，O(log n) |
|
等值查找 |
✅ 极快 |
✅ 较快 |
|
范围查找 |
❌ 不支持 |
✅ 高效（双向链表） |
|
排序 |
❌ 不支持 |
✅ 叶子天然有序 |
|
最左前缀 |
❌ 不支持 |
✅ 支持联合索引最左前缀 |
|
模糊查找 |
❌ 不支持 |
✅ 支持前缀匹配 |
|
冲突处理 |
哈希冲突影响性能 |
不存在冲突 |
|
适用场景 |
等值查找的缓存表 |
MySQL 默认，适用所有场景 |
7.2 自适应哈希索引（Adaptive Hash Index）
InnoDB 还有一个自动机制：如果某些数据页被频繁访问（热点数据），InnoDB 会自动在 Buffer Pool 中为它们建立哈希索引，加速等值查找。这是自动的、不可手动控制的。
八、B+ 树的优势总结
|
维度 |
普通二叉树 |
B 树 |
B+ 树 |
|---|---|---|---|
|
树的高度 |
极高（千万级 ~23 层） |
较低（千万级 ~4-5 层） |
最低（千万级 ~3 层） |
|
每次查找 IO |
20+ 次 |
4-5 次 |
3 次 |
|
磁盘 IO 利用率 |
低 |
中 |
高 |
|
范围查询 |
慢 |
较慢 |
快 |
|
排序支持 |
不支持 |
不支持 |
支持 |
|
全表扫描 |
需遍历整棵树 |
需遍历整棵树 |
只需遍历叶子链表 |
|
数据库适用性 |
❌ |
一般 |
✅ MySQL InnoDB 默认 |
九、面试高频追问
Q: B+ 树的非叶子节点存不存数据？
不存。非叶子节点只存索引 Key + 子节点指针。所有完整数据行都在叶子节点。这是 B+ 树和 B 树最核心的区别。
Q: B+ 树的范围查询为什么快？
叶子节点之间用双向链表连接。找到起点后，沿链表往后遍历即可，不需要回溯父节点。时间复杂度 O(log n + k)，k 是范围内的数据量。
Q: B+ 树 3 层为什么能存千万级数据？
InnoDB 默认页 16KB，非叶子每个索引条目约 14 字节，每页存约 1170 个索引。两层非叶子（根+一层中间）可索引 1170×1170≈137 万个叶子页，每页假设存 10+ 行数据，总量约 2000 万行。
Q: 为什么不用 B 树做数据库索引？
B 树中间节点存数据 → 同样页面大小能存的索引数少 → 同样数据量树更高 → IO 更多。且 B 树不支持高效范围查询。唯一的"有时精确查找少一次 IO"优势在范围查询劣势面前不值一提。
Q: B+ 树插入什么时候会分裂？
叶子节点已满（超过页大小限制）时触发分裂。将中位数提升到父节点，原节点分成两个。父节点满则向上级联分裂。根节点分裂是树增高的唯一途径。
Q: 为什么不用跳表（SkipList）？
跳表是内存数据结构，依赖指针随机访问，不擅长磁盘场景。B+ 树的节点大小与磁盘页对齐（16KB），每次 IO 都能充分利用。