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

索引介绍

索引是一种特殊的数据库结构，被设计用来快速查询数据库表中的特定记录。索引有多种类型，就像字典有拼音查找和偏旁查找一样都是为了提高检索效率。 MySQL中最常见的索引类型有B+树索引 和 哈希索引，下面来简单介绍一下这两种索引类型有哪些差别和优劣。

B+树索引

B+树索引是一种多路径的平衡搜索树，具有如下特点：

• 1.非叶子节点不保存数据，只保存索引值
• 2.叶子节点保存所有的索引值和数据
• 3.同级节点通过指针自小而大顺序链接
• 4.节点内的数据也是自小而大顺序存放
• 5.叶子节点拥有父节点的所有信息

结构如下图：

优点

• 如图可知，由于数据顺序存放，所以无论是区间还是顺序扫描都更快。
• 非叶子节点不存储数据，因此几乎都能放在内存中，搜索效率更高
• 单节点中可存储的数据更多，平均扫描I/O请求树更少
• 平均查询效率稳定（每次查询都从根结点到叶子结点，查询路径长度相同）

缺点

• 新增数据不是按顺序递增时，索引树需要重新排列，容易造成碎片和页分裂情况。

哈希索引

哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快，具有如下特点：

• 1.哈希索引建立在哈希表的基础上
• 2.对于每个值，需要先计算出对应的哈希码（Hash Code），不同值的哈希码唯一
• 3.把哈希码保存在哈希表中，同时哈希表也保存指向对应每行记录的指针

结构如下图：

优点

• 大量唯一等值查询时，哈希索引效率通常更高。

缺点

• 哈希索引对于范围查询和模糊匹配查询显得无能为力。
• 哈希索引不支持排序操作，对于多列联合索引的最左匹配规则也不支持。
• 哈希索引不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。
• 访问哈希索引的数据非常快，除非有很多哈希冲突（不同的索引列值却有相同的哈希值）当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。