[翻译] InnoDB 空间文件中的页面管理

本系列文章翻译自 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 页面，用来跟踪哪些 区段 是正在使用的，以及每个 区段 内哪些页面是正在使用的。这些页面的结构非常简单:

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

• 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]”）是一种非常通用的结构，可以将多个相关结构链接在一起。它由“链表基节点”和“链表节点”两个互补的结构共同组成了一个很好的磁盘上双向链表。“链表基节点”的结构如下:

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

文件空间头和区段列表

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

每个 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 条目具有以下结构:

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

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

把这一切联系在一起

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

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

下一步是什么

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

本文文字及图片出自 InfoQ