InnoDB(6)索引页select --mysql从入门到精通（十一)

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

InnoDB(5)索引页 --mysql从入门到精通（十)

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来遍历这个槽，效率就会很高。

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