MySQL 索引结构 hash 有序数组

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

?

有序数组

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

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

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

?

相关推荐