【MySQL】十三、深入MySQL索引的秘密（一）

本文主要介绍MySQL数据库的必须要掌握的索引的相关知识

假设没有任何索引，数据库是如何根据查询语句搜索数据的

在磁盘文件中，数据页之间是组成双向链表的，然后数据页内部的数据行是组成单向链表的，而且数据行是根据主键从小到大排序的。然后每个数据页里都会有一个页目录，里面根据数据行的主键存放了一个目录，同时数据行是被分散存储到不同的槽位里去的，所以实际上每个数据页的目录里，就是这个页里每个主键跟所在槽位的映射关系，如下图所示

所以假设你要根据主键查找一条数据，而且假设此时你数据库里那个表就没几条数据，那个表总共就一个数据页，那么就太简单了，首先就会先到数据页的页目录里根据主键进行二分查找。

然后通过二分查找在目录里迅速定位到主键对应的数据是在哪个槽位里，然后到那个槽位里去，遍历槽位里每一行数据，就能快速找到那个主键对应的数据了。每个槽位里都有一组数据行，你就是在里面遍历查找就可以了。

但是假设你要是根据非主键的其他字段查找数据呢？

此时你是没有办法使用主键的那种页目录来二分查找的，只能进入到数据页里，根据单项链表依次遍历查找数据了，这就性能很差了。

那么现在加入我们有很多数据页呢？一个表里往往都是有大量数据的，可能有多达成百上千个数据页，这些数据页就存放在物理磁盘文件里，所以此时是如何查找数据的呢？

如果要是没有建立任何索引，那么无论是根据主键查询，还是根据其他字段来条件查询，实际上都没有什么取巧的办法。你一个表里所有数据页都是组成双向链表的，直接从第一个数据页开始遍历所有数据页，从第一个数据页开始，你得先把第一个数据页从磁盘上读取到内存buffer pool的缓存页里来。

然后就在第一个数据页对应的缓存页里，按照上述办法查找，假设是根据主键查找的，你可以在数据页里的页目录里二分查找，假设要是根据其他字段查找的，只能是根据数据页内部的单项链表来遍历查找，如下图：

那么假设如上图所示，假设第一个数据页没找到你要的那条数据呢？

没办法，只能根据数据页的双向链表去找下一个数据页，然后读取到buffer pool的缓存页里去，然后按一样的方法在一个缓存页内部查找那条数据。如果依然还是查找不到呢？那只能根据双向链表继续加载下一个数据页到缓存页里来，以此类推，循环往复。此时就是在对数据库做全表扫描。

不断在表中插入数据时，物理存储是如何进行页分裂的？

一般来说，在没有索引的情况下，所有的数据查询，其实在物理层面都是全表扫描，依次扫描每个数据页内部的每个数据行。没有索引情况下在一个表中的数据查询，可以说是慢到惊人，所以一般肯定是不能让查询走全表扫描的，因此必须要运用到索引来加速查询的执行。

我们在一个表里不停的插入数据的时候，还会涉及到一个页分裂的过程，也就是说，这个表里是如何出现一个又一个数据页的。

在正常情况下我们在一个表里插入一些数据后，他们都会进入到一个数据页里去，在数据页内部，他们会组成一个单向链表，这个数据页内部的单向链表大致如下图所示：

如上图所示，里面就是一行一行的数据，刚开始第一行是起始行，他的行类型是2，就是最小的一行，然后他有一个指针指向了下一行数据，每一行数据都有自己每个字段的值，然后每一行通过一个指针不停的指向下一行数据，普通的数据行的类型都是0，最后一行是一个类型为3的，就是代表最大的一行。

上面就是一个典型的数据页内部的情况，那么页分裂是什么意思呢?

假设你不停的在表里插入数据，那么刚开始是不是就是不停的在一个数据页插入数据？接着数据越来越多，越来越多，此时就要再搞一个数据页了，如下图所示：

但是此时会遇到一个问题，索引运作的一个核心基础就是要求你后一个数据页的主键值都大于前面一个数据页的主键值，但是如果你的主键是自增的，那还可以保证这一点，因为你新插入后一个数据页的主键值一定都是大于前一个数据页的主键值。

但是有的时候你的主键不是自增长的，所以可能会出现你后一个数据页的主键值里，有的主键是小于前一个数据页的主键值的。比如在第一个数据页里有一条数据的主键是10，第二个数据页里居然有一条数据的主键值是8，那此时肯定有问题了。

所以此时就会出现一个过程，叫做页分裂，就是万一你的主键值都是你自己设置的，那么在增加一个新的数据页的时候，实际上会把前一个数据页里主键值较大的，挪动到新的数据页里来，然后把你新插入的主键值较小的数据挪动到上一个数据页里去，保证新数据页里的主键值一定都比上一个数据页里的主键值大。

这个就是页分裂的过程，核心目标就是保证下一个数据页里的主键值都比上一个数据页里的主键值要大。

基于主键的索引是如何设计的，以及如何根据主键索引查询？

当我们不停的往表里灌入数据的时候，会搞出来一个一个的数据页，如果你的主键不是自增的，他可能会有一个数据行的挪动过程，保证你下一个数据页的主键值都大于上一个数据页的主键值。

假设我们有多个数据页，然后想要根据主键来查询数据，那么直接查询的话也是不行的，因为我们也不知道主键到底是在哪里。比如下图：

现在假设你要搜id=4的数据，你怎么知道在哪个数据页里？没有任何证据可以告诉你他到底是在哪个数据页里，所以假设还是这个样子的话，你也就只能全表扫描了，从第一个数据页开始，每个数据页都进入到页目录里查找主键，最坏情况下，所有数据页你都得扫描一遍，还是很坑的。

所以其实此时就需要针对主键设计一个索引了，针对主键的索引实际上就是主键目录，这个主键目录呢，就是把每个数据页的页号，还有数据页里最小的主键值放在一起，组成一个索引的目录，如下图所示：

现在我们有了上图的主键目录就方便了，直接就可以到主键目录里去搜索，比如你要找id=3的数据，此时就会跟每个数据页的最小主键来比，首先id=3大于了数据页2里的最小主键值1，接着小于了数据页8里的最小主键值4。

所以既然如此，你直接就可以定位到id=3的数据一定是在数据页2里的，假设你有很多的数据页，在主键目录里就会有很多的数据页和最小主键值，此时你完全可以根据二分查找的方式来找你要找的id到底在哪个数据页里。所以这个效率非常高，类似上图的主键目录，就可以认为是主键索引。

而我们的数据页都是一坨一坨的连续数据放在很多磁盘文件里的，所以只要你能够根据主键索引定位到数据所在的数据页，此时假设我们有别的方式存储了数据页跟磁盘文件的对应关系，此时你就可以找到一个磁盘文件。

而且我们假设数据页在磁盘文件里的位置也就是offset偏移量，你也是可以知道的，此时就可以直接通过随机读的方式定位到磁盘文件的某个offset偏移量的文职，然后就可以读取连续的一大坨数据了。

索引的页存储物理结构是如何用B+树来实现的

我们表里的数据可能很多很多，比如有几百万、几千万，甚至单表几亿条数据都是有可能的，所以此时可能有大量的数据页，然后你的主键目录里就要存储大量的数据页和最小主键值，这肯定是不行的。

在考虑这个问题的时候，实际上是采取了一种把索引数据存储在数据页里的方式来做的，也就是说，你的表的实际数据是存放在数据页里的，然后你的表的索引其实也是存放在页里的，此时索引放在页里之后，就会有索引页，假设你有很多很多的数据页，那么此时你就可以有很多的索引页，此时如下图所示：

但是现在又会存在一个问题，你现在有很多索引页，但是此时你需要知道，你应该在哪个索引页里去找你的主键数据，是索引页20？还是索引页28，这也是个大问题。

于是接下来我们又可以把索引页多加一个层级出来，在更高的索引层级里，保存了每个索引页和索引页里的最小主键值，如下图所示：

现在就好了，假设我们要找id=46的，直接先到最顶层的索引页35里去找，直接通过二分查找可以定位到下一步应该到索引页20里去找，接下来到索引页20里通过二分查找定位，也很快可以定位到数据应该在数据页8里，再进入数据页8里，就可以找到id=46的那行数据了。

那么现在问题再次来了，假如你最顶层的那个索引页里存放的下层索引页的页号也太多了，怎么办呢？此时可以再次分裂，再加上一层索引页，比如下面图里那样子：

所以索引页就被搞成一个B+树，属于数据结构里的一种属性数据结构，所以一直说MySQL的索引是用B+树来组成的。

当你为一个表的主键建立起来索引之后，其实这个主键的索引就是一颗B+树，然后当你要根据主键来查询数据的时候，直接就是从B+树的顶层开始二分查找，一层一层往下定位，最终一直定位到一个数据页里，在数据页内部的目录里二分查找，找到那条数据。