MySQL索引数据结构：B+树 vs 哈希索
MySQL索引数据结构：B+树 vs 哈希索
一、核心概览
| 特性 | B+树索引 | 哈希索引 |
|---|---|---|
| 底层结构 | 平衡多叉树 | 哈希表（数组 + 链表/红黑树） |
| 默认引擎 | InnoDB、MyISAM的默认索引类型 | Memory引擎的默认索引，InnoDB支持自适应哈希索引（内部自动构建） |
| 核心思想 | 有序存储，基于比较的搜索。 | 散列映射，基于哈希函数的精确匹配。 |
二、B+树索引深度解析
1. 数据结构特点
平衡多路搜索树：非二叉树，一个节点可包含多个子节点（大大降低树高）。
数据有序：所有节点内的键值按顺序排列。
数据全在叶子节点：非叶子节点仅存储键值（索引）和子节点指针，不存储实际数据行。叶子节点存储完整的键值及对应的数据行信息（在InnoDB中，聚簇索引叶子节点存数据行，非聚簇索引存主键）。
叶子节点双向链表：所有叶子节点通过指针串联成一个有序双向链表。
2. 优势
出色的范围查询性能：得益于数据有序和叶子节点链表，可以快速定位范围起点，然后通过链表顺序扫描，效率极高。
稳定的查询性能（O(log n)）：作为平衡树，从根到叶的搜索路径长度均衡，不会出现性能剧烈波动。
支持排序和分组：索引本身有序，
ORDER BY、GROUP BY操作可直接利用索引，避免额外排序。支持最左前缀匹配：对于联合索引，可以高效利用索引的最左前缀进行查询。
支持覆盖索引：当查询所需列全部包含在索引中时，无需回表，直接在索引中完成查询。
3. 劣势
单条记录的等值查询在极致场景下可能略慢于哈希索引（但仍非常快）。
维护成本相对较高：插入、删除数据时，为维持树平衡，可能需要进行复杂的节点分裂与合并。
4. 经典适用场景
绝大多数在线事务处理（OLTP）和在线分析处理（OLAP）场景。
需要范围查询（
BETWEEN，>，<）、排序（ORDER BY）、分组（GROUP BY）的操作。使用
LIKE 'prefix%'的前缀匹配查询。
三、哈希索引深度解析
1. 数据结构特点
基于哈希表：对索引键值应用哈希函数，计算出一个哈希码（hash code）。
直接定位：哈希码对应到哈希表中的某个“桶”（bucket）。
解决冲突：桶内通常以链表形式存储实际数据行的指针（或主键值）。当发生哈希冲突时（不同键值哈希到同一桶），在链表内遍历。
2. 优势
极致的等值查询速度（理论O(1)）：只需一次哈希计算和一次定位，速度通常快于B+树，尤其是在数据量巨大时。
简单高效：对于精确匹配查询，路径非常短。
3. 劣势与限制
完全不支持范围查询：因为哈希函数打乱了数据的原始顺序，无法进行
>，<，BETWEEN等操作。不支持排序：无法利用索引进行
ORDER BY。不支持部分索引列匹配（最左前缀）：哈希索引是基于整个索引键值计算哈希的。对于
(A, B, C)的联合哈希索引，查询条件必须包含所有列（或精确匹配哈希计算时的组合），仅查询(A)或(A, B)无法使用该索引。哈希冲突影响性能：当存在大量重复键值或哈希冲突严重时，链表会变长，查询性能退化为
O(n)。不支持
LIKE模糊查询：即使是LIKE 'abc%'也无法利用哈希索引。
4. 经典适用场景
仅等值查询（
=，IN）且数据离散度高的场景。内存表（如MySQL的Memory引擎），数据常驻内存，追求极致点查速度。
InnoDB的自适应哈希索引：InnoDB会监控表上的查询模式，如果发现某些索引值被频繁用于等值查询，它会在内存中自动为这些热点数据页建立一个哈希索引，以加速访问。此功能对用户透明。
四、核心对比与选型总结
| 对比维度 | B+树索引 | 哈希索引 |
|---|---|---|
| 查询类型 | 等值、范围、排序、前缀匹配 | 仅等值查询 |
| 查询性能 | 稳定，O(log n)。范围查询优势巨大。 | 极端快，理论O(1)，但仅限等值。冲突时退化。 |
| 数据有序性 | 有序，是核心优势。 | 无序，是主要限制。 |
| 是否支持覆盖索引 | 支持 | 支持，但意义有限。 |
| 是否支持联合索引部分匹配 | 支持（最左前缀） | 不支持 |
| 存储开销 | 相对较高（存储多份键值） | 相对较低（仅存储哈希值和指针） |
| 维护开销 | 插入/删除需维护树平衡 | 插入快，但扩容时需重哈希 |
结论与选型建议：
B+树是通用型冠军：其对范围查询和有序性的支持，使其适用于99%以上的数据库应用场景。这也是MySQL主流存储引擎默认选择它的原因。
哈希索引是特型专家：仅在纯等值查询、无范围需求、数据离散度高的极端场景下可作为备选。在MySQL中，通常不主动创建哈希索引，而是利用InnoDB的自适应哈希索引来自动优化热点查询。
理解“自适应哈希索引”：这是一个重要的扩展点。它不是由用户创建的，而是InnoDB的内部优化机制，用于加速缓冲池中热点数据页的访问，完美结合了B+树的持久化优势和哈希的内存检索速度。