InnoDB数据页

导读：

我们已经知道了页是数据库存储的基本单位，知道了一条行记录的存储格式是怎样的，当数据越来越多时，那一条条行记录具体又是怎么在页中被组织起来的呢？

一、InnoDB数据页结构

二、总结

1、一条条行数据是如何在数据页中被组织起来的？

首先，在每一个数据页中存在两个虚拟记录，一个代表最小记录，一个代表最大记录，它们被存储在数据页的 Infimum + Supremum 部分。

紧接着，当向表中插入一些数据时，这些记录会被存储在数据页中的 User Records 中，这里不仅存储了其真实内容，还有存储了一些额外的数据，比如头信息中的 next_record，通过这个标记加上两个虚拟记录，使得记录形成了一条按照主键值由小到大的顺序的单链表(非插入顺序)。

然后，为了数据能够查的更快，将数据页中的数据进行了分组，每组最后一个记录的地址偏移量作为槽，存放在 Page Directory(页目录)，这样对于之后通过主键查询记录时，只需通过二分法确定目标结果存储在哪个组，然后在组中通过记录的 next_record 属性进行遍历即可找到目标。这样就完成了一个数据页中数据的组织。

最后，一个数据页默认大小为 16 KB，当一个数据页不足存储新数据时，将会申请新的数据页进行存储。此时，数据页结构中的 File Header 就发挥作用，其包含 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 两个属性，它们分别代表本页的上一个和下一个页的页号，这样就可通过这两个属性将许许多多的页就都串联起来了，形成一个双向链表。

总的来说，各个数据页可以组成一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边儿的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

三、在 MySQL InnoDB 的页目录（Page Directory）设计中，为什么槽（Slot）记录的是分组中最大主键值，而不是最小值？

在 InnoDB 数据页中，所有记录按主键顺序物理存储（升序排列）。页目录的槽将这些记录分成多个分组（例如，每个分组通常包含 4-8 条记录），槽的信息允许二分查找快速定位目标记录所在的分组，然后在该分组内进行线性查找（因为分组内记录数量较少，线性查找代价低）。使用最大主键值作为槽值的核心原因是：它使二分查找的决策更简单、更高效，减少了比较操作的歧义，并能直接利用主键单调递增的特性。

1、为什么最大值优于最小值？

1.1、使用最大值时的二分查找逻辑：当目标主键（Target Key）与槽值比较时：

如果目标主键 <= 槽值（分组最大主键），则目标记录可能位于该槽对应的分组或更早的分组（因为槽值是该分组的最大主键，目标值不超过最大值说明它可能在这个分组内）。
如果目标主键 > 槽值，则目标记录一定位于后续的分组（因为分组最大主键小于目标值，说明目标不在当前或之前的任何分组）。

这允许二分查找高效调整搜索范围（例如，调整 high 或 low 指针），每次比较都能明确缩小搜索范围，没有歧义。

1.2、使用最小值时的二分查找问题：如果槽记录分组的最小主键值：

如果目标主键 < 槽值（分组最小主键），则目标记录一定位于更早的分组。
如果目标主键 >= 槽值，则目标记录可能位于该槽对应的分组或更晚的分组。

这种方式在比较时存在歧义：当目标主键 >= 槽值时，无法立即确定目标是否在分组内，因为分组最小主键只表示分组的起始点，但分组可能包含更大的值（例如，目标值可能落在两个分组之间）。这会导致二分查找需要额外的检查步骤（如检查后一个槽的最小值），或多次线性探测，降低了效率。

简单来说，使用最大值允许二分查找直接通过 target <= slot_value 条件锁定目标分组，而最小值会导致条件模糊，查询路径更长。

2、结合二分法的详细示例

下面通过一个具体例子说明。假设一个 InnoDB 数据页包含以下主键值（已排序）：1, 3, 5, 7, 9, 11, 13, 15。为简化，假设每个分组包含2条记录，页目录有4个槽：

分组：组1 (1, 3)、组2 (5, 7)、组3 (9, 11)、组4 (13, 15)。

现在，执行二分查找目标主键为10的记录（10不存在，但查找过程相同）。

二分查找的伪代码如下（以方案A和B分别演示）：

# 通用二分查找框架（查找可能的分组索引）

low = 0

high = num_slots - 1

while low <= high:

mid = (low + high) // 2

if target <= slots[mid].value: # 比较目标值和槽值

high = mid - 1 # 目标在左半部分（包括当前槽）

else:

low = mid + 1 # 目标在右半部分

# 结束时，low 是可能的目标分组索引

方案A：使用最大值的二分查找（高效）

槽值设置：槽0 = 3（组1最大主键）、槽1 = 7（组2最大主键）、槽2 = 11（组3最大主键）、槽3 = 15（组4最大主键）。
槽值数组：[3, 7, 11, 15]（槽索引：0,1,2,3）
查找目标：10
二分查找过程：
- 初始：low = 0, high = 3
  - mid = (0 + 3) // 2 = 1, 槽值 = 7
  - 比较：10 <= 7？ False → 目标 > 7，所以目标在槽1之后，设置 low = mid + 1 = 2
- 更新：low = 2, high = 3
  - mid = (2 + 3) // 2 = 2, 槽值 = 11
  - 比较：10 <= 11？ True → 目标可能位于槽2或更早分组，设置 high = mid - 1 = 1
- 现在 low = 2, high = 1，low > high，循环结束。返回候选索引 low = 2（可能的目标分组）。
结果：槽2被选中（对应组3）。然后在组3内线性查找记录（9和11），发现10不存在。
分析：仅2次比较就锁定了槽2（组3），因为最大值为11提供了明确的上界：10 <= 11表示目标一定在槽2之前的某个分组（或槽2本身），而前一步的 low 调整确保了高效收敛。整个查找过程直接，没有歧义。

方案B：使用最小值的二分查找（低效）

槽值设置：槽0 = 1（组1最小主键）、槽1 = 5（组2最小主键）、槽2 = 9（组3最小主键）、槽3 = 13（组4最小主键）。
槽值数组：[1, 5, 9, 13]（槽索引：0,1,2,3）
查找目标：10
二分查找过程：
- 初始：low = 0, high = 3
  - mid = (0 + 3) // 2 = 1, 槽值 = 5
  - 比较：10 <= 5？ False → 目标 > 5，但无法确定是否在槽1分组内（因为 min=5，目标可能位于槽1或后续分组），设置 low = mid + 1 = 2
- 更新：low = 2, high = 3
  - mid = (2 + 3) // 2 = 2, 槽值 = 9
  - 比较：10 <= 9？ False → 目标 > 9，同样无法确定，设置 low = mid + 1 = 3
- 更新：low = 3, high = 3
  - mid = (3 + 3) // 2 = 3, 槽值 = 13
  - 比较：10 <= 13？ True → 目标可能位于槽3或更早分组，设置 high = mid - 1 = 2
- 现在 low = 3, high = 2，low > high，循环结束。返回候选索引 low = 3（可能的目标分组）。
结果：槽3被选中（对应组4）。但组4的最小主键是13 > 10，所以目标不在该分组。需要额外检查前一个槽（槽2，组3）或直接线性扫描组3，才能确定10在组3范围内（但不存在）。
分析：使用了3次比较，但结束时 low=3 是错误的（组4最小主键13 > 10，目标不可能在组4）。二分查找后，必须额外检查槽2的槽值（9），才能发现目标可能位于槽2分组（因为 9 <= 10 但 10 < 13）。整个路径更长，存在歧义：当目标 > 槽值时，无法排除当前分组的可能性，导致 low 和 high 调整不精确。这会增加不必要的比较和分组访问次数。

关键区别总结

决策清晰性：使用最大值时，槽值（最大主键）定义了分组的明确上界。二分查找中，target <= slot_value 直接表示目标位于索引 <= mid 的某个分组，从而高效缩小搜索范围。最小值则只能定义分组的起始点，没有上界信息，导致决策模糊。
效率：最大值的二分查找平均只需 O(log N) 次比较（N是槽数），就能锁定唯一可能的分组。最小值可能需要额外线性探测或回溯，增加开销。
插入与范围查询：在插入新记录时，使用最大值也更容易处理边界情况（如记录插入到分组末尾）。对于范围查询（如 key BETWEEN A AND B），最大值可以快速排除不相关的分组。
单调性利用：主键值单调递增，使用最大值序列（如3,7,11,15）也单调递增，恰好匹配二分查找要求。

设计背后的权衡

InnoDB 选择最大值是工程优化，牺牲少量内存（存储最大值）换取查询性能。分组大小（如默认每组6-8条记录）也进行了权衡，确保二分查找快速收敛的同时，分组内线性查找成本低。实际实现中，InnoDB 的页目录还处理了记录删除、变长记录等复杂情况，但最大值原则保持了二分查找的效率。

总之，槽记录分组最大主键值而非最小值，是为了使二分查找在页内定位记录时更高效、直接，减少了歧义和额外操作，从而提升整体查询性能。