MySQL索引是如何形成的

■金澜

MySQL查询过程的瓶颈在于磁盘IO，那怎么降低磁盘IO次数呢？答案就是索引。

正确的使用索引，就能有效地把磁盘IO的次数降到常数级，这样查询速度将会变得非常快。

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

在磁盘中，MySQL存放数据的基本单位是数据页，数据是放在数据页中的，每个数据页中都有很多的数据行。在数据页的数据区中存放着很多数据行，这些数据行就对应数据表中的一行行数据，它们都是通过单向链表方式连接组合起来的。而多个数据页之间又是通过双向链表的方式连接起来的。

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

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

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

最糟糕的情况就是沿着数据页1、数据页2、一直到最后，在最后一个数据页中才找到想要的那条数据，但在这之前，我们得要把数据页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优化的一个关键点。