MySQL索引数据结构深度解析：B+Tree vs Hash

MySQL索引数据结构深度解析：B+Tree vs Hash

• 引言
• 1. 索引数据结构全景图
• 2. B+Tree索引详解
  • 2.1 什么是B+Tree？
  • 2.2 B+Tree的结构特点
  • 2.3 B+Tree vs B-Tree
  • 2.4 B+Tree的查询过程
  • 2.5 B+Tree的三大优势
  • 2.6 B+Tree的适用场景
• 3. Hash索引详解
  • 3.1 什么是Hash索引？
  • 3.2 Hash索引的结构
  • 3.3 Hash索引的查询过程
  • 3.4 Hash索引的优缺点
  • 3.5 Hash索引的局限性演示
• 4. B+Tree vs Hash 对比
  • 4.1 全方位对比表
  • 4.2 查询性能对比图
  • 4.3 选择建议
• 5. 实际案例：索引选择错误导致的性能问题
  • 5.1 错误案例：使用Hash索引做范围查询
  • 5.2 正确设计
• 6. 面试题：为什么MySQL选择B+Tree作为默认索引？
  • 6.1 面试官考察点
  • 6.2 标准答案
• 7. 总结
  • 7.1 一句话总结
  • 7.2 选择指南

引言

当我们谈论MySQL索引时，本质上是在讨论数据结构。就像不同的工具箱适合不同的修理场景一样，不同的索引数据结构也各有优劣。MySQL主要支持两种索引数据结构：B+Tree和Hash。本文将深入剖析这两种结构的原理、优缺点以及适用场景，并用流程图和代码示例帮助你彻底理解。

1. 索引数据结构全景图

MySQL索引数据结构

索引数据结构

B+Tree索引

Hash索引

InnoDB默认

MyISAM默认

适合范围查询

适合排序

Memory默认

适合等值查询

不适合范围查询

不适合排序

2. B+Tree索引详解

2.1 什么是B+Tree？

B+Tree是一种平衡多路查找树，是B-Tree的变种。它是MySQL InnoDB和MyISAM存储引擎默认的索引结构。

2.2 B+Tree的结构特点

B+Tree结构示意图

双向链表

双向链表

双向链表

双向链表

双向链表

根节点
存储索引项
50 100 150

中间节点
20 35 50

中间节点
70 85 100

中间节点
120 135 150

叶子节点
10 15 20

叶子节点
25 30 35

叶子节点
40 45 50

叶子节点
60 65 70

叶子节点
75 80 85

叶子节点
90 95 100

B+Tree的核心特性：

2.3 B+Tree vs B-Tree

B+Tree

节点
10 20 30
指针

节点
5 8
指针

节点
15 18
指针

节点
25 28
指针

叶子节点
1 3 5 8
data

叶子节点
10 12 15 18
data

叶子节点
20 22 25 28
data

B-Tree

节点
10 20 30
data1 data2 data3

节点
5 8
data

节点
15 18
data

节点
25 28
data

2.4 B+Tree的查询过程

-- 示例：查找 age = 45 的记录-- 表结构CREATETABLEuser( id INTPRIMARYKEY, name VARCHAR(50), age INT,INDEX idx_age (age));-- 查询语句SELECT*FROMuserWHERE age =45;

查询步骤：

1. 根节点：加载根节点，比较45，确定去哪个子节点
2. 中间节点：逐层向下，直到叶子节点
3. 叶子节点：在叶子节点中找到age=45的记录
4. 回表（如果需要）：如果查询字段不都在索引中，通过主键回表取完整数据

数据表叶子节点中间节点根节点客户端数据表叶子节点中间节点根节点客户端查找age=4545>30,走右子树进入中间节点45<60,走左子树进入叶子节点在有序链表中找到45根据主键id回表返回完整数据

2.5 B+Tree的三大优势

优势一：范围查询高效

-- B+Tree范围查询SELECT*FROMuserWHERE age BETWEEN20AND30;-- 执行过程-- 1. 找到age=20的第一个记录-- 2. 沿着叶子节点的链表向后遍历-- 3. 直到遇到第一个age>30的记录停止

优势二：排序无需额外操作

-- B+Tree排序查询SELECT*FROMuserORDERBY age LIMIT10;-- 执行过程-- 1. 直接遍历最左边的叶子节点-- 2. 顺序读取即可，无需filesort

优势三：磁盘IO少

假设1000万条数据，B+Tree高度约为3-4 查询一条数据最多需要3-4次磁盘IO 每次IO约10ms，总耗时30-40ms 

2.6 B+Tree的适用场景

3. Hash索引详解

3.1 什么是Hash索引？

Hash索引基于哈希表实现，通过哈希函数将索引键值计算为哈希值，映射到对应的槽位。MySQL中只有Memory存储引擎默认支持Hash索引。

3.2 Hash索引的结构

Hash索引结构

键值: '张三'

Hash函数
CRC32

哈希值: 0x7F3A5C

键值: '李四'

Hash函数

哈希值: 0x2B8D1E

键值: '王五'

Hash函数

哈希值: 0x7F3A5C
哈希冲突

槽位0x7F3A5C

槽位0x2B8D1E

链表解决冲突
'张三' -> '王五'

3.3 Hash索引的查询过程

-- 示例：查找 name = '张三' 的记录-- 表结构（Memory引擎）CREATETABLEuser( id INT, name VARCHAR(50), age INT,INDEX idx_name USINGHASH(name))ENGINE=MEMORY;-- 查询语句SELECT*FROMuserWHERE name ='张三';

查询步骤：

1. 计算哈希值：对’张三’应用哈希函数，得到哈希值H
2. 定位槽位：根据H找到对应的槽位
3. 处理冲突：如果槽位有多个记录，遍历链表
4. 返回数据：找到匹配的记录直接返回（Memory引擎数据在内存中）

3.4 Hash索引的优缺点

3.5 Hash索引的局限性演示

-- 1. 不支持范围查询EXPLAINSELECT*FROMuserWHERE age >30;-- type: ALL (全表扫描，无法使用Hash索引)-- 2. 不支持排序EXPLAINSELECT*FROMuserORDERBY age;-- Extra: Using filesort (无法使用Hash索引)-- 3. 不支持部分索引-- 联合索引 (a,b)，查询条件只有aEXPLAINSELECT*FROM t WHERE a =1;-- 无法使用Hash索引，必须同时提供a和b-- 4. 不支持模糊查询EXPLAINSELECT*FROMuserWHERE name LIKE'张%';-- 无法使用Hash索引

4. B+Tree vs Hash 对比

4.1 全方位对比表

4.2 查询性能对比图

范围查询

B+Tree: 链表遍历

线性增长

Hash: 不支持

全表扫描

等值查询

B+Tree: 3-4次IO

约30-40ms

Hash: 1次计算

约1-2ms

4.3 选择建议

/** * 索引类型选择决策器 */publicclassIndexTypeChooser{/** * 根据查询模式推荐索引类型 */publicstaticStringrecommendIndexType(QueryPattern queryPattern){// 场景1：只有等值查询，没有范围查询if(queryPattern.isOnlyEqualityQueries()){return"可以考虑Hash索引（如果使用Memory引擎）";}// 场景2：包含范围查询或排序if(queryPattern.hasRangeQueries()|| queryPattern.hasOrderBy()){return"必须使用B+Tree索引";}// 场景3：模糊查询if(queryPattern.hasLikeQueries()){return"必须使用B+Tree索引（支持前缀匹配）";}// 默认推荐return"B+Tree索引（适用性最广）";}}// 查询模式类classQueryPattern{privateList<String> queryTypes;publicbooleanisOnlyEqualityQueries(){return queryTypes.stream().allMatch(t -> t.equals("EQ"));}publicbooleanhasRangeQueries(){return queryTypes.stream().anyMatch(t -> t.equals("GT")|| t.equals("LT")|| t.equals("BETWEEN"));}publicbooleanhasOrderBy(){return queryTypes.contains("ORDER_BY");}publicbooleanhasLikeQueries(){return queryTypes.contains("LIKE");}}

5. 实际案例：索引选择错误导致的性能问题

5.1 错误案例：使用Hash索引做范围查询

-- 错误设计CREATETABLE event_log ( id INTPRIMARYKEY, event_time DATETIME, content VARCHAR(255),INDEX idx_time USINGHASH(event_time)-- 错误：Hash索引不能范围查询)ENGINE=MEMORY;-- 查询某时间段日志SELECT*FROM event_log WHERE event_time BETWEEN'2024-01-01'AND'2024-01-02';-- 结果：全表扫描，性能极差

5.2 正确设计

-- 正确设计CREATETABLE event_log ( id INTPRIMARYKEY, event_time DATETIME, content VARCHAR(255),INDEX idx_time (event_time)-- 默认B+Tree)ENGINE=InnoDB;-- 查询某时间段日志SELECT*FROM event_log WHERE event_time BETWEEN'2024-01-01'AND'2024-01-02';-- 结果：使用索引，快速返回

6. 面试题：为什么MySQL选择B+Tree作为默认索引？

6.1 面试官考察点

6.2 标准答案

B+Tree作为MySQL默认索引结构，主要基于以下原因：

1. 适合磁盘存储：B+Tree每个节点可以存储大量索引项，树的高度低（通常3-4层），查询时磁盘IO次数少
2. 支持范围查询：叶子节点形成双向链表，范围查询时只需找到起点，然后沿着链表遍历，效率极高
3. 支持排序：数据按索引键值顺序存储，ORDER BY可以直接使用索引，无需额外排序
4. 查询稳定：任何查询从根节点到叶子节点的路径长度相同，性能稳定
5. 适应MySQL的OLTP场景：大多数业务场景既需要等值查询，也需要范围查询和排序

7. 总结

7.1 一句话总结

• B+Tree索引：像一本有目录和页码的书，既能精确查找，又能连续阅读
• Hash索引：像一本词典后的部首检字表，定位单个字极快，但不能连续查看

7.2 选择指南

最终结论：B+Tree是MySQL的默认选择，也是最稳妥的选择。Hash索引只在特定场景（Memory引擎、纯等值查询）下使用。理解两者的原理和适用场景，才能在设计索引时做出正确的选择。