MySQL 索引结构 hash 有序数组
wangshuangbao 2020-07-05
MySQL 索引结构 hash 有序数组
除了最常见的树形索引结构，Hash索引也有它的独到之处。
?
Hash算法
Hash本身是一种函数，又被称为散列函数。
它的思路很简单：将key放在数组里，用一个hash算法把不同的key转换成一个确定的value，然后放在这个数组的指定位置
相同的输入永远可以得到相同的输出
具体的算法有MD5、SHA1、SHA2、SHA3
Hash冲突：不同的key得到了相同的value
当出现Hash冲突，可以在冲突发生的位置跟一个链表
?
Hash索引
索引使用的数据结构的特性会让索引也具有不同的特性：
Hash索引只适用于等值查询的场景，区间查询速度很慢
因为经过hash函数处理后，即便是原本有序的输入，最后存放的位置也会变为无序的。
检索速度很快
索引检索一次到位，而不需要想B+树那样从根节点访问到叶子节点。不过在有大量重复值得情况下，hash索引的效率极低，因为要频发地处理Hash冲突。
无法完成排序，模糊查询
因为它们本质上是范围查询
不支持多列联合索引的最左匹配原则
对于Hash索引的联合索引，是将联合索引字段值相捆绑然后计算Hash值的，无法利用对单一字段的Hash值
Hash索引的用途：
Hash索引更多地使用在键值型的数据库中，比如Redis
MySQL的Memory存储引擎支持Hash存储
如果我们需要用到查询的临时表时，就可以选择 Memory 存储引擎，把某个字段设置为 Hash 索引，比如字符串类型的字段，进行 Hash 计算之后长度可以缩短到几个字节。当字段的重复度低，而且经常需要进行等值查询的时候，采用 Hash 索引是个不错的选择
InnoDB自适应Hash索引
当某个索引值使用非常频繁的时候，它会在 B+ 树索引的基础上再创建一个 Hash 索引，这样让 B+ 树也具备了 Hash 索引的优点。
?
有序数组
如果我们使用有序数据作为索引结构的话，那么
- 等值查询和范围查询的性能都十分优秀
- 但是插入和删除的成本太大
因此有序数组的结构只适合静态存储引擎，如果我们要存储以某种有序编号为序的不轻易增删的历史数据，我们可以使用有序数组作为索引结构。
?
