[翻译] InnoDB 空间文件中的页面管理
本系列文章翻译自 中的 文章 。共 16 篇，本文为第 4 篇。原文链接：
因翻译水品有限，为了避免对读者造成误解，一些专有名词的翻译会在其后用标记出原文。
InnoDB 空间文件中的页面管理
在 （）一文中，我介绍了用来记录 内部结构的 项目，本文中所使用的图表均可以在该项目中找到。
空间的基本结构以及每个页面的基本结构在 （）一文已经中有所描述，接下来我们将详细描述 中 与 页面管理、区段管理、空闲空间管理相关的结构，以及它如何跟踪分配给不同用途的页面的使用情况。
区段和区段描述符
正如前面所描述的， 页面通常是 ，并被分组为 大小的块，一块包含个连续页面，这被称为“区段[]”。 在空间内的固定位置分配 和 页面，用来跟踪哪些 区段 是正在使用的，以及每个 区段 内哪些页面是正在使用的。这些页面的结构非常简单:
它们包含通用的 和 ，一个 （将在稍后讨论），以及 个“区段描述符[]”，还包含大量未使用的空间。
区段描述符具有以下结构:
区段描述符中各个字段的用途如下：
，文件段：如果一个区段属于文件段的话，这个字段表示该区段所属文件段的
， 链表的链表节点：在区段描述符链表中指向上一个区段和下一个区段的指针
，区段当前的的状态：目前只定义了四个值：，，（这三个状态表示区段属于 链表 / 链表 / 链表），（这个状态表示区段属于某个文件段，文件段ID 存储在 结构中的 字段中）
，页面状态位图：在该区段中为每个页面分配的位图（ x = 位，字节）。第一位表示该页是否为空闲；第二个位被预留用于指示页面是否是干净[]的（干净的表示没有未刷新到磁盘的脏数据），但是这个位当前未使用，该位始终设置为
其他结构如果要引用区段，需要使用 区段描述符所在的 页面（或 页面）的页号 和 区段描述符条目本身在页内的字节偏移量 组合来实现。例如，引用的区段是空间中的第一个区段，包含页面，而包含页面。
译者注：这里对第二个例子进行一下详细的计算，对于，首先号页面是第个区段中的第一个页面(类型)，所以这个页面中记录了第区段中的区段描述符，偏移量指向的是本页面中第个条目（），所以描述的是第个区段的信息，也就是号页面。
链表基节点和链表节点
链表（ 称之为“自由链表[]”）是一种非常通用的结构，可以将多个相关结构链接在一起。它由“链表基节点”和“链表节点”两个互补的结构共同组成了一个很好的磁盘上双向链表。“链表基节点”的结构如下:
“链表基节点” 只在某些高级结构（如 ）中存储一次。它包含 链表的长度，以及指向链表中第一个和最后一个节点的指针。“链表节点”的结构看起来非常相似，只是“链表节点”中存储的不是第一个和最后一个节点的指针，而是前一个和下一个节点的指针：
所有指针都包含一个页码（必须在同一空间内）和一个可以找到链表节点的页面中的字节偏移量。所有指针都指向“链表节点”结构的起始位置（即 ），而并不一定是链表节点所属结构的起始位置。例如，在区段描述符条目链表中，由于链表节点在 条目结构中的偏移量为，读取 条目的代码必须“知道” 结构开始于列表节点的偏移量之前个字节，并从那里开始读取结构。（确保列表节点在任何结构中都位于最前面可能是一个好主意，但事实并非如此。）
文件空间头和区段列表
除了存储区段描述符条目本身之外， 页面（该页面在空间中始终是号页面）还存储了 结构，它包含了大量链表，这也是我为什么没有在前面描述该结构的原因。的结构如下:
中与列表无关的字段（不按顺序排列）：
：当前空间的空间 ID
：表示最高的有效页码，并且随文件增长递增。但是，并非所有分配了页码的页都被初始化了（有些可能是被零填充的），因为空间的扩展是一个包含很多步骤的过程
，是所有已经被初始化的所有页面中的最大页码，初始化过程中包含将页码存储在页面自身中。始终小于或等于。
：储存与空间有关的标记
：将被用于下一个分配的文件段的文件段 。（这是一个自动递增的整数。）
：存储这个字段是出于性能优化的考虑，以便能够快速计算 链表中所有区段的空闲页数和，而无需遍历链表中的所有区段并对每个区中可用的空闲页求和。
下列区段描述符链表的链表基节点也存储在 中:
链表：该链表中的区段均为 存在空闲的页面可用于按照"碎片"方式分配 的区段，按照“碎片”方式分配的含义是可以根据不同的需要分配单独的页面，而不是分配整个区段。例如，每个具有 页面或 页面的 区段 将被放置在 列表中，以便 区段 中剩余的空闲页面可以分配用于其他用途。
链表：与 完全一样，但是链表中保存的是没有剩余可用页面的区段。当 链表中的某个区段变满（所有页面均已使用）时，区段便会从 链表 移动到 链表，如果其中有页面被释放，这些区段就会被移回 链表，因为它们不再满了。
链表：链表中的区段均为完全未使用的区段，且可用于按照整个区段来整体。 区段可以分配给一个文件段（并放置在适当的 列表中），或者移动到 链表中按照“碎片”方式分配页面使用。
文件段和 inodes
文件段和 可能是 中术语和文档最模糊的地方。 重载了文件系统中常用的术语 ，将其用于 条目（单个小结构）和 页面（包含许多 条目的页面）。暂且不考虑命名的混乱， 中的一个 条目仅描述一个文件段（通常称为 ），下文中我们将称之为“文件段”。包含这些信息的 页具有以下结构:
每个 页包含个 文件段 条目（对于大小的页），每个条目都是个字节。此外，每个页还包含一个链表节点，该节点可用于组成下面两个 页面链表：
：至少有一个空闲 条目 的 页面 组成的链表。
：没有空闲 条目 的 页面 组成的链表。当使用“”类型表空间时，每个表空间中的这个列表将是空的，除非表有超过 个索引，因为每个索引正好消耗两个文件段 条目。
页面链表的基节点存储在上文提到的 页面的 结构中。
一个文件段 条目具有以下结构:
文件段 条目 中非列表字段的用途如下:
，文件段 ：该 文件段 条目 描述的文件段（）的 。如果 为 ，则表明该条目未使用。
，魔数： 固定存储 作为该 文件段条目 已正确初始化的标记。
， 链表中已经使用的页面数：与空间的 链表（保存在中）类似，该字段存储的是 链表中已使用的页面数，以便能够快速计算出链表中的空闲页面数而不需要遍历链表中的所有区段并求和。
，碎片页面数组：来自空间的 链表或 链表 中的“碎片”区段中的个单独分配的页面的页码数组。一旦这个数组变满，就只能将完整的区段分配给文件段。
随着表的增长， 首先为每个文件段中分配单独的页面，直到文件段中的碎片页面数组变满，然后改为一次分配 个区段，最终一次分配 个区段。
每个 文件段条目 中同样包含区段描述符链表的基节点：
链表：包含分配给此文件段且完全空闲的区段。
链表：包含分配给此文件段且至少有一个已用页面的区段。当最后一个空闲页被使用，该区段将移动到链表中。
链表：包含分配给此文件段的已经没有空闲页的区段。如果其中某个区段中有页面变为空闲，则该区段将移动到列表中。
如果链表的某个区段中的最后一个使用的页面被释放，其实该区段可以移动到文件段的链表，但实际上该区段会直接被移回空间的链表。
索引如何使用文件段
虽然我们还没有介绍 页面，但现在可以看看其中一个小方面。每个索引的根页面中包含指向 文件段 条目 的指针，这些条目描述了索引使用的文件段。每个索引的 叶子 页面 使用一个文件段，非叶叶子（内部）页面使用一个文件段。这些信息存储在 结构中（这是 页面中的一个结构）：
其中存储的有点多余———它们将始终与当前空间相同。 和 指向页面中的 文件段 条目。这两个文件段将始终存在，即使它们可能完全为空。
例如，在新创建的表中，唯一存在的页只有根页面，它也是一个叶子节点页面，但存在于“内部[]”文件段中（这样新增数据时就可以不必再移动它）。“叶[]”文件段的 链表 和 碎片页面数组 都为空。“内部”文件段的 链表也为空，唯一已经分配的根页面存在于碎片页面数组中。
把这一切联系在一起
下面这张图将索引的整个多级结构联系在了一起：
索引根页面指向两个文件段，每个文件段都有一个碎片页面数组（指向碎片页面链表中的单独的页面，最多 个），以及几个完整区段的链表，这些链表通过区段描述符中的链表节点指针链接在一起。区段描述符用于引用区段以及跟踪区段内的空闲页。很简单！
下一步是什么
接下来，我们将从用户的角度来看看中最重要的页面类型之一， 页面的结构。然后我们将看看 如何在宏观上构建索引。