MySQL 索引底层结构揭秘：B-Tree 与 B+Tree 的区别与应用

文章目录

 一、背景知识：什么是 B-Tree 和 B+Tree？

  B-Tree（平衡多路查找树）

  B+Tree（B-Tree 的变种）

 二、结构对比：一张图看懂

 三、为什么 MySQL InnoDB 选择 B+Tree？

1. 范围查询更快

 2. 数据访问更稳定

3. 节点利用率更高，降低树高

 四、示例演示：索引结构差异

B-Tree 查找

B+Tree 查找（MySQL InnoDB 使用）

 五、实际应用中的建议

 六、总结

 附：面试回答模板

 推荐阅读

---

 一、背景知识：什么是 B-Tree 和 B+Tree？

  B-Tree（平衡多路查找树）

• 是一种多路平衡搜索树，每个节点可以有多个子节点。

• 每个节点同时存储键和值，并维护有序结构。

• 查找时可能在非叶子节点就找到目标数据。

  B+Tree（B-Tree 的变种）

• 所有实际数据只存在叶子节点。

• 非叶子节点只存键（索引），作为导航用途。

• 所有叶子节点之间通过链表连接，支持高效的范围查找。

---

 二、结构对比：一张图看懂

特性	B-Tree	B+Tree
数据存储位置	所有节点都存键和值	只有叶子节点存值，非叶子只存键
范围查询效率	较低，需遍历多个节点	高，叶子节点链表支持顺序遍历
查询命中位置	可能在中间节点	一定命中在叶子节点，访问路径更稳定
节点利用率	较低，数据占空间	更高，非叶节点只存键，占空间更少
是否支持顺序遍历	支持但不高效	天然支持（链表结构）
MySQL 支持情况	（MyISAM 用过早期版本）	InnoDB 默认使用 B+Tree

---

 三、为什么 MySQL InnoDB 选择 B+Tree？

1. 范围查询更快

SQL 中很多查询是范围查找：

SELECT * FROM orders WHERE price BETWEEN 100 AND 500;

B+Tree 中，叶子节点按大小排序，并通过链表连接，只需顺着链表扫描，性能极高。

---

 2. 数据访问更稳定

在 B+Tree 中，无论查找哪个值，路径总是走到叶子节点，避免 B-Tree 中“命中中间节点”的不确定性，有利于磁盘缓存和预读。

---

3. 节点利用率更高，降低树高

• 非叶子节点只存键值，占空间更小；

• 每层可存更多索引，树高更低，减少磁盘 IO 次数。

举例：如果单次 IO 能读 16KB，一个节点能放 400 个索引项，3 层 B+Tree 可管理 6400 万条记录，极大提高性能。

---

 四、示例演示：索引结构差异

B-Tree 查找

        [10 | 20]/    |    \[5]   [15]   [25]

可能在中间节点 [10 | 20] 就找到了值，不必下探。

---

B+Tree 查找（MySQL InnoDB 使用）

        [10 | 20]/    |    \[5]→[10]→[15]→[20]→[25]

所有数据都在叶子节点，查找、范围扫描、排序更高效。

---

 五、实际应用中的建议

场景	建议
主键索引	B+Tree 最适合
范围查询 / 排序字段	用 B+Tree（天然支持）
哈希查找	不建议使用 B-Tree / B+Tree，适用 Hash 索引（Memory 引擎）
高频随机查询	可配合缓存使用，优化 IO

---

 六、总结

B+Tree 是为数据库量身定制的索引结构，MySQL InnoDB 使用它正是因为它在磁盘存储、范围查询、空间效率上都表现优异。

对比点	B-Tree	B+Tree （MySQL 使用）
查询速度	中等	更稳定
范围查询效率	一般	极高
IO 次数	可能少	更可控
空间利用率	较低	更高

---

 附：面试回答模板

Q：MySQL 为什么使用 B+Tree 而不是 B-Tree？

答：

因为 B+Tree 将所有数据放在叶子节点，并通过链表连接，查询路径稳定、范围查询效率高、节点利用率高，能有效减少磁盘 IO，特别适合大规模数据场景。InnoDB 就是基于 B+Tree 的索引结构。

---

 推荐阅读

• 《高性能 MySQL》第三章 索引基础

• MySQL 官方文档：InnoDB 索引结构

• MIT 6.830 数据库系统课程：Tree-based Indexing