全面透彻,深刻理解 MySQL 索引

小七学习网,助您升职加薪,遇问题可联系:客服微信【1601371900】 备注:来自网站

对于 MySQL 索引,相信每位后端同学日常工作中经常会用到,但是对其索引原理,却可能未曾真正深入了解。B- 树和 B+ 树是 MySQL 索引使用的数据结构,对于索引优化和原理理解都非常重要,下面就…

对于 MySQL 索引,相信每位后端同学日常工作中经常会用到,但是对其索引原理,却可能未曾真正深入了解。B- 树和 B+ 树是 MySQL 索引使用的数据结构,对于索引优化和原理理解都非常重要,下面就揭开 B- 树和 B+ 树的神秘面纱,让大家在面试的时候碰到这个知识点一往无前,不再成为你前进的羁绊!

在本文中,会讲到如下内容:

  1. MySQL 查询耗时分析,抓性能优化核心问题点
  2. 常见用于查询的数据结构,性能优劣对比
  3. B-Tree 与 B+Tree 如何选择,结合场景来做分析更靠谱
  4. InnoDB 中的索引介绍,知己知彼,应用得心应手

适合人群:软件研发



一、查询耗时分析

我们首先进行下查询耗时分析,抓性能优化核心问题点。

1.1 记录读取顺序

MYSQL 维护着自己的缓存空间,如果要读取一条记录,根据优先顺序,路径如下:

缓存区 => 磁盘缓存区 => 磁盘

1.1.1 缓存区读取

这是成本最低的方式,可以直接被 CPU 使用,不涉及磁盘 IO,可以考虑 IO 时间为 0。

1.1.2 从磁盘缓存区读取

如果磁盘缓存区有需要的记录,则只需要直接读出,传输时间考虑为 1ms。

1.1.3 从磁盘读取

由于 SSD 比较贵,常用的还是机械硬盘,对于机械硬盘,要读取指定地址的数据,是需要经过寻道的,机械臂需要先移动到指定位置,因此无论读取多少数据,准备工作都会耗费一段时间。整个 IO 流程包括:排队等待 => 寻道 => 半圈旋转 => 传输。

在这里插入图片描述

一次随机读取中,有 90% 的时间都花费在排队和准备工作,真正的传输时间只有 1ms,但总 I/O 时间却为 10ms。

当随机读取 10 页,就需要 10*10=100ms,但如果是顺序读,对于传输速度为 40MB/s 的硬盘,读取一个 4kb 的页仅需要 0.1ms,即使顺序读取 100 页,也只需要 1 页随机读 99 页顺序读,也就是 10ms+9.9ms=19.9ms。

速度差距几十倍,这也是为何我们想要尽量保证需要读取的数据都在物理上排列在一起,因为这样就可以顺序读取多个页,而不需要进行多次随机读取。

这样做的理论依据是计算机科学中著名的局部性原理:

当一个数据被用到时,其附近的数据也通常会马上被使用。

通过以上分析可知:对于数据读取速度的优化,主要就是需要降低 IO 时间,而降低 IO 时间的关键,就在于减少随机读次数以及读取更少的数据

二、常见查询数据结构对比

在此梳理常见用于查询的数据结构,性能优劣大比拼。

2.1 二叉查找树

二叉查找树(Binary Search Tree),亦称二叉搜索树。是数据结构中的一类。在一般情况下,查询效率比链表结构要高。

如图所示:

在这里插入图片描述

查询数据的效率不稳定,若树左右比较平衡的时,最差情况为 O(logN),如果插入数据是有序的,退化为了链表,查询时间变成了 O(N)。

数据量大的情况下,会导致树的高度变高,如果每个节点对应磁盘的一个块来存储一条数据,需 IO 次数大幅增加,显然用此结构来存储数据是不可取的。

2.2 平衡二叉树

平衡二叉树(Balanced Binary Tree) 指的是棵空树或它的左右两个子树的高度差的绝对值不超过 1,并且左右两个子树都是一棵平衡二叉树。

如图所示:

在这里插入图片描述

如果数据都存储在内存中,采用 AVL 树来存储,还是可以的,查询效率非常高。不过我们的数据是存在磁盘中,用过采用这种结构,每个节点对应一个磁盘块,数据量大的时候,也会和二叉树一样,会导致树的高度变高,这样逻辑上很近的节点实际可能非常远,无法很好的利用磁盘预读(局部性原理),会增加 IO 次数,显然用这种结构存储数据也是不可取的。

2.3 B-树

B 树(英语:B-tree),这里的 B 表示 balance( 平衡的意思),是一种自平衡的树,能够保持数据有序,B-树允许每个节点有更多的子节点。

如图所示: 在这里插入图片描述

B-树不利于范围查找,范围查找也是我们经常用到的,所以 B-树也不太适合在磁盘中存储需要检索的数据。

2.4 B+ 树

B+ 树是 B- 树的一个升级版,也是一种多路搜索树,相对于 B 树来说 B+ 树更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。B+ 树元素自底向上插入,这与二叉树恰好相反。

如图所示:

在这里插入图片描述

如上图所示,每个节点占用一个盘块的磁盘空间,一个节点上有两个升序排序的关键字和三个指向子树根节点的指针,指针存储的是子节点所在磁盘块的地址。

2.5 B-Tree vs B+Tree

对于 B-Tree 和 B+Tree,我们该如何选择呢?结合场景来做分析更靠谱。

让我们来想想平时的高频查询场景吧,大概存在如下几种:

  1. 按照 id 查询唯一一条记录
  2. 查找某个范围的所有记录

接下来,just do it!

2.5.1 场景:按照 id 查询唯一一条记录

在这里插入图片描述

B-树 模拟查找关键字 20 的过程(3 次 io 操作+内存中二分法)):

  1. 根据根节点找到磁盘块 1,读入内存。【磁盘 I/O 操作第 1 次】
  2. 比较关键字 20 在区间(12,32),找到磁盘块 1 的指针 P2
  3. 根据 P2 指针找到磁盘块 3,读入内存。【磁盘 I/O 操作第 2 次】
  4. 比较关键字 20 在区间(15,26),找到磁盘块 3 的指针 P2
  5. 根据 P2 指针找到磁盘块 7,读入内存。【磁盘 I/O 操作第 3 次】
  6. 在磁盘块 7 中的关键字列表中找到关键字 20

如果我们是关键字 15 的话 ,那就是 2 次 io 操作+内存中二分法。但是如果是 B+ 树,就只能通读到底了。

2.5.2 场景:查找某个范围的所有记录

在这里插入图片描述

假如 B- 树要查找 [8,52] 区间的数据,需要访问 8 个磁盘块(1/2/6/3/7/8/4/9),IO 次数又上去了。

2.5.3 小结

故 B-Tree vs B+Tree 两种在索引的区别如下:

1. B-Tree 查找某个关键字的效率更高

B-Tree 因为非叶子结点也保存具体数据,所以在查找某个关键字的时候找到即可返回。而 B+Tree 所有的数据都在叶子结点,每次查找都得到叶子结点。所以在同样高度的 B-Tree 和 B+Tree 中,B-Tree 查找某个关键字的效率更高。

2. B-Tree 不利于范围查询

由于 B+Tree 所有的数据都在叶子结点,并且结点之间有指针连接,在找大于某个关键字或者小于某个关键字的数据的时候,B+Tree 只需要找到该关键字然后沿着链表遍历就可以了,而 B-Tree 还需要遍历该关键字结点的根结点去搜索。

3. B-Tree 的深度会更大

由于 B-Tree 的每个结点(这里的结点可以理解为一个数据页)都存储主键+实际数据,而 B+Tree 非叶子结点只存储关键字信息,而每个页的大小有限是有限的,所以同一页能存储的 B-Tree 的数据会比 B+Tree 存储的更少。这样同样总量的数据,B-Tree 的深度会更大,增大查询时的磁盘 I/O 次数,进而影响查询效率。

4. B+树的磁盘读写代价更低

B+树的内部节点并没有指向关键字具体信息的指针,因此其内部节点相对 B 树更小,如果把所有同一内部节点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多,一次性读入内存的需要查找的关键字也就越多,相对 IO 读写次数就降低了。

5. B+树的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

三、InnoDB 中的索引

InnoDB 中的索引介绍,知己知彼,应用起来得心应手。

3.1 InnoDB 索引实现

InnoDB 数据页有 7 个组成部分,各个数据页可以组成一个双向链表。而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表,每个数据页都会为存储在它里边儿的记录生成一个页目录。在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽,然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

页和记录的关系示意图如下: 在这里插入图片描述

索引同样存储在数据页中,只不过目录项中的两个列是主键和页号。

那 InnoDB 怎么区分一条记录是普通的用户记录还是目录项记录呢?是根据记录头信息里的 record_type 属性,它的各个取值代表的意思如下:

0:普通的用户记录

1:目录项记录

2:最小记录

3:最大记录

3.2 查找步骤

整体结构如下: 在这里插入图片描述

现在如果我们想根据主键值查找一条用户记录大致需要 3 个步骤,以查找主键值为 20 的记录为例:

1、确定目录项记录页。

2、通过目录项记录页确定用户记录真实所在的页。

3、在真实存储用户记录的页中定位到具体的记录。

四、InnoDB 中的索引分类

InnoDB 中的索引类别介绍,明确后期应用注意事项。

4.1 聚簇索引

上边介绍的 B+树索引。它有两个特点:

1、根据记录主键值的大小进行记录和页的排序

这包括三个方面的含义:

  • 页内的记录是按照主键的大小顺序排成一个单向链表。
  • 各个存放用户记录的页也是根据主键大小顺序排成一个双向链表。
  • 存放目录项记录的页分为不同的

层次,在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。

2、B+树的叶子节点存储的是完整的用户记录

我们把具有这两种特性的 B+树称为聚簇索引,所有完整的用户记录都存放在这个聚簇索引的叶子节点处。

4.2 二级索引

上边介绍的聚簇索引只能在搜索条件是主键值时才能发挥作用,因为 B+树中的数据都是按照主键进行排序的。

Q1:那如果我们想以别的列作为搜索条件该咋办呢?

Q2:难道只能从头到尾沿着链表依次遍历记录么?

我们可以多建几棵 B+树,不同的 B+树中的数据采用不同的排序规则。比方说我们用 c2 列的大小作为数据页、页中记录的排序规则,再建一棵 B+树,效果如下图所示: 在这里插入图片描述

但是但是这个 B+树的叶子节点中的记录只存储了 c2 和 c1(也就是主键)两个列,所以我们必须再根据主键值去聚簇索引中再查找一遍完整的用户记录。

由于主键值具有唯一性,二级索引不具有唯一性,那么 新的问题来了: 在这里插入图片描述

在上图中,如果我们想新插入一行记录,其中 c1、c2、c3 的值分别是:9、1、’c’。

那么在修改这个为 c2 列建立的二级索引对应的 B+树时便碰到了个大问题:

由于页 3 中存储的目录项记录是由 c2 列 + 页号的值构成的,页 3 中的两条目录项记录对应的 c2 列的值都是 1,而我们新插入的这条记录的 c2 列的值也是 1,那我们这条新插入的记录到底应该放到页 4 中,还是应该放到页 5 中啊?懵逼了。

为了让新插入记录能找到自己在那个页里,我们需要保证在 B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。

所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的:

1、索引列的值

2、主键值

3、页号

我们为 c2 列建立二级索引后的示意图实际上应该是这样子的:

4.3 联合索引

我们可以同时以多个列的大小作为排序规则,也就是同时为多个列建立索引,比方说我们想让 B+树按照 c2 和 c3 列的大小进行排序,这个包含两层含义:

1、先把各个记录和页按照 c2 列进行排序;

2、在记录的 c2 列相同的情况下,采用 c3 列进行排序。

五、总结

MySQL 普遍采用 B+Tree 实现,索引本身很大,不可能全部存储内存,因此需要以索引文件的形式存储磁盘。相对于内存读取,I/O 存取的消耗要高几个数量级,由于 MySQL 数据存储保存在磁盘中,所以在查询时磁盘 I/O 是其主要查询性能瓶颈,而使用索引就可以减少磁盘 I/O

索引的原理其实是不断的缩小查找范围, 就如我们平时用字典查单词一样,先找首字母缩小范围,再第二个字母等等。

对于 B-树、B+树而言,当高固定情况下,宽度越大索引性能越好。

小七学习网,助您升职加薪,遇问题可联系:客服微信【1601371900】 备注:来自网站

免责声明: 1、本站信息来自网络,版权争议与本站无关 2、本站所有主题由该帖子作者发表,该帖子作者与本站享有帖子相关版权 3、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和本站的同意 4、本帖部分内容转载自其它媒体,但并不代表本站赞同其观点和对其真实性负责 5、用户所发布的一切软件的解密分析文章仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。 6、您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。 7、请支持正版软件、得到更好的正版服务。 8、如有侵权请立即告知本站(邮箱:1099252741@qq.com,备用微信:1099252741),本站将及时予与删除 9、本站所发布的一切破解补丁、注册机和注册信息及软件的解密分析文章和视频仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。如有侵权请邮件与我们联系处理。