点击上方蓝色“
石杉的架构笔记”，选择“设为星标”
回复“PDF”获取独家整理的学习资料！
本次分享儒猿专栏
《从零开始带你成为
MySQL
实战优化高手》
中Mysql索引的内容。本次会先从一个数据页中如何存储和查询数据开始，拓展到多个数据页中查询数据，分析无索引查询时的低效率问题，然后通过页分裂过渡到主键目录以及索引页相关内容，见证一颗索引树是如何一步步生长起来的。
最后站在更高的角度看下常见的一些索引名词、索引的优缺点以及如何才能设计出更好的索引来，开始分析前我们先来思考下如下的一些面试题：
1.InnoDB的索引数据结构是什么？
为什么用这种数据结构？
数据页是Mysql中数据管理的最小单元，既然我们要研究索引是如何高效查询数据的，首先我们肯定要搞清楚数据是如何存放的，数据页的结构通过上篇文章我们了解到大概是这样的：
而数据表中的每行数据就存放在数据区中，数据区中每行数据以单向链表的方式，通过指针连接起来，如下图所示：
同时每个数据页之间再通过双向链表的方式组织连接起来，如下图所示：
通过以上对数据页以及数据页内部数据结构初步的分析，现在我们就可以看下，如果说要查询某张表的某行数据会经过什么样的流程。
数据页一开始当然是存放在磁盘中的，一张表对一般会应着多个数据页，查询数据时从磁盘中依次加载数据页到InnoDB的缓冲池中，然后对缓冲池中缓存页的每行数据，通过数据页的单向链表一个一个去遍历查找，如果没有找到，那么就会顺着数据页的双向链表数据结构，依次遍历加载磁盘中的其他数据页到缓冲池中遍历查询。
大家可以看到，像上面这样的查询方式就有点傻了，因为如果恰好你要查的数据行在这张表最后一个数据页的最后一行，那岂不是所有的数据页都要被扫描一遍，然后每个数据页中也是遍历链表，整体的效果就是
以O(n)的时间复杂度在遍历链表了,这样查询的性能肯定是不行的。
我们先把目光转移到单个数据页内的数据查询，假如说我们现在已经锁定数据就在某个数据页中了，但是我们该怎样快速的从这个数据页中找到我们想要的那行数据呢？
通过之前的分析我们可以知道，最傻的一种方式就是遍历数据页中的单向链表查询，一个节点一个节点去扫描，相对应的查询效率是肉眼可见的低。但是如果说可以像翻书一样，根据目录来减小我们查询的范围，相对应的查询效率不就上来了吗，根据这种想法，InnoDB存储引擎设计了槽位这种方式来组织数据页中的多个数据行，槽位信息存放在数据页中的数据页目录中。
槽位简单来说就是将数据页中的多个数据行分组划分，每个数据行组都找这个组中的主键值最大的那个数据行的地址作为槽位的信息，这样数据页目录中的一个个槽位不就是像是一个个目录了吗，标记好了多个数据行分组的位置信息，如下图所示：
这下有了数据页目录中的槽位信息，此时要查询数据页中的某行数据不就很简答了，比如我们要查询主键为4的那行数据，直接通过二分法以O(logn)的时间复杂度锁定数据页目录中的槽位2，因为槽位之间都是紧密连接的，可以通过槽位2找到槽位1，从槽位1末尾开始，对分组2中的数据开始遍历，因为每个分组中的数据量都很少，此时在这么小的范围内简单遍历下就可以快速找到主键为4的那行数据，时间复杂度从之前的O(n)降低到O(logn)效率还是挺可观的。
但是如果你不是通过主键去查询的，槽位此时就排不上用场，你还得一个一个遍历数据页中的单向链表去找到你想要的那行数据。
2.2 索引的前夕-页分裂
这里我们先来个小插曲，简单了解下页分裂，这块内容也是后面索引机制能够正常运行的基础。
我们都知道一个数据页就是16KB大小，当一个数据页中的数据行足够多时就会重新创建一个数据页继续写数据行，如果说我们没有用到索引还好，但是如果我们要在表中创建索引，那么对多个数据页中的数据就有约束了。
如果新创建的数据页中的数据行的主键值，存在比它上一个数据页的主键值还小的情况，这种情况是不被允许的，如下图所示：
如果出现上图的情况，多个数据页之间的主键就无序了，而索引机制的实现是要基于多个数据页主键的大小是依次递增的，所以此时就会出现页分裂的情况。
其实页分裂目的也很明确，就是调整下不同数据页的数据顺序，使得最终按顺序创建的索引页之间，后一个数据页中的每一个数据行的主键值都要大于上一个数据页，当然一个数据页中当然是按照单向链表的方式依次递增的，页分裂流程如下图所示：
我们可以看到页分裂主要就是调整了下数据页之间数据行的数据的顺序，使得多个数据页之间的主键值是按照顺序来存放的，在这样有序的数据中，高效查询才变得可能。
频繁的出现页分裂情况，毕竟页分裂要涉及到数据的移动，在性能上也是会有损耗的，这也警示我们减少页分裂的出现概率是非常有必要的，在设计表结构时我们可以尽量使用主键自增长的方式，而不是用很难保证主键顺序的自定义创建主键的方式，使用主键自增长方式，能大大避免说数据页之间主键大小出现顺序错乱的问题，减少页分裂发生的概率。
2.2 从主键目录到索引页
查询一行数据，在物理层面就是定位到哪一个数据页中的哪一行数据。在数据页中定位数据的问题，在之前我们已经通过槽位的方式优化了查询的效率，现在我们要解决的是如何在大量的数据页中定位数据页，这就是索引的目标。
InnoDB存储引擎一开始是使用主键目录的方式，将数据页号和数据页最小的主键值作为一条记录，如下图所示：
这样的话，我们要查哪一条数据就不用扫描一个数据页内的所有数据再扫描下一个了，直接通过id去主键目录看一下，通过二分查找定位到具体哪个数据页，然后数据页内部通过定位槽位，遍历那个槽位对应数据行分组找到具体的一行数据。
现在有一个问题就是，每张表对应的数据页都有很多，主键目录就会有大量的数据、就有可能放不下，这时InnoDB设计者们就想存放目录数据也是数据啊，为什么不可以使用数据页来放呢，就这样主键目录的信息就被移到数据页来了，而这些数据页就被称为索引页，如下图所示：
从这里我们可以知道数据页肯定不是简单只存放数据表中的数据的。好了，现在主键目录由于容量有限，我们把主键目录信息移动到了数据页中形成了索引页，但同样的问题不还是会出现吗，一个数据页的大小也才16KB，索引页本身的容量也是有限的，容量不够了该怎么办呢？
为了解决索引页容量不够的问题，索引页会重新创建和升级，先把超出容量的数据放到一个新的索引页中，然后再加一层索引页，如下图所示：
由上图我们可以看到，新的一层索引页35它存放的就不是最小主键对应的数据页目录了，而是最小主键对应的索引页目录了，以此类推如果索引页35这里容量也不够呢，那就继续往上一层扩展啊，最终效果看起来就像下面一样：
