分库分表实战：寻根问底 — MySQL索引是如何形成的？

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

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

答案就是索引。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

首先，我们看下数据页内部的构造：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

结束语

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