MySQL使用 B+ 树作为索引结构的示例详解
目录
- 1、简述
- 2、什么是索引?为什么重要?
- 3、B+ 树 与其他结构的区别
- 3.1 B+ 树 vs B 树
- 3.2 为什么不是 Hash 索引
- 4、B+ 树为什么适合 mysql
- 4.1 高扇出,I/O 次数少
- 4.2 全部数据在叶子节点,遍历效率高
- 4.3 非叶子节点仅存索引,占用空间少
- 5、InnoDB 索引与 B+ 树的关系
- 5.1 主键索引(聚簇索引)
- 5.2 二级索引(辅助索引)
- 6、实践样例:验证 B+ 树索引特性
- 创建测试表
- 插入数据
- 查询测试
- 输出分析
- 7、结语
1、简述
在日常开发中,SQL 查询速度往往决定了系统响应的快慢,而索引的底php层结构直接影响数据库性能。你或许听过:
“MySQL 索引使用的是 B+ 树,而不是 Hash、红黑树、B 树。”
但你是否真正理解:为什么偏偏是 B+ 树?
本文将揭开 B+ 树在 MySQL 中大行其道的秘密,并结合 Java 示例和 SQL 实践帮助你彻底理解。
2、什么是索引?为什么重要?
索引是数据库中的“加速器”,作用类似于书籍的目录,它能快速定位数据位置,避免全表扫描。
索引结构常见的实现方式:
结构 | 特点 |
---|---|
Hash 表 | 精确查找快,但不支持范围查询 |
二叉搜索树 | 理论好,但高度不稳定 |
红黑树 | 自平衡,但节点过多,不适合磁盘 |
B 树 | 多路搜索,适合磁盘查找 |
✅ B+ 树 | 兼顾范围查找与磁盘效率,MySQL 首选 |
3、B+ 树 与其他结构的区别
3.1 B+ 树 vs B 树
特性 | B 树 | ✅ B+ 树 |
---|---|---|
数据存储位置 | 所有节点都存数据 | 仅叶子节点存数据 |
叶子节点结构 | 无需指针连接 | 有链表连接 |
范围查询性能 | 较差(需中序遍历) | 极优(链式遍历) |
均匀度 | 多层级有冗余 | 非叶子节点仅存索引 |
B+ 树更适合数据库的两个场景:
- 范围查找(BETWEEN、ORDER BY)
- 大量磁盘 I/O 操作(叶子节点有序链表,顺序读取更快)
3.2 为什么不是 Hash 索引
虽然 Hash 查找时间复杂度是 O(1),但存在严重缺陷:
缺点 | 举例 |
---|---|
❌ 不支持范围查询 | WHERE age BETWEEN 20 AND 30 |
❌ 无法排序 | ORDER BY 无法利用 |
❌ 不支持联合索引前缀匹配 | WHERE a = 1 AND 编程客栈b = 2 只能匹配全部 |
❌ 冲突概率高,影响性能 | hash 冲突时退化为链表 |
4、B+ 树为什么适合 MySQL
4.1 高扇出,I/O 次数少
B+ 树是“多叉平衡搜索树”,每个节点可包含几百甚至上千个 key,大大降低树的高度。
例如,扇出为 1000,1 亿条数据只需 3 层:
根RSetor → 中间层 → 叶子层(数据)
每次查询最多只需 3 次磁盘随机 I/O!
4.2 全部数据在叶子节点,遍历效率高
叶子节点之间是链表结构,天然支持范围查询、排序:
SELECT * FROM orders WHERE amount BETWEEN 100 AND 500 ORDER BY amount;
这种查询在 B+ 树中,只需要定位起点节点后顺序遍历,非常快。
4.3 非叶子节点仅存索引,占用空间少
B+ 树的非叶子节点不存储数据,只存索引字段,因此:
- 节点更小,磁盘页能装更多 key
- 树高度更低,查询更快
5、InnoDB 索引与 B+ 树的关系
InnoDB 支持两类 B+ 树索引:
5.1 主键索引(聚簇索引)
数据存储与主键索引绑定
叶子节点直接存储整行数据
查询主键非常快
SELECT * FROM users WHERE id = 100;
5.2 二级索引(辅助索引)
非主键字段索引
叶子节点存储的是主键值(回表)
SELECT * FROM users WHERE email = 'xx@example.com';
如果 email 是二级索引,则先查 B+ 树找到主键,再去主键索引查整行数据,称为 回表。
6、实践样例:验证 B+ 树索引特性
创建测试表
CREATE TABLE user ( id INT PRIMARY KEY, name VARCHAR(50), age INT, INDEX idx_age (age) ) ENGINE=InnoDB;
插入数据
for (int i = 1; i <= 1000000; i++) { String sql = "INSERT INTO user (id, name, age) VALUES (?, ?, ?)"; PreparedStatement ps = conn.prepareStatement(sql); javascript ps.setInt(1, i); ps.setString(2, "User" + i); ps.setInt(3, (int)(Math.random() * 100)); ps.executeUpdate(); }
查询测试
-- 使用索引(范围查询) 编程EXPLAIN SELECT * FROM user WHERE age BETWEEN 20 AND 30; -- 使用全表扫描(函数干扰索引) EXPLAIN SELECT * FROM user WHERE age + 0 = 25;
输出分析
type = range
:范围索引使用成功
key = idx_age
:使用了 age 索引
rows
明显少于总行数
总结:B+ 树是数据库索引的首选原因
优势 | 原因 |
---|---|
✅ I/O 成本低 | 多路搜索,树高低 |
✅ 范围查询高效 | 叶子节点有序链表 |
✅ 支持排序与前缀匹配 | WHERE、ORDER BY |
✅ 非叶节点存索引更紧凑 | 降低层级 |
✅ 回表机制高效 | 主键索引快速定位 |
7、结语
MySQL 使用 B+ 树,不是偶然,而是对磁盘性能、查询效率、排序能力等综合考量的结果。在 Java 开发中理解这些底层原理,可以:
编写更高效的 SQL
更合理地设计索引
减少因查询慢带来的系统瓶颈
到此这篇关于MySQL使用 B+ 树作为索引结构的示例详解的文章就介绍到这了,更多相关MySQL B+树索引内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章
精彩评论