从根上彻底理解MySQL的索引( 二 ) _MySQL

图中包含4个槽，分别是0、1、2、3，二分法查找之前，最低的槽low=0，最高的槽high=3 。现在我们再来看看在这个数据页中，我们查询id为7的记录，过程是怎样的。

使用二分法，计算中间槽的位置，(0+3)/2=1，查看槽1对应的“组长”的主键值为4，因为4<7，所以设置low=1，high保持不变；
再次使用二分法，计算中间槽的位置，(1+3)/2=2，查看槽2对应的“组长”的主键值为8，因为8>7，所以设置high=2，low保持不变；
现在high=2，low=1，两者相差1，已经没有必要继续进行二分了，可以确定我们的记录就在槽2中，并且我们也能知道槽2对应的“组长”的主键是8，但是记录之间是单向链表，我们无法向前遍历。上文提到过，我们可以通过槽2找到槽1，进而找到它的“组长”，然后沿着“组长”向下遍历直到找到主键为7的记录就可以了。

当用户记录多到一个数据页装不下的时候，就再申请一个数据页，各个数据页在逻辑上使用双向链表进行连接，因此新分配的数据页编号就没必要非得按照从小到大的顺序进行排列了，如下图所示：

文章插图

因此，虽然在一个数据页内能够做到主键的快速查询，但是InnoDB存储引擎不知道你要查找的记录所在的页号，那也只能从第一页开始沿着双向链表一直进行查找，遍历每一页，至于在每一个数据页中是怎么查找的，你已经很清楚了。
很显然，InnoDB引擎有办法能够快速定位到你要的主键数据所在的数据页，而不是从第一页开始遍历，否则不可能有例3那样的查询速度。
那么，InnoDB是怎么做到的呢？
3. InnoDB索引3.1 主键索引登场为了方便描述，我们假设一个数据页最多只能放3条用户记录，那么user_innodb表的前12条数据的保存形式如下图：

文章插图

大家看这些连接起来的数据页像不像组成一本书的每一章？自然，数据页中的每一条记录就是章中的每一个小节了。

文章插图

那么为了加快检索，我们可以模拟书籍章节目录，给数据页添加一个目录。

文章插图

如上图，我们为4个数据页创建了一个目录，每个数据页对应了一条记录，为了区别于用户记录，我们称之为目录项记录，目录项记录同样是按照主键从小到大的顺序进行单向链接的。
不同于用户记录中包含了完整的数据，目录项记录只包含了数据页的最小主键值和对应的数据页号。既然都是记录，InnoDB的设计者直接用数据页来存储目录项记录了，所以上图中页32的页面结构和其他数据页是完全一样的。
接下来我们看看加了个目录是如何提高我们的查询效率的，以查询主键id为8的记录为例，步骤大致如下：

先找到存储目录项的数据页32，通过二分法快速定位到对应的目录项记录，因为7<8<10，所以定位到对应的记录所在的页应该是页14；
然后在页14中进行查找就可以了，查找的方法我们之前介绍过了。

目前的页面并不多，所以对查询效率的提升并不十分明显，但是一旦数据页的数量飞速增长，这种通过添加目录的方式带来的查询优势会被无限放大！但是同时有个问题，数据页多了，目录项记录在一个数据页中不够用了怎么办？
再加一个数据页。我们再添加2条用户记录，看一下添加之后的样子：

注：实际上一个页面中能够存放的记录（用户记录/目录项记录）数目是非常多的，为了方便画图，我只是假设了数据页最多存放3条用户记录，最多存放4条目录项记录

文章插图

现在假设要查找主键ID为14的记录，我们还是先得找到存储目录项的数据页，可是现在有2个这种数据页，分别是页32、页124，我怎么知道要定位到哪一个目录项数据页呢？从页32开始遍历吗？别开玩笑了，我们做这么多就是为了不想遍历。这样吧，我们为存储目录项的数据页再生成一个目录。我们来捋一捋关系。
前面举过例子，存储用户记录的数据页相当于章，用户记录相当于小节，为章节生成目录就得到了存储目录项记录的数据页（页32和页124），相当于是一本书，然后再为书编一个目录，就相当于是个书架。