MySQL中的B+树索引和哈希索引

马谦马谦马谦 2020年2月16日20:26:01 发表评论
文章最后编辑于:2020-2-19 20:28:23

一、为什么要使用索引

索引是存储引擎用于快速找到记录的一种数据结构。索引对于数据库良好的性能十分关键,尤其是表中的数据量越来越大时,索引对性能的影响十分明显。

《高性能MySQL》中对索引的评价是:索引优化应该是对查询性能优化最有效的手段了,索引能够轻而易举将查询性能提高几个数量级。

以innodb为例,innodb中存储数据的基本元素是,页里面保存了许多数据记录,各个记录通过链表串联起来。一个innodb页的结构为:

MySQL中的B+树索引和哈希索引

innodb给每个页分配了16KB的大小,除了存储用户记录以外还有一些额外的字段没有展示出来。用户记录并不是一定装满了整个页,因此除了用户记录以外还有一部分未使用的空间,后续的新纪录可以继续插入到未使用空间中。

除了页内的记录用链表串起来了之外,每个页面也是通过链表连接起来的:

MySQL中的B+树索引和哈希索引

试想正常情况下,如果想要找到一条记录应该怎么找呢?首先要遍历所有的页面,然后遍历页面里面的记录,一条条记录对比,找到需要查询的记录。这样的话时间复杂度是O(N),N代表总的记录条数。

如果数据库中只有几条或者几十条记录,查起来或许还行。但是如果数据库有几千万甚至上亿条记录,这么查起来是什么样子?MySQL数据是写在磁盘上的,一次磁盘寻址所需要的时间是10ms,如果有1亿条记录,那么执行一次查询需要10亿毫秒,也就是1百万秒,算下来需要11.5天。这种级别的耗时是任何一个业务系统都无法忍受的。

而索引存在的意义就在于此,通过特定的结构来排布整个数据库,使得系统能在较快的时间内查询到记录。索引就像是一本书的目录,告诉你哪一章在哪一页,想看对应的章节直接放到对应页数就可以了。

一个最简单的索引思路是:把所有的记录排序,通过二分查找的方式来查找元素,查询的时间复杂度是O(logN)。这样的话1亿条记录,只需要20多次查询就可以了,算下来时间不到1秒,相比之前的11天已经不是一个数量级了。当然,实际的索引实现也不仅仅是二分查找这么简单。

最常用的索引有两种:

  1. B-Tree索引,基于B+树结构的索引。
  2. 哈希索引,基于哈希表实现的索引。

大部分时候,使用的都是B-Tree索引。

二、B-Tree索引

B-Tree索引是一种基于B+树结构的索引,B+树因为其独特的结构优势所以被广泛应用于索引中:

  1. 一个节点包含了多个数据域,适应于操作系统成块访问磁盘的特性,可以一次读取多个节点的数据。
  2. 相对于B树来说,B+树非叶子节点不包含任何数据,只包含子节点指针 ,因此一个节点所能指向的子节点个数更多,这样的话B+树会更矮,查询起来更高效。

一个B-Tree索引的结构为(橙色是数据域,绿色是子节点指针):

MySQL中的B+树索引和哈希索引

如果想要找到id等于32的记录,首先通过页1定位到子页10,然后继续查找页10,定位到页31,最终找到32。

可以看出,查找的效率是与B+树的层数相关的,树越高,查找效率越慢,树越低,查找效率越快。实际的应用中,一个页远远不止上面展示的3个记录项,按照一行记录100字节来算,一页数据(16K)至少可容纳1500个记录,那么1亿条记录只需要三层树(10^9<1500*1500*1500)。也就是说,1亿条数据最多执行三次IO就能定位到,可见其效率之高。

索引除了可以按值查找以外,还支持对ORDER BY子句的排序,只要排序字段也正确匹配上了索引就可以。

B-Tree支持的索引匹配条件:

  1. 全部匹配:支持同时匹配多个索引。
  2. 部分匹配:支持同时匹配多个索引中的部分索引。
  3. 匹配列前缀:对添加了索引的列,可以匹配其左前缀。例如匹配maqian中的前缀ma。
  4. 匹配范围:支持对索引列去范围值。

三、哈希索引

哈希索引是一种基于哈希表的索引结构,它是一种需要精确匹配才生效的索引结构。

实现原理:对索引列计算哈希值把记录映射到哈希槽中,然后指向对应记录行的地址。因此,在查询的时候只要正确匹配到索引列,就能在O(1)的时间复杂度内查到记录。

以下是一个哈希索引的示例,左边是哈希槽,右边是对应的数据列:

MySQL中的B+树索引和哈希索引

相比于B-Tree索引而言,哈希索引有不少的局限性:

  • 哈希索引不支持排序
  • 哈希索引不支持部分列索引查找
  • 哈希索引只支持等值查询,无法提供范围查询功能

哈希索引的查找效率是非常高的,大多数时候都能在O(1)的时间内找到记录,除非哈希冲突很高。

innodb中有一个内建功能叫自适应哈希,当存储引擎注意到有列频繁访问的时候,就会建立对应的哈希索引。这样,引擎就同时拥有了B-Tree索引和哈希索引,就能使用更加快速的查找。这是一个无需人工干预的自动行为。

哈希索引使用的场景

哈希索引常见的一种场景是针对长字符串查询的优化,例如数据库中保存了大量的URL信息,查询URL中不可能一个字符一个字符去搜索,这样效率太低。

这种情况就可以使用哈希索引:给所有的URL计算一个crc保存起来,然后对crc做哈希索引。查询的时候指定crc和url就能快速定位到记录了。如:

执行这条语句的时候,会先针对crc查找哈希索引,找出所有crc值等于xxxx的记录,过滤掉大多数不符合条件的记录。然后再根据后面的url信息详细匹配,这样查询效率就很高了。

四、索引的缺点

所有的优点是查询速率很快,但同时也有缺点。

索引的主要缺点是会导致插入和更新语句变慢,因为每次更新数据都要重新维护索引,索引越多,耗时越长。

同时,如果建立了不恰当的索引可能还会导致数据库性能更低,这个就依赖人工的操作了。

本文共执行65次查询,耗时0.569秒!
马谦马谦马谦

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: