MySQL为什么使用B+树作为索引结构？
📌 MySQL为什么使用B+树作为索引结构？
MySQL之所以选择B+树作为索引结构，是因为B+树同时兼顾了磁盘IO效率、范围查询能力、排序能力以及数据稳定性， 相比二叉树、红黑树、Hash表等数据结构，更适合作为数据库的磁盘索引结构。
1️⃣ 问题背景
面试中经常会被问到一个经典问题：
为什么不用Hash？
为什么不用B树？
很多人只会回答一句：
其实这只是其中一个原因。
InnoDB索引设计是一系列权衡的结果，既要考虑磁盘存储特点，也要考虑查询场景，还要考虑范围查询、排序、分页等业务需求。
理解B+树为什么存在，本质上是在理解数据库索引设计思想。
2️⃣ 核心原理
数据库中的数据量往往非常大。
几百万、几千万甚至上亿条记录根本不可能全部放入内存。
因此数据库查询最大的成本其实不是CPU计算，而是磁盘IO。
内存访问磁盘：毫秒级
两者相差几十万倍以上
所以数据库索引设计目标非常明确：
- 减少树的高度
- 减少磁盘访问次数
- 提升范围查询效率
- 支持排序查询
- 支持分页查询
B+树正是围绕这些目标设计出来的。
3️⃣ 数据结构分析
① 二叉查找树
├──30
└──80
二叉树查询时间复杂度理论上为O(logN)。
但如果数据有序插入：
会退化成链表。
② 红黑树
红黑树解决了二叉树退化问题。
它能保证树始终平衡。
时间复杂度稳定在：
但是红黑树有一个致命缺陷：
数据量达到千万级时：
意味着一次查询可能需要24层树高。
每层都可能触发一次磁盘IO。
IO成本极高。
③ B树
B树是多路平衡搜索树。
一个节点可以存储大量Key。
树高大幅降低。
但是B树每个节点既存索引又存数据。
导致一个页能存储的Key数量减少。
④ B+树
B+树进行了进一步优化。
- 非叶子节点只存索引
- 叶子节点存真实数据
- 叶子节点双向链表连接
[100 | 200]
↓ ↓ ↓
[1~99] [100~199] [200~300]
非叶子节点不存储数据，因此单页可以容纳更多Key。
树高进一步降低。
4️⃣ 算法分析
假设：
- 页大小16KB
- 主键8字节
- 指针6字节
一个索引节点大约：
≈ 1170个索引项
即：
树高为3时：
≈ 16亿条记录
这就是B+树最大的优势。
5️⃣ 执行流程
主键查询流程
↓
Root节点
↓
中间节点
↓
叶子节点
↓
返回数据
整个过程中只需要极少的磁盘IO。
范围查询流程
where id between 100 and 1000
B+树先定位到100。
然后通过叶子节点链表不断向后遍历。
无需回到根节点重新查找。
这就是范围查询极快的原因。
6️⃣ 实际案例
假设用户表：
id BIGINT PRIMARY KEY,
name VARCHAR(50),
age INT
);
主键索引采用聚簇索引B+树。
当执行：
WHERE id=10001;
通过B+树快速定位叶子节点。
当执行：
WHERE id BETWEEN 10000 AND 20000;
叶子节点链表顺序扫描。
效率远超Hash结构。
7️⃣ 优缺点分析
优点
- 树高极低
- 磁盘IO次数少
- 支持范围查询
- 支持排序查询
- 支持分页查询
- 天然适合磁盘存储
- 支持最左前缀匹配
缺点
- 实现复杂
- 维护成本高于Hash
- 频繁更新存在页分裂和页合并
8️⃣ 面试常见问题
为什么不用Hash？
Hash只能等值查询。
无法支持：
- 范围查询
- 排序查询
- LIKE前缀查询
- 分页查询
为什么不用红黑树？
红黑树树高太高。
磁盘IO次数远高于B+树。
为什么不用B树？
B树非叶子节点存储数据。
单页容纳Key更少。
树高更高。
范围查询效率也不如B+树。
B+树为什么适合范围查询？
因为所有叶子节点通过双向链表连接。
找到起点后可以顺序遍历。
InnoDB索引和数据为什么放一起？
InnoDB采用聚簇索引。
主键索引叶子节点直接存储整行数据。
可以减少一次回表操作。
9️⃣ 总结
✅ 多路平衡树降低树高
✅ 减少磁盘IO次数
✅ 非叶子节点只存索引，提高页利用率
✅ 支持范围查询
✅ 支持排序查询
✅ 支持分页查询
✅ 叶子节点链表天然适合顺序扫描
✅ 综合性能远优于红黑树、Hash和普通B树
面试中可以总结为一句话：
MySQL选择B+树并不是因为单点查询最快，而是因为它在磁盘IO、范围查询、排序查询、分页查询以及海量数据存储场景下达到了最优的综合平衡，因此成为数据库索引事实上的标准实现。
相关文章
-
分库分表分页实现方案 + 主流中间件解析
在高并发互联网系统中，随着数据量不断增长，单表数据很容易突破千万甚至亿级规模。此时传统数据库分页（LIMIT offset,size）会出现严重性能问题，查询延迟急剧上升。
NEW个对象 2026-06-11
-
聚簇索引与非聚簇索引的区别
聚簇索引：将数据存储与索引放到了一块，索引结构的叶子节点保存了行数据。 非聚簇索引：将数据与索引分开存储，索引结构的叶子节点指向了数据对应的位置。
NEW个对象 2024-12-25
-
Redis持久化机制详解：RDB与AOF原理、实现流程与生产实践
Redis持久化机制详解：RDB与AOF原理、实现流程与生产实践
NEW个对象 2026-06-12
