【转载】hash 索引和 B+树索引的区别

B+树索引

• B+树首先是有序结构，为了不至于树的高度太高，影响查找效率，在叶子节点上存储的不是单个数据，提高了查找效率； 为了更好的支持范围查询，B+树在叶子节点冗余了非叶子节点数据，为了支持翻页，叶子节点之间通过指针相连；

• B+树算法： 通过继承了B树的特征，通过非叶子节点查询叶子节点获取对应的 value，所有相邻的叶子节点包含非叶子节点，使用链表进行结合，有一定顺序排序，从而范围查询效率非常高。 缺点：因为有冗余节点数据，会比较占内存。

B+树索引特点

• 所有非叶子节点只存储关键字信息
• 所有具体数据都存在叶子节点中
• 所有叶子节点中包含了全部元素信息
• 所有叶子节点之间都有一个链指针
  

hash 索引

• hash 是 key,value 形式，通过一个散列函数，能够根据 key快速找到 value。

• 哈希索引由 hash 表构成，以 key、value 的形式存储。即采用一定的 hash 算法运算出的值作为 key，value 用来存储指针。检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需要一次 hash 算法即可立即定位到相应的位置，速度非常快。

• hash 冲突的产生：当数据表中的数据量非常大时，就可能产生 hash 冲突。（即不同的数据通过 hash 函数运算之后得出了相同的结果）。解决冲突的方法是，添加一个链表元素，把元素存在链表中（对比 key，相同则获取 value）。

B+树和 hash 索引的区别

• 如果是等值查询，那么 hash 索引有明显的优势，因为只需要经过一次算法即可找到相应的键值；当然了，这个键值是唯一的，如果不唯一，则需要先找到下标位置再链式查找。
• hash 索引无法支持范围查询，因为原先是有序的键值，但是经过 hash 算法后，有可能变成不连续的，就没有办法利用索引完成范围查询检索数据。
• 同样，hash 索引也没办法利用索引完成排序，以及 like xxx%这样的模糊查询（范围查询）。
• hash 索引也不支持多列联合索引的最左前缀匹配规则。
• B+树索引的关键字检索效率比较平均，不像B树那样波动幅度大，在有大量重复键的情况下，hash 索引的效率也是极低的，因为存在 hash 冲突问题。
  （等值查询 hash 索引效率高，但它无法进行范围查询、无法排序、无法按照 like%xxx% 查询、无法最左前缀匹配，而因存在 hash 冲突，查询效率也很低）