数据页的结构
数据页是如何存储记录的？
- 文件头：包含上一页和下一页的指针，让 B+树中同一层的节点组成双向链表，目的是方便范围查询
- 页头：表示页的状态信息
- 最大最小记录：两条伪记录
- 用户记录：存储真实的行记录
- 空闲空间：页中还未被使用的空间
- 页目录：用户记录的索引，加速查找
- 文件尾：校验页是否完整
页目录对记录的索引
页目录如何加速查找？
- 所有记录会被划分为多个组（包含最大最小记录）
- 每组最后一条记录的头信息中会存储「当前组的记录数量」，作为
n_owned字段（上图的粉色字段） - 页目录包含多个槽（slot），按顺序指向每个组的最后一条记录
- 查找时，先通过二分法查找目标记录所在的槽位，然后遍历槽位指向的组内的所有记录，例如查找键为 11 的记录，会二分找到槽 2，然后向后遍历下一个分组的记录找到 11
避免槽位的索引失效
如果槽位内的记录过多会导致性能退化为单向链表的 ，通过以下限制避免索引失效
- 第一个分组内只能有一条最小记录
- 最后一个分组只能you 1~8 条记录
- 其他分组只能有 4~8 条记录
B+树中的数据页
B+树是如何进行查询的？
B+树中每个节点都是数据页，从根节点到叶子节点，每一层都通过二分法找到目标记录在哪一个数据页中
以在上图中查找主键为 6 的记录为例：
- 6 在 1~7 之间，读取页 30
- 6 在 5 之上，读取页 16
- 在叶子节点（页 16）中二分找到记录所在槽位，遍历对应分组内的记录找到目标记录