在 MySQL 里常用的索引数据结构有 B + 树索引和哈希索引两种，我们来看下这两种索引数据结构的区别及其不同的应用建议。
二者区别
一个经典的 B + 树索引数据结构见下图：
B + 树是一个平衡的多叉树，从根节点到每个叶子节点的高度差不超过 1，而且同层级的节点之间由指针相互链接
在 B + 树上的常规检索，从根节点到叶子节点的查找效率基本相当，不会出现大幅波动，而且基于索引的顺序扫描时，也可以利用双向指针快速只有移动，效率非常高
因此，B + 树索引被广泛应用于数据库、文件系统等场景
而哈希索引的示意图则是这样的：
简单来说，哈希索引就是采用一定的 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 + 树索引就可以了。
【来源：https://python.iitter.com/other/155870.html，转载请注明】
若有收获，就点个赞吧
0 人点赞
