vlambda博客
学习文章列表

分库分表实战(第5期):寻根问底 — MySQL索引是如何形成的?

「 关注“石杉的架构笔记”,大厂架构经验倾囊相授 

帮您解忧,儒猿特别打造 “跳槽训练专栏系列”

   |    
分库分表实战(第5期):寻根问底 — MySQL索引是如何形成的?
分库分表实战(第5期):寻根问底 — MySQL索引是如何形成的?
<<  滑动查看更多专栏  >>


问题分析:为什么查询变慢呢?



接上期,我们知道了MySQL查询的全过程,也知道了整个过程的瓶颈在于磁盘IO,那怎么降低磁盘IO次数呢?

答案就是索引。

正确的使用索引,我们就能有效的把磁盘IO的次数降到常数级,这样查询速度将会变得非常快,接下来让我们深入了解下MySQL的索引。

无索引时,为什么查询会很慢呢?



在磁盘中,MYSQL存放数据的基本单位是数据页,数据是放在数据页中的,每个数据页中都有很多的数据行,如下图:

分库分表实战(第5期):寻根问底 — MySQL索引是如何形成的?

可以看到,在数据页的数据区中存放着很多数据行,这些数据行就对应数据表中的一行行数据,它们都是通过单向链表方式连接组合起来的。

而多个数据页之间又是通过双向链表的方式连接起来的,如下图:

分库分表实战(第5期):寻根问底 — MySQL索引是如何形成的?

而一个数据页的大小默认为16KB,16KB的大小肯定是不可能放得下一整张表的数据的,所以MYSQL表中的数据,比如我们的订单表中的订单数据,会通过这样双向链表的结构放在多个数据页中。

如果我们要查询一条数据的话,就要沿着双向链表一个个去寻找。比如,我们要查询主键为1的那条数据,我们可以从数据页1开始查询。

首先,将数据页1从磁盘中加载到MYSQL内存中,如果发现数据页1中没有找到我们想要的那条数据,我们就要沿着双向链表一直寻找下去。

最糟糕的情况,就是我们沿着数据页1、数据页2、一直到最后,我们在最后一个数据页100中才找到我们想要的那条数据,但在这之前,我们得要把数据页1一直到数据页100,将这100个数据页通过磁盘IO加载到内存中,相当于是全表扫描了。

就算MYSQL中有预读机制存在,可能会预先发生几次磁盘IO,提前加载一些数据页到内存中,但这100个数据页同样至少会导致几十次磁盘IO了,而磁盘IO这个过程是很耗费性能的。

MYSQL的索引是如何形成的呢?



那有没有什么办法,能够让我们尽量快的定位到数据页,而不至于全表扫描呢?

这件事,就要交给索引来处理了。

顺着数据页的双向链表数据结构一个个去寻找,未免显得太费力了,我们可以为每个数据页创建一个目录,查询数据时,先到目录里看一样有没有自己想要的数据,这样不就快很多了吗。

首先,我们看下数据页内部的构造:

分库分表实战(第5期):寻根问底 — MySQL索引是如何形成的?

比如,我们以数据页1举例,数据页1中有很多的数据行,数据行之间都是用指针连接,并且以单向链表的方式组织起来的,并且单向链表中主键一定是保证有序的,无序的数据是没法创建索引的。

可以看到,数据行前面的 0、2、3  表示记录的类型,也就是数据行的类型,0表示普通类型,就是表中的一行普通数据,2表示最小记录,3表示最大记录,因为我们都知道数据行对应的主键都是有顺序的。

这里为了方便展示索引,我们假设每个数据页中都有20条数据,当我们建立索引之后,如下图:

分库分表实战(第5期):寻根问底 — MySQL索引是如何形成的?

可以看到,索引页中会记录每个数据页中最小的主键即id的值,以及对应的数据页号,而索引页就发挥了我们刚提到的数据页目录的效果。

索引页其实也是数据页,只不过是我们拿来专门存放数据页的目录信息而已,可以看到索引页中的记录类型,除了2和3之外还有1,1表示的是目录的类型,因为它是指向具体的某个数据页的。

而如果数据页很多的话,一个索引页中肯定就放不下这些目录信息,此时,MYSQL会把超出索引页的目录信息放到新的索引页中,然后向上再扩展出一个索引页,如下图:

分库分表实战(第5期):寻根问底 — MySQL索引是如何形成的?

可以看到,数据页3和数据页4的目录信息,被放到了索引页2中,然后索引3作为扩展出来的索引页,记录索引页1和索引页2中的最小主键值以及索引页号,也就是说索引页3中记录的信息,就相当于更上一层索引的目录信息了。

如果索引页3中的容量也不够了,这个时候,同样会把超出索引页3的信息,放到新的一个同层级的索引页中,然后再向上扩展一层,如下图:

分库分表实战(第5期):寻根问底 — MySQL索引是如何形成的?

可以看到,在索引页3中的信息放不下之后,就会放到索引页4中,然后向上再拓展一层索引5,索引5中存放的就是索引3和索引4的目录信息,规律都是一样的。

而图片中,我们可以看到,索引页逐层的往上扩展,看起来就像一棵树一样,这也就是我们经常说的B+索引树,图片中索引的高度为3层,一般就可以存放千万级别的数据了。

为什么利用索引查询就能变快呢?


我们再来看下刚才这张图:

分库分表实战(第5期):寻根问底 — MySQL索引是如何形成的?

有了索引之后,如果我们要查询主键为1的那条数据,就可以从B+索引树最上面的那个索引页开始查询。

如图,我们可以把索引页5先加载到内存,此时会发生一次磁盘IO,然后再通过二分法,根据主键值1,到索引页5中快速的和各个目录项中的最小主键值对比一下,然后找到下一个索引页3,通过索引页3又可以定位到下一个索引页1。

在这颗B+索引树中,通过二分法对比最小主键值的方式,最终在索引页1中发现,原来主键值为1的那条数据,是位于数据页1中,此时,我们就可以针对性的把数据页1加载到内存,然后在内存中就可以查到主键为1的数据了。

通过这样的方式可以发现,我们不需要像之前无索引一样全表扫描,挨个加载数据页到内存中,而是利用索引页,通过高效的二分法查找,很快就可以定位到数据具体是在哪个数据页中。

并且这个过程中我们也发现,就算是上千万级别的数据量,我们也可以做到只发生个位数磁盘IO,就可以查询到数据,这也是为什么用了索引之后查询的效率明显提高的原因。

所以,接下来的sql优化,关键在于要想办法让sql语句能利用索引查数据,这样的话查询的效率才会上来,但是有时会有很多因素,导致不能正常让sql语句使用索引,这也是接下来sql优化的一个关键点。

结束语



好了,通过才的索引原理,我们知道千万级的数据量,B+树基本也就是三到四层,那么如果正常使用到了索引,性能通常不是问题,所以问题原因基本可以确定是因为sql没有使用到索引,也就是索引失效了。

现在理论都已经准备好了,那么下一步就是针对性的实操了。

B站视频链接:https://sourl.cn/q4TCAu

下期连载预告:“分库分表实战(第6期):小试牛刀 — 千万级数据之sql优化上篇”



分库分表实战(第5期):寻根问底 — MySQL索引是如何形成的?

精彩往期

-------------  END  -------------




为了程序员能够顶住面试现场的连环炮,将生产上线的分库分表经验用到自己项目中去。顺利跳槽加薪,实现人生跨越!儒猿特制了海量数据场景下的分库分表生产实践”专栏。有跳槽计划或分库分表技术感兴趣的同学一定要点击下方海报了解哈!





分库分表实战(第5期):寻根问底 — MySQL索引是如何形成的?


分库分表实战(第5期):寻根问底 — MySQL索引是如何形成的?


扫描上方二维码,获取更多资料

点个在看你最好看