本系列文章翻译自 Jeremy Cole's Blog 中的 InnoDB系列 文章 。共 16 篇，本文为第 4 篇。原文链接：Page management in InnoDB space files

因翻译水品有限，为了避免对读者造成误解，一些专有名词的翻译会在其后用[]标记出原文。

InnoDB 空间文件中的页面管理

在 On learning InnoDB: a journey to the core （译文）一文中，我介绍了用来记录 InnoDB 内部结构的 innodb_diagrams 项目，本文中所使用的图表均可以在该项目中找到。

空间的基本结构以及每个页面的基本结构在 The basics of InnoDB space file layout （译文）一文已经中有所描述，接下来我们将详细描述 InnoDB 中 与 页面管理、区段管理、空闲空间管理相关的结构，以及它如何跟踪分配给不同用途的页面的使用情况。

区段和区段描述符

正如前面所描述的，InnoDB 页面通常是 16KB，并被分组为 1MB 大小的块，一块包含64个连续页面，这被称为“区段[extent]”。InnoDB 在空间内的固定位置分配 FSP_HDR 和 XDES 页面，用来跟踪哪些 区段 是正在使用的，以及每个 区段 内哪些页面是正在使用的。这些页面的结构非常简单:

它们包含通用的 FIL Header 和 FIL Trailer，一个 FSP Header（将在稍后讨论），以及 256 个“区段描述符[extent descriptors]”，还包含大量未使用的空间。

区段描述符具有以下结构:

区段描述符中各个字段的用途如下：

• File Segment ID(8)，文件段ID：如果一个区段属于文件段的话，这个字段表示该区段所属文件段的 ID
  

• List node for XDES list(12)，XDES 链表的链表节点：在区段描述符链表中指向上一个区段和下一个区段的指针

• State(4)，区段当前的的状态：目前只定义了四个值：FREE，FREE_FRAG，FULL_FRAG（这三个状态表示区段属于 FREE 链表 / FREE_FRAGE 链表 / FULL_FRAGE 链表），FSEG（这个状态表示区段属于某个文件段，文件段 ID 存储在 XDES Entry 结构中的 File segment ID 字段中）

• Page State Bitmap(16)，页面状态位图：在该区段中为每个页面分配2位的位图（64 x 2 = 128位，16字节）。第一位表示该页是否为空闲；第二个位被预留用于指示页面是否是干净[clean]的（干净的表示没有未刷新到磁盘的脏数据），但是这个位当前未使用，该位始终设置为1
  

其他结构如果要引用区段，需要使用 区段描述符所在的 FSP_HDR 页面（或 XDES 页面）的页号 和 区段描述符条目本身在页内的字节偏移量 组合来实现。例如，0号页面 偏移量 150引用的区段是空间中的第一个区段，包含页面0-63，而16384号页面 偏移量270包含页面16576-16639。

译者注：这里对第二个例子进行一下详细的计算，对于16384号页面 偏移量270，首先16384号页面是第256个区段中的第一个页面(XDES类型)，所以这个页面中记录了第256-511区段中的区段描述符，偏移量270指向的是本页面中第4个XDES条目（38+112+40x3 = 270），所以描述的是第259个区段的信息，也就是16576-16639号页面。

链表基节点和链表节点

链表（InnoDB 称之为“自由链表[free lists]”）是一种非常通用的结构，可以将多个相关结构链接在一起。它由“链表基节点”和“链表节点”两个互补的结构共同组成了一个很好的磁盘上双向链表。“链表基节点”的结构如下:

“链表基节点” 只在某些高级结构（如 FSP Header）中存储一次。它包含 链表的长度，以及指向链表中第一个和最后一个节点的指针。“链表节点”的结构看起来非常相似，只是“链表节点”中存储的不是第一个和最后一个节点的指针，而是前一个和下一个节点的指针：

所有指针都包含一个页码（必须在同一空间内）和一个可以找到链表节点的页面中的字节偏移量。所有指针都指向“链表节点”结构的起始位置（即 N+0 ），而并不一定是链表节点所属结构的起始位置。例如，在区段描述符条目链表中，由于链表节点在 XDES 条目结构中的偏移量为8，读取 XDES 条目的代码必须“知道” XDES 结构开始于列表节点的偏移量之前8个字节，并从那里开始读取结构。（确保列表节点在任何结构中都位于最前面可能是一个好主意，但事实并非如此。）

文件空间头和区段列表

除了存储区段描述符条目本身之外，FSP_HDR 页面（该页面在空间中始终是0号页面）还存储了 FSP Header 结构，它包含了大量链表，这也是我为什么没有在前面描述该结构的原因。FSP Header的结构如下:

FSP Header中与列表无关的字段（不按顺序排列）：

• Space ID(4)：当前空间的空间 ID

• Highest page number in the space (size)(4)：size表示最高的有效页码，并且随文件增长递增。但是，并非所有分配了页码的页都被初始化了（有些可能是被零填充的），因为空间的扩展是一个包含很多步骤的过程

• Highest page number initialized (free limit)(4)，free limit是所有FIL header已经被初始化的所有页面中的最大页码，初始化过程中包含将页码存储在页面自身中。free limit始终小于或等于size。

• Flags(4)：储存与空间有关的标记

• Next Unused Segment ID(8)：将被用于下一个分配的文件段的文件段 ID。（这是一个自动递增的整数。）

• Number of pages used in the FREE_FRAG list：存储这个字段是出于性能优化的考虑，以便能够快速计算 FREE_FRAG 链表中所有区段的空闲页数和，而无需遍历链表中的所有区段并对每个区中可用的空闲页求和。

下列区段描述符链表的链表基节点也存储在 FSP Header 中:

• FREE_FRAG链表：该链表中的区段均为 存在空闲的页面可用于按照"碎片"方式分配 的区段，按照“碎片”方式分配的含义是可以根据不同的需要分配单独的页面，而不是分配整个区段。例如，每个具有 FSP_HDR 页面或 XDES 页面的 区段 将被放置在 FREE_FRAG 列表中，以便 区段 中剩余的空闲页面可以分配用于其他用途。

• FULL_FRAG链表：与 FREE_FRAG 完全一样，但是链表中保存的是没有剩余可用页面的区段。当 FREE_FRAGE 链表中的某个区段变满（所有页面均已使用）时，区段便会从 FREE_FRAG 链表 移动到 FULL_FRAG 链表，如果其中有页面被释放，这些区段就会被移回 FREE_FRAG 链表，因为它们不再满了。

• FREE链表：链表中的区段均为完全未使用的区段，且可用于按照整个区段来整体。 FREE 区段可以分配给一个文件段（并放置在适当的 INODE 列表中），或者移动到 FREE_FRAG 链表中按照“碎片”方式分配页面使用。

文件段和 inodes

文件段和 inodes 可能是 InnoDB 中术语和文档最模糊的地方。InnoDB 重载了文件系统中常用的术语 INODE ，将其用于 INODE 条目（单个小结构）和 INODE 页面（包含许多 INODE 条目的页面）。暂且不考虑命名的混乱，InnoDB 中的一个 INODE 条目仅描述一个文件段（通常称为 FSEG），下文中我们将称之为“文件段INODE”。包含这些信息的 INODE 页具有以下结构:

每个 INODE 页包含85个 文件段INODE 条目（对于16KB大小的页），每个条目都是192个字节。此外，每个INODE页还包含一个链表节点，该节点可用于组成下面两个 INODE 页面链表：

• FREE_INODES：至少有一个空闲 INODE 条目 的 INODE 页面 组成的链表。

• FULL_INODES：没有空闲 INODE 条目 的 INODE 页面 组成的链表。当使用“file per table”类型表空间时，每个表空间中的这个列表将是空的，除非表有超过 42 个索引，因为每个索引正好消耗两个文件段 INODE 条目。

INODE页面链表的基节点存储在上文提到的FSP_HDR 页面的 FSP Header 结构中。

一个文件段 INODE 条目具有以下结构:

文件段 INODE 条目 中非列表字段的用途如下:

• File Segment ID，文件段 ID：该 文件段 INODE 条目 描述的文件段（FSEG）的 ID 。如果 ID 为 0，则表明该条目未使用。

• Magic Number，魔数： 固定存储 97937874作为该 文件段INODE条目 已正确初始化的标记。

• Number of used pages in "NOT_FULL" list，NOT_FULL 链表中已经使用的页面数：与空间的 FREE_FRAG 链表（保存在FSP Header中）类似，该字段存储的是 NOT_FULL 链表中已使用的页面数，以便能够快速计算出链表中的空闲页面数而不需要遍历链表中的所有区段并求和。

• Fragement Array，碎片页面数组：来自空间的 FREE_FRAG 链表或 FULL_FRAG 链表 中的“碎片”区段中的32个单独分配的页面的页码数组。一旦这个数组变满，就只能将完整的区段分配给文件段。

随着表的增长，InnoDB 首先为每个文件段中分配单独的页面，直到文件段中的碎片页面数组变满，然后改为一次分配 1 个区段，最终一次分配 4 个区段。

每个 文件段INODE条目 中同样包含区段描述符链表的基节点：

• FREE链表：包含分配给此文件段且完全空闲的区段。

• NOT_FULL链表：包含分配给此文件段且至少有一个已用页面的区段。当最后一个空闲页被使用，该区段将移动到FULL链表中。

• FULL链表：包含分配给此文件段的已经没有空闲页的区段。如果其中某个区段中有页面变为空闲，则该区段将移动到NOT_FULL列表中。

如果NOT_FULL链表的某个区段中的最后一个使用的页面被释放，其实该区段可以移动到文件段的FREE链表，但实际上该区段会直接被移回空间的FREE链表。

索引如何使用文件段

虽然我们还没有介绍 INDEX 页面，但现在可以看看其中一个小方面。每个索引的根页面中包含指向 文件段 INODE 条目 的指针，这些条目描述了索引使用的文件段。每个索引的 叶子 页面 使用一个文件段，非叶叶子（内部）页面使用一个文件段。这些信息存储在 FSEG Header 结构中（这是INDEX 页面中的一个结构）：

其中存储的Space ID有点多余———它们将始终与当前空间相同。 Page Number 和 Offset 指向INODE页面中的 文件段 INODE 条目。这两个文件段将始终存在，即使它们可能完全为空。

例如，在新创建的表中，唯一存在的页只有根页面，它也是一个叶子节点页面，但存在于“内部[internal]”文件段中（这样新增数据时就可以不必再移动它）。“叶[leaf]”文件段的 INODE链表 和 碎片页面数组 都为空。“内部”文件段的 INODE 链表也为空，唯一已经分配的根页面存在于碎片页面数组中。

把这一切联系在一起

下面这张图将索引的整个多级结构联系在了一起：

索引根页面指向两个文件段，每个文件段都有一个碎片页面数组（指向碎片页面链表中的单独的页面，最多 32 个），以及几个完整区段的链表，这些链表通过区段描述符中的链表节点指针链接在一起。区段描述符用于引用区段以及跟踪区段内的空闲页。很简单！

下一步是什么

接下来，我们将从用户的角度来看看InnoDB中最重要的页面类型之一，INDEX 页面的结构。然后我们将看看 InnoDB 如何在宏观上构建索引。