一、Mysql中使用页的目录项的前提条件
- 记录在页中是按照主键值从小到大的顺序串联成为一个单向链表。那么如果我们要查询id=4的数据，我们用笨方法就是从记录的链表头开始，一直往下查找。但是，如果数据量很大，那么性能就无法保证了。针对这个问题，InnoDB采取了图书目录的解决方案，即：Page Directory。
1、 首先，将非删除的数据（包含Infimum记录和Supremum记录）划分几个组。
（1）、分组规则如下：
- 对于Infimum记录所在的分组只能有1条记录。
- 对于Supremum记录所在的分组只能在1～8条记录之间。
- 剩下的记录所在的分组只能在4～8条记录之间。
（2）、分组步骤如下：
- 初始情况下，一个数据页中只有Infimum记录和Supremum记录这两条，所以分为两个组。
- 之后每当插入一条记录时，都会从页目录中找到对应记录的主键值比待插入记录的主键值大，并且差值最小的槽，然后把该槽对应的n_owned加1。
- 当一个组中的记录数等于8时，当再插入一条记录的时候，会将组中的记录拆分成两个组（一个组中4条记录，另一个组中5条记录）。并在拆分过程中，会在Page Directory中新增一个槽，并记录这个新增分组中最大的那条记录的偏移量。
- 每个组的最后一条记录（即：也是这个组里，最大的那条记录）——“带头大哥”，其余的记录均为“组内小弟”；“大哥”记录的头信息中的n_owned属性表示该组内共有几条记录，而“小弟”的n_owned属性都为0；
- 将“大哥”在页面中的地址偏移量取出来，按顺序存储到靠近Page Trailer的地方。这个地方就是Page Directory。
- Page Directory中的这些地址偏移量被称为槽（Slot），每个槽占用2个字节。
- 一个正常的页面为16KB，即：16384字节。而2个字节可以表示的地址偏移量范围是0～(2^16-1)，即：0～65535。所以2个字节表示一个槽足够了。
- 页目录就是由多个槽组成的。
2、记录和页目录的关系，如下所示，分为2组。 
3、页目录生成完毕后，则可以通过二分法快速进行查找。
4、在一个数据页中查找指定主键值的记录时，过程分为两步：
4.1 、通过二分法确定该记录所在分组对应的Slot，然后找到该Slot所在分组中主键值最小的那条记录。
（1）、每个槽对应的都是组内主键值最大的记录，那么怎么定位一个组中主键值最小的记录呢？
由于每个槽都是挨着的，所以，我们可以通过找到前一个槽中的最大主键值记录，这个记录的
下一条记录（next_record），就是本槽的最小主键值记录。
4.2、通过记录的next_record属性遍历该槽所在组中的各个记录。
