InnoDB表空间之段的概念

1. 前言

通过前面的文章，我们已经知道了索引页的结构可以使得它们不用在物理上连续也能正常工作，只是不连续会导致大量的随机 IO 性能较差，为了解决这个问题 InnoDB 引入了区的概念，物理上连续的 64 个页就是一个区，这样 InnoDB 就可以以“区”为单位来分配空间了。同时，为了避免少量数据也占用 2 个区的问题，InnoDB 采取先零散页后完整区的分配策略，当某个段使用的零散页数量超过 32 时，开始以区为单位进行分配。

介绍区时我们稍微提到了“段”的概念，但没有细讲，今天的文章我们重点分析。先提几个问题：

为什么一棵 B+树会有两个段？
为什么使用的零散页数量超过 32 才开始分配完整区？
段的三条 XDES Entry 链表基节点保存在哪里？
段对应的 INODE Entry 节点又保存在哪里？

2. 段的概念

相较于区，段(Segment)只是一个逻辑上的概念，段是由一些零散页和若干个区组成的。一棵 B+树索引对应两个段，分别是叶子节点段和非叶子节点段，也就是说，对于用户记录和目录项记录，InnoDB 是分开存储的，为什么要这么做呢？很多查询场景下，InnoDB 都需要顺序的扫描叶子节点的记录，如果一个区里既存储用户记录，又存储目录项记录，那么这个顺序扫描的性能就会受到影响，所以 InnoDB 才给一棵 B+树分配了两个段。

为了更好的管理这些段，InnoDB 给每个段都创建了一个INODE Entry节点，每个节点占用固定的 192 字节，结构如下：

名称	大小	说明
Segment ID	8 字节	每个段都有唯一一个 ID
NOT_FULL_N_USED	4 字节	NOT_FULL 链表已经使用的页面数量
List Base Node * 3	16 字节 * 3	三条 XDES Entry 链表基节点
Magic Number	4 字节	魔数，固定值，标记节点是否初始化。
Fragment Array Entry * 32	4 字节 * 32	32 个零散页的页号

Segment ID

每个段都有唯一一个 ID，如果区隶属于某个段，那么 XDES Entry 里的 Segment ID 和这里一致。

NOT_FULL_N_USED

记录该段的 NOT_FULL 链表里已经使用了多少个页。

List Base Node

隶属于段的区对应的 XDES Entry 会根据区内页的使用情况自动串联成三条链表，分别是 FREE 链表、NOT_FULL 链表、FULL 链表，每条链表对应一个链表基节点 List Base Node，基节点记录了链表的页面数量和头尾节点指针。

Fragment Array Entry

段由 32 个零散页和若干个区组成，区会形成三条链表，另外的 32 个零散页就存储在这里，记录的是页号，所以你现在知道为啥是 32 个零散页了吧？

看完 INODE Entry 的结构，是不是有一种豁然开朗的感觉，这已经回答了前面三个问题了。第 4 个问题，这些 INODE Entry 节点存储在哪里呢？

2.1 FIL_PAGE_INODE

InnoDB 为了不同的目的设计了很多不同类型的页，比如有存放记录的索引页，有存放 XDES Entry 的 XDES 页。为了存放 INODE Entry，InnoDB 专门设计了FIL_PAGE_INODE页，简称“INODE 页”，页结构如下：

名称	大小	说明
File Header	38 字节	所有页的通用文件头信息

List Node for INODE Page List

由于页大小的限制，一个 INODE 页最多只能存储 85 个 INODE Entry 节点，当表中段特别多的时候，一个 INODE 页是存储不下的，InnoDB 会使用多个页来存储，为了管理这些 INODE 页，InnoDB 使用该属性将这些页串联成两条链表：SEG_INODES_FULL 链表和 SEG_INODES_FREE 链表，前者代表页已用完，后者代表页还空闲。

INODE Entry

85 个 INODE Entry 节点，紧凑的排列在一起，一共占用 16320 个字节。

第一个 INODE 页固定存储在独立表空间的第 1 个组的第 3 个页面里，第 1 组的第 1 个页面存储的是 XDES Entry。

2.2 INODE Entry 链表基节点

我们已经知道，一个页最多存储 85 个 INODE Entry 节点，当表中段特别多时只能使用多个页面来存储了，这些页面会根据空闲情况串联成 FREE 和 FULL 两条链表，那么 InnoDB 如何找到这两条链表呢？

和 XDES Entry 一样，InnoDB 也为 INODE Entry 链表设计了链表基节点，每个基节点占用固定的 16 字节，结构和 XDES Entry 链表基节点一样，4 字节存储链表节点数，12 字节存储头尾节点指针。一张表对应两条 INODE Entry 链表，也就是说需要两个 INODE Entry 链表基节点，这俩基节点存储在哪里呢？独立表空间的第 1 个组的第 1 个页面是固定的，页类型是FIL_PAGE_TYPE_FSP_HDR，它有一个叫File Space Header的部分，占用 112 字节，最后的 32 个字节分别用来存储 INODE Entry FULL 链表基节点和 FREE 链表基节点。

还有印象吗？这里还存储了隶属于表空间的三条 XDES Entry 链表基节点。

如此一来，InnoDB 就可以很轻松的访问到这两条链表了，因为链表基节点位置是固定的。InnoDB 每创建一个段都会创建一个对应的 INODE Entry 节点，节点的存储过程是这样的：如果 SEG_INODES_FREE 链表不为空，则取出一个空闲页面存储节点，页面满了则将其从链表中移除并添加到 SEG_INODES_FULL 链表。如果 SEG_INODES_FREE 为空，则从表空间的 FREE_FRAG 中申请一个页面，将页面类型改为 INODE，然后加入到 SEG_INODES_FREE 链表使用，重复前面的流程。

2.3 Segment Header

一棵 B+树索引对应两个段，每个段对应一个 INODE Entry，当我们向 B+树插入记录需要申请空间时，首先必须要找到这棵 B+树对应的两个段，才能找到隶属于段的空闲区。现在的问题是，InnoDB 如何找到 B+树对应的段呢？

大家还记得索引页的结构吗？索引页有一个Page Header部分，里面有 20 个字节非常重要，如下：

名称	大小	描述
PAGE_BTR_SEG_LEAF	10 字节	B+树叶子段的头部信息，仅在 B+树的 Root 页定义
PAGE_BTR_SEG_TOP	10 字节	B+树非叶子段的头部信息，仅在 B+树的 Root 页定义

一棵 B+树的根节点页的 Page Header 部分，会使用 20 个字节，分别记录该索引对应的叶子节点段和非叶子节点段信息，这个结构被叫作「Segment Header」，每个 Segment Header 占用固定的 10 字节，如下：

名称	大小	描述
Space ID of the INODE Entry	4 字节	INODE Entry 节点所在表空间 ID
Page Number of the INODE Entry	4 字节	INODE Entry 节点所在页的页号
Byte Offset of the INODE Entry	2 字节	INODE Entry 节点所在页的地址偏移量

如此一来，InnoDB 就可以根据 B+树的根节点页面，知晓两个段对应的 INODE Entry 所在的页面和地址偏移量，从而快速定位到准确的 INODE Entry 节点，找到隶属于区的空闲页就不再是难事了。

3. 总结

段是一个逻辑上的概念，它由 32 个零散页和若干个区组成。一棵 B+树索引对应两个段，分别是叶子节点段和非叶子节点段，之所以将用户记录和目录项记录分开存储，是因为大多数查询场景，InnoDB 需要顺序扫描叶子节点的记录，如果两者混合存储在同一个区里，就会影响扫描的效率。InnoDB 为了更好的管理段，会为每个段创建一个 INODE Entry 节点，这些节点统一存储在表空间的第 1 组的第 3 个页面里，页面类型是FIL_PAGE_INODE，一个页最多存储 85 个 INODE Entry，所以多个 INODE 页会根据页的使用情况自动串联成 FREE 和 FULL 两条链表，链表的基节点存储在表空间第 1 组的第 1 个页的File Space Header里。为了方便找到 B+树索引对应的段，InnoDB 在 B+树索引的根页面的 Page Header 部分使用 20 个字节，分别存储叶子节点段和非叶子节点段的信息，这个结构叫作「Segment Header」，存储了 INODE Entry 节点所在表空间以及所在页的页号和地址偏移量。当 InnoDB 要为 B+树分配空间时，先从根页面找到对应的 INODE Entry，再找到隶属于当前段的 XDES NOT_FULL 链表，从空闲区里取出一个页。