MySQL面试：B+树索引和哈希索引的区别

た入场券 2022-09-16 11:11 34阅读 0赞

在MySQL里常用的索引数据结构有B+树索引和哈希索引两种，我们来看下这两种索引数据结构的区别及其不同的应用建议。

# 二者区别 #

一个经典的B+树索引数据结构见下图：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16]

*  B+树是一个平衡的多叉树，从根节点到每个叶子节点的高度差不超过1，而且同层级的节点之间由指针相互链接
 *  在B+树上的常规检索，从根节点到叶子节点的查找效率基本相当，不会出现大幅波动，而且基于索引的顺序扫描时，也可以利用双向指针快速只有移动，效率非常高
 *  因此，B+树索引被广泛应用于数据库、文件系统等场景

而哈希索引的示意图则是这样的：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_18_color_FFFFFF_t_70_g_se_x_16]  
简单来说，哈希索引就是采用一定的hash算法，把键值换算成新的hash值，检索时不需要类似的B+那样从根节点到叶子节点逐级查找，只需要一次hash算法就可以立即定位到相应位置，速度非常快。

从上面来看，B+树索引和Hash索引的区别是：

*  如果是等值查找，那么hash索引具有明显优势。因为只需要经过一次算法就可以找到响应的减值；当然，这个前提是，减值都是唯一的。如果减值不唯一，那么就需要先找到键值所在的位置，然后再扫描链表，知道直到对应的数据
 *  如果是范围查找，hash索引也无法作用，因为原先是有序的键值，经过hash算法之后，有可能变得不连续了，就没有办法利用索引完成范围hash查找检索了
 *  同理，hash索引也没有版本利用索引完成排序，以及like ‘xxx%’ 这样的部分模糊查询（这种部分模糊查询，其实本质上也是范围查询）；
 *  hash索引也不支持多列联合索引的最左匹配原则
 *  B+树索引的关键字检索效率比较平均，不像B树那样波动幅度大，在有大量重复键值情况下，哈希索引的效率也是极低的，因为存在所谓的哈希碰撞问题。

总的来说： hash索引能以O(1)时间进行查找，但是失去了有效性。无法用于排序和分组，只支持精确查找，无法用于部分查找和范围查找

# 后记 #

在MySQL中，只有Heap/Memory引擎表才能显式的支持hash索引（NDB也支持，但这个不常用）。InnoDB引引擎的自适应hash引擎不再此列，因为这不是创建索引时可以指定的。

> InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在B+树索引之上再创建一个hash索引，这样就让B+Tree索引具有hash索引的一些优点。

还要注意到：Heap/Memory引擎表在MySQL实例重启后，数据就会丢失。

通常，B+树索引适合绝大多数场景，

*  在Heap表中，如果存储的数据重复度很低(也就是说技术很大)，对该列数据以等值查询为主，没有范围查找、排序时，特别适合采用哈希索引。例如这种SQL：SELECT … FROM t WHERE C1 = ?; — 仅等值查询
 *  在大多数场景下，都会有范围查询、排序、分组等查询特征，用B+树索引就可以了。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/16b81d34d42d42d783b1630ff6fcf8a0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f26521a146074892b198e739ec1dda92.png