参考资料
https://relph1119.github.io/mysql-learning-notes/#/mysql/
我们知道InnoDB 管理存储空间的基本单位是页，一个页的大小默认是16KB 。 InnoDB 为了不同的目的而设计了许多种不同类型的页，如change buffer page、undo log page、index page。其中，Index Page就是用于存放数据的页。
数据页结构
一个 InnoDB 数据页的存储空间大致被划分成了 7 个部分
数据页字段信息
Infimum/Supremum
固定占用26个字节，每个数据页中都自动添加了两个记录，一个代表最小记录，一个代表最大记录。
User Records
用于存储记录数据的的区域，记录按照主键的顺序由小到大存储。每行记录中存储了下一行记录的地址，形成一个单向的链表。
Page Directory
我们知道记录在页中按照主键值由小到大的顺序串联成一个单链表，那么，怎么根据主键值查询页中的记录呢？比如说这样的查询语句：
SELECT * FROM page_demo WHERE c1 = 3;
最简单的方式是遍历页中的记录，从最小记录Infimum开始，沿着链表往下依次查找，直到找到符合条件的记录或者链表遍历完为止，时间复杂度是O(N)。这种查找方式随着页中记录数量的增加，查询时间也同步随之增加。
在实际情况中，一个数据页中保存的记录是很多的，通过遍历的方式，过于低效。Page Directory就是用来加速页内记录查找的，类似于一本书的目录，通过目录可以快速找到内容。
Page Directory的创建
- 将所有正常的记录（包括最大和最小记录，不包括标记为已删除的记录），按顺序划分组，每组最多包含八行记录。 其中最小记录为第一个分组，该分组只有一条记录。
- 每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的 n_owned 属性表示该组内共有几条记录。
- 将每个组的最后一条记录的地址偏移量单独提取出来按顺序存储到Page Directory，也叫做页目录，页面目录中的这些地址偏移量被称为槽（Slot）。
有些类似于一个两层的跳表，先通过第一层的链表(相当于Slot)进行二分查找，确定记录所在的区间，然后在该区间进行遍历匹配。
例如现在一个数据页中page directory中有0,1,2,3,4五个槽位，对应的主键值分别是4,8,12,16,20。现在查找主键等于10的记录：
- 开始二分查找，(0+4)/2=2，查看槽位2对应的主键是12
- 因为10小于12，所以在槽位2之前再进行二分查找，(0+2)/2=1，查看槽位1对应的主键值8
- 因为10>8，所以不可能在槽位1中，记录只可能在槽位2中。
- 进入槽位2中遍历，查找主键等于10的记录
Page Header
这个部分固定占用56个字节，用于存储数据页中各种信息，如数据页归属的索引Id、页中存储了多少条记录、第一条记录的地址、页目录中有多少个槽位等等。
File Header
位于数据页头部，用于描述当前页面的基础信息，比如说页的编号、上一个页、下一个页，这个部分占用固定的 38 个字节。
其中FIL_PAGE_PREV 和 FIL_PAGE_NEXT，用于标识上一个页和下一个页，数据页之间由此组成了一个双向链表。InnoDB数据页（FIL_INDEX_PAGE)中这两个字段有值，便于进行范围查询。
File Trailer
用于检测页是否完整，如将内存中更改的页刷新到磁盘上时，怎么判断内存中的页数据全部刷新到磁盘上了。
位于数据页尾部，这个部分由 8 个字 节组成，可以分成2个小部分：
前4个字节代表页的校验和
与File Header 中的校验和相对应。每当一个页面在内存中修改了，在同步之前就要把它的校验和算出来。File Header在页面的前边，所以校验和会被首先同步到磁盘。当刷新完成后，校验File Header和File Trailer中的检验和，如果一致则表示同步成功；不一致则表示同步失败。
后4个字节代表页面被最后修改时对应的日志序列位置（LSN）
也是用于校验页的完整性
标签：记录,查找,InnoDB,File,数据,Page From： https://www.cnblogs.com/cd-along/p/18107294