哈希索引和B+树索引的区别 (Hash索引 和 B+tree索引 区别)

前段时间被问到Hash索引和B+tree索引的区别，一时间没回答上来，这边做下记录。

索引

       索引是对数据库表中一列或多列的值进行处理后的一种结构，使用索引可快速访问数据库表中的特定信息。本文主要对Hash索引和B+tree索引的区别做说明，如果不了解B+tree 索引的老铁可以先了解下B+tree，后面我会再补一个B+tree 索引的内容。

Hash索引概念

       说到Hash，老铁们很容易联想到HashMap，没错，Hash索引的结构和HashMap相类似，键值 key 通过 Hash 映射找到桶 bucket。在这里桶（bucket）指的是一个能存储一条或多条记录的存储单位。一个桶的结构包含了一个内存指针数组，桶中的每行数据都会指向下一行，形成链表结构，当遇到 Hash 冲突时，会在桶中进行键值的查找。

       InnoDB中采用除法散列函数(取余法)，冲突机制采用链接法

Hash索引和B+tree索引查询效率

        采用 Hash 进行检索效率非常高，基本上一次检索就可以找到数据，而 B+ 树需要自顶向下依次查找，多次访问节点才能找到数据，中间需要多次 I/O 操作，理论上来说 Hash 比 B+ tree更快。下图是引用网上的Hash索引图片和 B+tree 索引图片，便于直观的理解2种索引结构。

1、Hash索引图片

                                                                         图1、Hash索引结构图

2、B+tree索引图片

                                                                       图2、B+tree 索引结构图 

Hash索引和B+tree索引的区别

      1、在查询速度上，如果是等值查询，那么Hash索引明显有绝对优势，因为只需要经过一次 Hash 算法即可找到相应的键值，复杂度为O(1)；当然了，这个前提是键值都是唯一的。如果键值不是唯一(或存在Hash冲突)，就需要先找到该键所在位置，然后再根据链表往后扫描，直到找到相应的数据，这时候复杂度会变成O(n)，降低了Hash索引的查找效率。所以，Hash 索引通常不会用到重复值多的列上，比如列为性别、年龄的情况等（当然B+tree索引也不适合这种离散型低的字段上）；

      2、Hash 索引是无序的，如果是范围查询检索，这时候 Hash 索引就无法起到作用，即使原先是有序的键值，经过 Hash 算法后，也会变成不连续的了。因此

           ①、Hash 索引只支持等值比较查询、无法索成范围查询检索，B+tree索引的叶子节点形成有序链表，便于范围查询。

           ②、Hash 索引无法做 like ‘xxx%’ 这样的部分模糊查询，因为需要对 完整 key 做 Hash 计算，定位bucket。而 B+tree 索引具有最左前缀匹配，可以进行部分模糊查询。

           ③、Hash索引中存放的是经过Hash计算之后的Hash值，而且Hash值的大小关系并不一定和Hash运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算。B+tree 索引的叶子节点形成有序链表，可用于排序。

      3、Hash 索引不支持多列联合索引，对于联合索引来说，Hash 索引在计算 Hash 值的时候是将索引键合并后再一起计算 Hash 值，不会针对每个索引单独计算 Hash 值。因此如果用到联合索引的一个或者几个索引时，联合索引无法被利用；

      4、因为存在哈希碰撞问题，在有大量重复键值情况下，哈希索引的效率极低。B+tree 所有查询都要找到叶子节点，性能稳定；

场景区分

      1、大多数场景下，都会有组合查询，范围查询、排序、分组、模糊查询等查询特征，Hash 索引无法满足要求，建议数据库使用B+树索引。

      2、在离散型高，数据基数大，且等值查询时候，Hash索引有优势。

 

 

本文地址：https://blog.csdn.net/weixin_43841693/article/details/107301253