上篇文章介绍了innoBD会有若干索引页,每个索引页的两个虚拟列，infimun小虚拟行记录，supremun大虚拟行记录，这两个存在innoDB的头部信息，里面还有delete_mark，next_record等。free space空间会给user records存储的数据申请，直到用完则会申请新的页。

Page directory(页目录)

我们现在知道记录页中的数据按主键从小到大的顺序组成一个单链表，那我们 查询单链表中的某一个数据该怎么办呢？

原始(笨)的发方法，当然是从按顺序，从Infimum(小)记录依次慢慢从小到大查找，这种还有一个好处是，当主键值大于要找的值时，后面的就不需要找了，因为后面的主键都是递增，说明没有要找的数据。那如果数据量太大这种查找显然不符合要求，如果你找字典，为了找一个字，从页翻到后一页，这显然太消耗性能，于是字典有了目录，而我们 的mysql也有page directory。

每个index数据页有页目录，页目录有两个槽点，槽0放小记录偏移量99和槽1放大记录偏移量112(112实际就是指页面从0字节开始，数112个字节)，小记录的n_owned值为1，大记录的n_owned值为5，包括大记录本身是5条数据，所以我们实际插入4条数据。

innoDB对每个槽点分组规定：小记录所在分组是一条记录，也就是小记录，大记录所在分组能拥有1~8条记录，剩下的范围都在4~8条记录。

所以插入数据的过程：

在初始化的时候，有两个槽点，小槽点和大槽点。

插入数据后，因为小槽点只有一条数据，吧数据插入大槽点，每次插入的时候，会吧当前槽点的n_owned值+1。当插入第9条数据的时候，分为两个槽点，这时候情况就是：三个槽点，小槽点，槽0，槽1放4条记录，大槽点，槽3 放5条记录。

INSERT INTO index_page_tb VALUES(5, 500, 'eeee'), (6, 600, 'ffff'), (7, 700, 'gggg'), (8, 800, 'hhhh'), (9, 900, 'iiii'), (10, 1000, 'jjjj'), (11, 1100, 'kkkk'), (12, 1200, 'llll'), (13, 1300, 'mmmm'), (14, 1400, 'nnnn'), (15, 1500, 'oooo'), (16, 1600, 'pppp');

为了方便查看，我们通过sql插入更多的数据，现在表里有16条真实数据，一共五个槽点（槽0到槽4），我们查询id为6的数据。low为0，大槽high为4，用二分法查找。

所以查询数据的过程：

1、所以二分查找法(0+4)/2 = 2，槽2对应的主键为8，而8>6，所以继续找，此刻的参数low为0，high为2。

2、(0+2)/2=1,槽1对应的主键为4，4<6，此刻的参数low为1，high为2。

3、high-low为1，所以确定主键6 在槽2中，所以槽2 大主键是8，因为每个槽都是挨着，槽1大主键是4，所以槽2 小主键是5，这时候只要从小主键5来遍历这个槽，效率就会很高。

所以总结就是通过二分查找法找到对应的槽，之后从小的主键遍历当前槽。