InnoDB设计了多种页结构用于存放不同类型的数据，我们现在主要研究存放数据的页，称为索引页或数据页。
每个页由七部分组成，大致功能如下：
其中User Records和Page Directory是我们的主要研究目标。
其实从一开始是没有user records这个空间的。当插入第一条数据的时候，会从free space空间分配出一个空间到user records，直到插入最后一条记录将free space的空间全部用完就会再去申请一个新的页。
User Records是用来存储数据的地方，简单来说就是怎么把每行数据摆在这个空间里。
行格式的数据结构中的记录头信息在摆放数据的过程中发挥了重要作用，我们来回顾一下记录头信息的各个属性。：
delete_mask 标记该记录是否被删除
n_owned 如果当前记录是组内最大记录，则代表槽内的记录数
heap_no 当前记录在本页中的位置信息
record_type 表示当前记录的类型
0表示普通记录，1表示B+树非叶子节点记录，2表示最小记录，3表示最大记录
next_record 表示当前记录到下一条记录的地址偏移量
我们发现有一个next_record记录了当前记录到下一个记录的地地址偏移量，也就是说我们知道了当前记录的位置就可以找到下一个记录。所以说，整个user record空间是一个单链表。链表中的各个节点是按照主键值从小到大的顺序连接起来的。
现在有一个问题，我们要在一个页中查找指定的一条记录。除了从头遍历还有更高效率的方法么？Page Directory提供了解决方案。
InnoDB会将一个页中的所有记录划分成若干个组，每组4-8个记录。将每个组最后一个记录相对于第一个记录的地址偏移量（可以定位到真实数据记录）提取出来存放在页中一个叫做Page Directory的数组中，数组中的元素就是这些地址偏移量，也称为槽(slot)。所以Page Directory就是由槽组成的。
所以在一个页中根据主键查找记录是很快的，步骤为：
二分法：只适用于数组。
链表是顺序存取，不是随机存取，用二分查找并不能提高查找效率，因为你每次还得从第一个结点出发，找到指针LOW,HIGH,MIDDLE所指的元素，所以一般不在链表内使用二分查找。
原文：https://www.cnblogs.com/hans-kl/p/12904374.html