MySQL – 索引本质、数据结构

时间:2021-7-5 作者:qvyue

本质

索引是排好序的数据结构,可以帮助MySQL高效获取数据。

索引的作用
MySQL - 索引本质、数据结构

考虑一张表设计和数据如上图,第一列是指数据行在磁盘的存放地址,
查询sql语句为

select *from t where t.Col2 = 89;

不用索引,需要从第一行开始遍历,查询每一行的Col2值是否等于89,需要查找6次。 而MySQL的数据是存放在磁盘的,每一行的查找相当于做了一次磁盘IO操作,磁盘的寻道时间大约为10ms,假如查找100次,就需要1s,效率非常低,更不用说成千上百万行记录的表。

给Col2加上索引,例如用上图的二叉树,树的节点是key,即Col2的值,value是索引所在行的磁盘文件地址(数据行在磁盘中存放不是连续的),那么从根节点查找Col2 = 89的值,只需要两次IO操作即可,比全表扫描快很多。

索引的优势
  • 提高数据检索的效率,降低数据库的IO成本,类似于书的目录(每次翻页就是IO操作)。
  • 通过索引列对数据进行排序,降低数据排序的成本,降低了CPU的消耗。
  1. 被索引的列会自动进行排序,包括【单列索引】和【组合索引】,只是组合索引的排序要复杂一些。
  2. 如果按照索引列的顺序进行排序,对应order by语句来说,效率就会提高很多。
索引的劣势:
  • 索引会占据磁盘空间
  • 索引虽然会提高查询效率,但是会降低更新表的效率。比如每次对表进行增删改操作,MySQL不仅要保存数据,还有保存或者更新对应的索引文件。

索引数据结构

  • 二叉树
  • 红黑树(平衡二叉树)
  • 有序数组
  • hash表
  • B树
  • B+树
为什么不用二叉树

考虑上图,对Col1进行索引,二叉树是长这样子

MySQL - 索引本质、数据结构

退化成了线性结构的链表,查询效率和全表扫描一样,复杂度是O(n)。
所以二叉树对于线性增长的字段是不适合做索引存储的。

为什么不用红黑树

对Col1进行索引,红黑树是长这样子

MySQL - 索引本质、数据结构

红黑树是采用二分法思维,除了具备二叉树的特点,最主要的特征是树的左右两个子树会自动平衡,在插入删除数据时通过左旋/右旋操作保持二叉树的平衡,不会出现左子树很高、右子树很矮的情况。

使用红黑树查找树查询的性能接近于二分查找法,查找时间复杂度是 O(log2n),是高效的数据结构。

存在问题:一张表动辄上千万的记录,即使红黑树具有自平衡功能,树也会很高,树高 = log2(记录数),
至少是20,假如元素落在叶子节点,就需要经历20次IO操作,还是有效率问题。

有序数组

对Col1进行索引,有序数组是长这样子

index 0 1 2 3 4 5
value 1 2 3 4 5 6

有序数组在等值查询和范围查询场景中的性能都非常优秀。
如果你要查 Col = 4,用二分法就可以快速得到,这个时间复杂度是 O(log(N))。
同时很显然,这个索引结构支持范围查询。

如果仅仅看查询效率,有序数组就是最好的数据结构了。但是,在需要更新数据的时候就麻烦了,你往中间插入一个记录就必须得挪动后面所有的记录,成本太高。

所以,有序数组索引只适用于静态存储引擎,比如你要保存的是 2017 年某个城市的所有人口信息,这类不会再修改的数据。

hash表

考虑对表的名字列用hash做索引,如下图

MySQL - 索引本质、数据结构
image.png

Hash表,以键值对的方式存储数据。我们使用Hash表存储表数据Key可以存储索引列,Value可以存储行记录或者行磁盘地址。每次插入数据,都对key用hash算法得出散列值,放入数组中。
当发生hash冲突时,采用开链表法解决,当链表太长会rehash,或者改用红黑树存储数据。

优点:

  • 在等值查询时效率很高,时间复杂度为O(1),比B+树索引高效;

缺点:

  • 仅满足等值查询,例如 “= “, “IN”,不支持范围快速查找,范围查找时还是只能通过扫描全表方式;
  • hash冲突问题。

所以,哈希表这种结构适用于只有等值查询的场景,比如 Redis,Memcache 及其他一些 NoSQL 引擎。
显然这种并不适合作为经常需要查找和范围查找的数据库索引使用。

B树

红黑树的缺点是大数据下树会变得很高,解决思路是横向扩展每层节点个数,每层存储更多的节点,就可以降低树的高度。 每个节点对应一块磁盘空间,分配更大的磁盘空间,以容纳更多的节点。
改造后的数据结构就是B树,每个大节点下可以存放多个数据。

MySQL - 索引本质、数据结构

B树特点:

  • 叶节点具有相同的深度,叶节点的指针为空
  • 所有索引元素不重复
  • 节点中的数据索引从左到右递增排列

相比二叉平衡查找树,在整个查找过程中,虽然数据的比较次数并没有明显减少,但是磁盘IO次数会大大减少。同时,由于比较是在内存中进行的,比较的耗时可以忽略不计。B树的高度一般2至3层就能满足大部分的应用场景,所以使用B树构建索引可以很好的提升查询的效率。

B树缺点:

  • B树不支持范围查询的快速查找,想要查找15和49之间的数据,查找到15之后,需要回到根节点重新遍历查找,需要从根节点进行多次遍历,查询效率有待提高。

  • 节点存储的是行记录,行的大小随着列数的增多,所占空间会变大。这时,一个页中可存储的数据量就会变少,树相应就会变高,磁盘IO次数就会变大。

B+树(多路平衡树)

MySQL实际上对B树再进行改造,得到B+树

MySQL - 索引本质、数据结构

B+树特点:

  • 非叶子节点不存储数据,只存储索引(冗余),可以放更多的索引
  • 叶子节点包含所有索引字段
  • 叶子节点用指针连接,提高区间访问性能。

假如要查找值为30的行,数据查找过程如下:

  • 先把根节点的索引全部load进内存,因为数据是已经有序的,可以使用二分查找,定位下一级索引位置。
  • 定位到第二级索引后,也是load进内存,定位第三级索引。
  • 定位到第三级索引,继续二分查找,找到索引位置,并取出索引对应的行数据。
    过程只需要三次IO操作,约等于30ms。

假如要查找18 ~ 50的行,数据查找过程如下:

  • 定位到value为18的索引,需要三次IO操作;
  • 从18的索引开始,依次读取索引下一个索引,直到>50为止,再需要两次IO操作。

B树与B+树两个区别:

  • B树:非叶子节点和叶子节点都会存储数据。
  • B+树:只有叶子节点才会存储数据,非叶子节点只存储键值,所以B+树一个页能放入更多的索引,同样的数据量,树高更低。叶子节点之间使用双向指针连接,最底层的叶子节点形成了一个双向有序链表,方便进行范围搜索。

MySql默认一个页的长度为16KB,即分配给B+树每个节点大小。

mysql> show global status like 'innodb_page_size';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| Innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.01 sec)

假如索引字段是BigInt,占8B,索引存储的值即磁盘地址长度占6B,加起来就是14B,页大小为16KB情况下,每页可以放 16KB / 14B = 1170个索引,假如叶节点,即存放数据的节点,每行数据大小为1KB,即每页可以放16个数据行,那么树高为3的B+树,可以放满 1170 * 1170 * 16 = 2000w个索引和数据,千万级别的数据依然很高。

而且MySQL底层,实际上会把所有非叶子结点放到内存中,因为非叶子节点内存占用少,例如树高为3的B+树,放满索引后,索引大小为 1170 * 1170 * 14B = 18.2MB,所以查找数据只需要1次IO操作,效率高。

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。