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 索引的优点。

有序数组

如果我们使用有序数据作为索引结构的话，那么

• 等值查询和范围查询的性能都十分优秀
• 但是插入和删除的成本太大

因此有序数组的结构只适合静态存储引擎，如果我们要存储以某种有序编号为序的不轻易增删的历史数据，我们可以使用有序数组作为索引结构。