25丨Hash索引的底层原理是什么？

作者回复: 我们先回顾下B+树索引和Hash索引： B+树索引是MySQL的默认索引机制，也是大部分 因为可以使用范围搜索，可以很容易对数据进行排序操作，在联合索引中也可以利用部分索引建进行查询。这些情况下，我们都没法使用Hash索引，是因为Hash索引仅能满足=, <>, IN查询，不能使用范围查询，同时因为数据的存储是没有顺序的，所以在ORDER BY的情况下，还需要对数据重新进行排序。而对于联合索引的情况，Hash值是针对联合索引建合并后一起来计算Hash值，因此无法对单独的一个键或者几个索引键进行查询。 好了，默认使用B+树作为索引是因为B+树存在着以上的优点，那为什么还需要自适当Hash索引呢？这里，需要了解Hash索引的特点，因为Hash索引结构的特点，导致它的检索数据效率非常高，通常只需要O(1)的复杂度，也就是一次就可以完成数据的检索。虽然Hash索引的使用场景有很多限制，但是优点也很明显，所以MySQL提供了一个自适当Hash索引的功能（Adaptive Hash index）。注意，这里的自适应指的是不需要人工来制定，而是系统根据情况来自动完成的。 那什么情况下才会使用自适应Hash索引呢？如果某个数据经常会访问到，当满足一定条件的时候，就会将这个数据页的地址存放到Hash表中。这样下次查询的时候，就可以直接找到这个页面的所在位置。需要说明的是： 1）自适应哈希索引只保存热数据（经常被使用到的数据），并非全表数据。因此数据量并不会很大，可以让自适应Hash放到缓冲池中，也就是InnoDB buffer pool，进一步提升查找效率。 2）InnoDB中的自适应Hash相当于是“索引的索引”，采用Hash索引存储的是B+树索引中的页面的地址。这也就是为什么可以称自适应Hash为索引的索引。 采用自适应Hash索引目的是可以根据SQL的查询条件加速定位到叶子节点，特别是当B+树比较深的时候，通过自适应Hash索引可以提高数据的检索效率。 3）自适应Hash采用Hash函数映射到一个哈希表中，所以对于字典类型的数据查找非常方便 哈希表是数组+链表的形式。通过Hash函数可以计算索引键值所对应的bucket（桶）的位置，如果产生Hash冲突，如果产生哈希冲突，就需要遍历链表来解决。 4）是否开启了自适应Hash，可以通过innodb_adaptive_hash_index变量来查看，比如：mysql> show variables like '%adaptive_hash_index'; 所以，总结下InnoDB本身不支持Hash，但是提供自适应Hash索引，不需要用户来操作，而是存储引擎自动完成的。自适应Hash也是InnoDB三大关键特性之一，另外两个分别是插入缓冲（Insert Buffer）和二次写(Double Write)。

作者回复: 对的

作者回复: 因为我们要找的是某个元素的值，比如我添加的元素是1，3,5,7...99 一共50个元素，如果我想要找7这个元素，你会用7作为下标进行检索，还是将7作为元素值进行查找呢？ 这里就需要检索具体的数值，对于数组来说下标是自动分配的，所以我们需要遍历数组来找到某个数值。 而对于字典来说，我们就可以创建索引了

作者回复: 多谢分享 我行我素同学

作者回复: 在MySQL的InnoDB和如果使用的是MySQL的话，我们需要了解下MySQL的存储引擎都支持哪些索引结构，可以参考https://dev.mysql.com/doc/refman/8.0/en/create-index.html） 针对MySQL 默认的存储引擎InnoDB，或者使用MyISAM存储引擎都会默认使用的是B+树来进行存储，无法使用Hash索引。InnoDB提供的自适应Hash是不需要手动指定的。如果是Memory/Heap，或者是NDB存储引擎，是可以进行选择的（Hash还是B+树）。

作者回复: 对的，like 后面需要有内容（不能直接是通配符），比如 'xx%' 是OK的

作者回复: 对的 所以对于一般需求来说，B+树在数据库应用的场景更多，Hash适用一些特殊的需求，比如文件校验，密码学等

作者回复: 感谢提问，一个数组如果有n个元素，需要遍历完所有的元素才能找到某个元素，所以是O(n)，如果是O(1)就是不需要遍历，直接找到那个元素

作者回复: 对的

作者回复: 采用bucket分桶的概念都是一样的