关于哈希索引和B+树索引

前言

Mysql中有哈希索引和B+树索引这两种数据结构,在此查找相关资料比对两者的优缺点。

B+树索引

B+树结构

InnoDB使用的索引是以B+树为数据结构的聚簇索引。

聚簇索引的优点:

1.当你需要取出一定范围内的数据时,用聚簇索引也比用非聚簇索引好。
2.当通过聚簇索引查找目标数据时理论上比非聚簇索引要快,因为非聚簇索引定位到对应主键时还要多一次目标记录寻址,即多一次I/O。

聚簇索引的缺点:

1.插入速度严重依赖于插入顺序,按照主键的顺序插入是最快的方式,否则将会出现页分裂,严重影响性能。因此,对于InnoDB表,我们一般都会定义一个自增的ID列为主键。
2.更新主键的代价很高,因为将会导致被更新的行移动。因此,对于InnoDB表,我们一般定义主键为不可更新。
3.二级索引访问需要两次索引查找,第一次找到主键值,第二次根据主键值找到行数据。
二级索引的叶节点存储的是主键值,而不是行指针(非聚簇索引存储的是指针或者说是地址),这是为了减少当出现行移动或数据页分裂时二级索引的维护工作,但会让二级索引占用更多的空间。
4.采用聚簇索引插入新值比采用非聚簇索引插入新值的速度要慢很多,因为插入要保证主键不能重复,判断主键不能重复,采用的方式在不同的索引下面会有很大的性能差距,聚簇索引遍历所有的叶子节点,非聚簇索引也判断所有的叶子节点,但是聚簇索引的叶子节点除了带有主键还有记录值,记录的大小往往比主键要大的多。这样就会导致聚簇索引在判定新记录携带的主键是否重复时进行昂贵的I/O代价。

哈希索引

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

  1. 如果是等值查询,那么哈希索引明显有绝对优势,因为只需要经过一次算法即可找到相应的键值;当然了,这个前提是,键值都是唯一的。如果键值不是唯一的,就需要先找到该键所在位置,然后再根据链表往后扫描,直到找到相应的数据; 从示意图中也能看到,如果是范围查询检索,这时候哈希索引就毫无用武之地了,因为原先是有序的键值,经过哈希算法后,有可能变成不连续的了,就没办法再利用索引完成范围查询检索;
  2. 同理,哈希索引也没办法利用索引完成排序,以及like ‘xxx%’ 这样的部分模糊查询(这种部分模糊查询,其实本质上也是范围查询); 哈希索引也不支持多列联合索引的最左匹配规则;
  3. B+树索引的关键字检索效率比较平均,不像B树那样波动幅度大,在有大量重复键值情况下,哈希索引的效率也是极低的,因为存在所谓的哈希碰撞问题。

适用场景:如果存储的数据重复度很低(也就是说基数很大),对该列数据以等值查询为主,没有范围查询、没有排序的时候,特别适合采用哈希索引

注意:在MySQL中,只有HEAP/MEMORY引擎表才能显式支持哈希索引,InnoDB引擎的自适应哈希索引(adaptive hash index)不可指定使用哈希索引

Reference

https://blog.csdn.net/sunsgne_ac/article/details/79374053

www.jianshu.com/p/e1dce41a6b2b