B+ 树原理与数据库索引
B+ 树是数据库索引的核心数据结构，理解它的原理对于数据库性能优化至关重要。
一、为什么数据库需要 B+ 树
1.1 二叉树的问题
如果使用二叉搜索树:
10
/ \
5 15
/ \ / \
3 7 12 20
/ \
1 4
假设数据量 = 100万
树高度 ≈ log₂(1000000) ≈ 20
问题:
- 每个节点只有 2 个子节点
- 树的高度较高
- 每次查询需要 20 次磁盘 I/O
- 磁盘 I/O 是性能瓶颈！1.2 磁盘 I/O 的特点
| 操作 | 耗时 |
|---|---|
| 内存访问 | ~100 纳秒 |
| SSD 随机读 | ~100 微秒 |
| HDD 随机读 | ~10 毫秒 |
内存 vs HDD：10万倍的差距！
减少磁盘 I/O 次数是数据库索引设计的核心目标。
1.3 B 树的思路
让每个节点存储多个键值，增加分支数：
B 树 (阶数=3):
[10 | 20]
/ | \
[1,5] [12,15] [25,30]
- 每个节点最多 3 个子节点
- 树的高度大幅降低
- 同样 100万 数据，高度可能只有 3-4 层二、B 树的基本概念
2.1 B 树的定义
B 树（Balance Tree）是一种自平衡的多路搜索树，一个 m 阶 B 树满足：
1. 每个节点最多有 m 个子节点
2. 每个非根节点至少有 ⌈m/2⌉ 个子节点
3. 根节点至少有 2 个子节点（除非是叶子节点）
4. 所有叶子节点在同一层
5. 节点内的键值有序排列2.2 B 树结构示例（3阶）
[10 | 20]
/ | \
[1 | 5] [12 | 15] [25 | 30]
/ | \ / | \ / | \
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
数据 数据 数据 数据 数据 数据 数据 数据 数据2.3 B 树的特点
| 特点 | 说明 |
|---|---|
| 多路平衡 | 每个节点可以有多个子节点 |
| 节点有序 | 节点内键值有序排列 |
| 叶子同层 | 所有叶子节点在同一层 |
| 数据分布 | 每个节点都存储数据 |
三、B+ 树的结构特点
3.1 B+ 树 vs B 树
B 树:
[10 | 20]
/ | \
[1 | 5] [12 | 15] [25 | 30]
↓ ↓ ↓ ↓ ↓ ↓
数据 数据 数据 数据 数据 数据
B+ 树:
[10 | 20] ← 非叶子节点只存索引
/ | \
[1|5|10]→[12|15|20]→[25|30] ← 叶子节点存数据，且链表连接3.2 B+ 树的核心特点
特点1：非叶子节点只存索引
B 树节点: [键值 | 数据 | 指针 | 指针 | 指针]
B+ 树节点: [键值 | 指针 | 指针 | 指针]
好处:
- 同样的节点大小可以存更多键值
- 树更矮，I/O 次数更少特点2：叶子节点存储所有数据
所有数据都在叶子节点
非叶子节点只是索引，用于路由
好处:
- 查询性能稳定，所有查询都走到叶子
- 范围查询高效特点3：叶子节点用链表连接
[1|5|10] ⇄ [12|15|20] ⇄ [25|30]
↑ ↑ ↑
双向链表 双向链表 双向链表
好处:
- 范围查询只需遍历链表
- 排序查询高效
- 支持反向遍历3.3 B+ 树结构图示
[30 | 60] ← 根节点 (索引)
/ | \
[10|20|30] [40|50|60] [70|80|90] ← 内部节点 (索引)
/ | | \ / | | \ / | | \
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[1|5]→[10|15]→[20|25]→[30|35]→[40|45]→... ← 叶子节点 (数据)
↕ ↕ ↕ ↕ ↕
双向链表连接所有叶子节点四、B+ 树的插入操作
4.1 插入规则
1. 找到合适的叶子节点
2. 如果叶子节点未满，直接插入
3. 如果叶子节点已满，分裂：
a. 叶子节点分裂成两个
b. 中间键值提升到父节点
c. 如果父节点也满，继续分裂4.2 插入示例（3阶B+树）
初始状态:
[10 | 20]
/ | \
[1|5] [12|15] [25|30]
插入 8:
找到叶子节点 [1|5]，未满，直接插入
[10 | 20]
/ | \
[1|5|8] [12|15] [25|30]
插入 3:
叶子节点 [1|5|8] 已满，需要分裂
分裂: [1|3] 和 [5|8]，中间值 5 提升
[5 | 10 | 20]
/ | | \
[1|3] [5|8] [12|15] [25|30]
如果父节点也满，继续分裂...4.3 插入操作代码思路
python
def insert(node, key, value):
if node.is_leaf:
if node.is_full:
# 分裂叶子节点
new_node = node.split()
# 将中间键提升到父节点
parent.insert_key(new_node.min_key, new_node)
else:
node.insert(key, value)
else:
# 找到合适的子节点
child = node.find_child(key)
insert(child, key, value)五、B+ 树的删除操作
5.1 删除规则
1. 找到包含该键的叶子节点
2. 删除该键
3. 如果叶子节点太小（少于 ⌈m/2⌉-1 个键）：
a. 尝试从兄弟节点借一个键
b. 如果兄弟也小，合并节点
4. 更新父节点的索引5.2 删除示例
初始状态:
[5 | 10 | 20]
/ | | \
[1|3] [5|8] [12|15] [25|30]
删除 8:
叶子节点 [5|8] 变成 [5]，键数 = 1 < ⌈3/2⌉-1 = 1
从兄弟借: 兄弟 [12|15] 有多余的键
借 12: [5] → [5|12]，父节点索引更新
[5 | 12 | 20]
/ | | \
[1|3] [5|12] [15] [25|30]5.3 合并节点
如果兄弟也没有多余的键:
删除前:
[10]
/ \
[1|5] [12|15]
删除 5:
[1|5] → [1]，兄弟 [12|15] 也小
合并: [1] + [12|15] = [1|12|15]
父节点删除键 10
结果:
[1|12|15]六、B+ 树的优势分析
6.1 查询性能稳定
B 树:
- 最好情况: 查到根节点 = 1 次 I/O
- 最坏情况: 查到叶子节点 = h 次 I/O
- 性能不稳定
B+ 树:
- 所有查询都走到叶子节点 = h 次 I/O
- 性能稳定，可预测6.2 范围查询高效
sql
-- 查询 id 在 10-100 之间的记录
SELECT * FROM users WHERE id BETWEEN 10 AND 100;B 树:
- 需要中序遍历整棵树
- 可能需要多次回溯父节点
B+ 树:
- 找到 id=10 的叶子节点
- 沿着链表遍历到 id=100
- 非常高效！6.3 磁盘 I/O 更少
| 对比项 | B 树 | B+ 树 |
|---|---|---|
| 节点存储 | 键值+数据 | 只存键值 |
| 单节点容量 | 较小 | 较大 |
| 树高度 | 较高 | 较矮 |
| I/O 次数 | 较多 | 较少 |
6.4 完整对比
| 特性 | B 树 | B+ 树 |
|---|---|---|
| 数据位置 | 所有节点 | 只在叶子 |
| 叶子链表 | 无 | 有 |
| 范围查询 | 效率低 | 效率高 |
| 查询稳定性 | 不稳定 | 稳定 |
| 空间利用 | 较低 | 较高 |
| 适用场景 | 文件系统 | 数据库索引 |
七、MySQL InnoDB 中的应用
7.1 聚簇索引（Clustered Index）
InnoDB 的主键索引就是 B+ 树结构:
叶子节点存储: 完整的行数据
非叶子节点: 主键值 + 指针
[10 | 20] ← 主键索引
/ | \
[1|5] [12|15] [25|30] ← 叶子节点存储完整行
↓ ↓ ↓
行数据 行数据 行数据特点：
- 每个表只能有一个聚簇索引（通常是主键）
- 数据按主键顺序物理存储
- 主键查询非常快
7.2 二级索引（Secondary Index）
非主键索引（如 name 索引）:
叶子节点存储: 主键值（不是完整行）
非叶子节点: 索引列值 + 指针
["Alice" | "Bob"] ← name 索引
/ | \
["Amy"] ["Alice"] ["Bob"] ← 叶子节点存主键值
↓ ↓ ↓
10 20 30 ← 回表查主键索引获取完整数据回表查询：
sql
-- 使用二级索引查询
SELECT * FROM users WHERE name = 'Alice';
-- 步骤:
-- 1. 在 name 索引中找到 Alice，得到主键 id=20
-- 2. 用 id=20 去主键索引查完整行数据（回表）7.3 覆盖索引
sql
-- 如果查询的列都在索引中，不需要回表
SELECT id, name FROM users WHERE name = 'Alice';
-- name 索引的叶子节点已经存储了 id 和 name
-- 直接返回，无需回表7.4 联合索引与最左前缀
sql
-- 联合索引 (name, age)
CREATE INDEX idx_name_age ON users(name, age);索引结构:
[("Alice",20) | ("Bob",25)]
/ | \
[("Alice",20)] [("Amy",30)] [("Bob",25)]
可以使用索引的查询:
- WHERE name = 'Alice' ✓
- WHERE name = 'Alice' AND age = 20 ✓
- WHERE age = 20 ✗ (不满足最左前缀)八、索引设计最佳实践
8.1 选择合适的索引列
sql
-- 适合建索引的列:
-- 1. WHERE 条件频繁使用的列
-- 2. JOIN 连接的列
-- 3. ORDER BY 排序的列
-- 4. 高选择性的列（不同值多）
-- 不适合建索引的列:
-- 1. 频繁更新的列
-- 2. 选择性低的列（如性别）
-- 3. 数据量小的表8.2 索引列顺序
sql
-- 联合索引的列顺序很重要
-- 规则: 选择性高的列放前面
-- 例如: users 表
-- name 选择性: 0.9 (几乎不重复)
-- age 选择性: 0.01 (很多重复)
-- gender 选择性: 0.001 (只有几个值)
-- 推荐: (name, age, gender)8.3 避免索引失效
sql
-- ❌ 在索引列上使用函数
WHERE YEAR(create_time) = 2025
-- ✅ 改为范围查询
WHERE create_time >= '2025-01-01' AND create_time < '2026-01-01'
-- ❌ 隐式类型转换
WHERE phone = 13800138000 -- phone 是 VARCHAR
-- ✅ 使用正确类型
WHERE phone = '13800138000'
-- ❌ LIKE 左模糊
WHERE name LIKE '%风'
-- ✅ 右模糊可以使用索引
WHERE name LIKE '沐%'8.4 覆盖索引优化
sql
-- 创建覆盖索引
CREATE INDEX idx_covering ON orders(user_id, status, create_time);
-- 查询只访问索引，无需回表
SELECT user_id, status, create_time
FROM orders
WHERE user_id = 1001 AND status = 1;九、总结
9.1 B+ 树的核心优势
| 优势 | 说明 |
|---|---|
| 树高度低 | 多路平衡，减少磁盘 I/O |
| 查询稳定 | 所有查询都走到叶子节点 |
| 范围查询高效 | 叶子节点链表连接 |
| 空间利用率高 | 非叶子节点只存索引 |
9.2 B+ 树在数据库中的应用
| 应用 | 说明 |
|---|---|
| 聚簇索引 | 叶子存完整行数据 |
| 二级索引 | 叶子存主键值 |
| 联合索引 | 多列组合索引 |
| 覆盖索引 | 避免回表查询 |
9.3 索引设计原则
1. 选择高选择性的列建索引
2. 联合索引注意最左前缀
3. 避免索引失效的写法
4. 使用覆盖索引减少回表
5. 控制索引数量，避免过度索引学习建议
- 理解 B 树到 B+ 树的演进原因
- 掌握 B+ 树的插入删除过程
- 理解聚簇索引和二级索引的区别
- 结合 MySQL 实际使用理解索引优化
- 通过 EXPLAIN 验证索引使用情况