InnoDB表空间之区的概念

1. 前言

目前为止我们已经知道，「行格式」决定了记录在磁盘中的存储格式，记录通过头信息里的指针串联成单向链表。为了更好的管理记录，InnoDB 使用「页」为基本单位来存储记录，页与页之间串联成双向链表。同时，为了提高记录的检索效率，InnoDB 借鉴了页中 Page Directory 的设计，给所有叶子节点页建立目录项记录，存储在内节点中，以此来构建一棵树，也就是我们熟悉的 B+树索引。

这一切看起来好像都没有问题，InnoDB 可以正常工作，但是在性能上会存在一些问题。我们往表中插入记录，本质上是往聚簇索引 B+树和二级索引 B+树插入记录，往这些树插入记录本质上是往树的节点插入记录，树的每一个节点都对应一个索引页。页的 File Header 部分有PREV和NEXT指针记录上一个页和下一个页的页号，以此来构建双向链表，这样就可以使得逻辑上相邻的页，在物理上可以不连续。但也会带来一个问题，如果 InnoDB 以页为基本单位来申请磁盘空间，那么很可能会导致逻辑上相邻的页在物理上距离很远，这必然会导致大量的随机 IO，机械硬盘的随机 IO 性能是很差的，磁头每次都需要重新寻址。为了解决这个问题，InnoDB 才引入了区、组、段的概念，致力于将逻辑上相邻的页在物理上也尽可能的相邻，将随机 IO 尽量转化为顺序 IO。注意，这里说的是“尽量”，InnoDB 会尽量保证页连续，即使不连续也可以正常工作，只是性能会差一点。

2. 表空间

InnoDB 支持多种表空间：

系统表空间
独立表空间
undo 表空间
临时表空间
通用表空间

其中系统表空间和独立表空间可以用于存储我们的表数据和索引数据，因此我们重点关注。系统表空间对应文件系统里的一个或多个文件，默认情况下，InnoDB 会有一个共享表空间ibdata1，所有的数据都存放在这个表空间里，查看系统表空间配置的命令：

SHOW VARIABLES LIKE 'innodb_data_file_path';
结果: ibdata1:12M:autoextend

可以看到，默认的系统表空间对应磁盘上的 ibdata1 文件，默认初始大小是 12M，这也太小了，没多少数据就装满了。别担心，后面的autoextend代表它是一个自增长文件，容量不够用了会自动扩容。

另外，你也可以通过参数innodb_file_per_table为每个表单独创建表空间，也就是独立表空间，查看是否开启独立表空间的命令如下：

SHOW VARIABLES LIKE 'innodb_file_per_table';
结果: NO

笔者的 MySQL 实例是开启了独立表空间的，这么一来 InnoDB 就会为每个表单独创建表名.frm和表名.ibd两个文件。前者是表结构定义文件，通常很小，后者用来存储表中的数据和索引，会随着记录数的增多而变大。

简单总结：系统表空间对应着文件系统上的一个或多个文件，独立表空间对应着表名.ibd文件，大家可以把表空间看作是一个许多页的大池子，当我们需要插入数据时，就会从这个池子里拿出一些页来使用。

3. 区的概念

前面已经说过，InnoDB 通过页来管理数据没什么不妥，也可以正常工作，只是性能不太理想，因为逻辑上相邻的页物理上可能距离很远，导致大量的随机 IO。为了改善这个问题，InnoDB 引入了区(extent)的概念。

InnoDB 规定，物理上连续的 64 个页就是一个区，即一个区的大小是16KB*64=1MB，无论是系统表空间还是独立表空间，都是由若干个连续的区组成的。连续的 256 个区就是一个组，即一个组的大小是 256MB。有了区以后，InnoDB 就可以以「区」为单位来给表中的数据和索引分配空间了，当表中数据量很大时，甚至会一次性分配好几个连续的区，这么做的好处就是这些页在物理上也是连续的，随机 IO 可以优化为顺序 IO，缺点是可能这些页用不完，有点浪费空间，不过总的来说是值得的。

InnoDB 将「区」分为四种状态，分别是：

状态名	说明
FREE	空闲区
FREE_FRAG	有空闲页面的碎片区
FULL_FRAG	没有空闲页面的碎片区
FSEG	隶属于某个段的区

段是一个逻辑上的概念，一棵 B+树会有两个段，分别是叶子节点段和非叶子节点段。后面的文章会详细介绍段，这里先跳过。

只有FSEG状态的区直接隶属于段，其它三种状态的区只属于表空间，不属于任何段。段隶属于表，更准确点说，段隶属于某个具体的 B+树索引，也就是说，一旦某个区状态为FSEG，那就意味着它里面的页只会存储这棵 B+树的记录。

一张表最少有一棵 B+树，也就是最少有 2 个段，每个段分配一个区，也就意味着即使表里只有 1 条记录也会占用 2MB 的空间，这未免也太浪费了，为了解决这个问题，InnoDB 采用“先分配零散页再分配区”的策略，所以，InnoDB 为表记录分配空间的策略是这样的：一开始，所有的区都是隶属于表空间的 FREE 状态，当我们向表中插入记录时，InnoDB 会拿出一个 FREE 区，并把它的状态改为 FREE_FRAG，然后从区里拿出一个页来存储记录，当区里没有空闲空间了就会把它的状态改为 FULL_FRAG，然后继续拿 FREE 区重复前面的过程。此时表的数据相当于是零散的存储在这些碎片区的，我们暂且称这些页为「零散页」，当某个段占用的零散页数量超过 32 时，InnoDB 将不再以页为单位分配空间了，而是以区为基本单位，这样就避免了少量数据也会占用 2 个区的问题。

3.1 XDES Entry

如何知道某个区隶属于哪个段呢？以及区里页的使用情况？为了更好的管理区，InnoDB 会为每个区创建一个 XDES Entry 节点，每个 XDES Entry 节点占用固定的 40 个字节，结构如下表：

名称	大小	说明
Segment ID	8Byte	所属的段 ID
List Node	12Byte	XDES Entry 形成双向链表的指针
State	4Byte	区的状态(共 4 种)
Page State Bitmap	16Byte	区内页的状态位图

List Node

List Node 由两个指针组成，用于将多个 XDES Entry 节点串联成双向链表，结构如下：

名称	大小	说明
Prev Node Page Number	4 字节	上一个 XDES Entry 节点所在的页号
Prev Node Offset	2 字节	上一个 XDES Entry 节点在页内的地址偏移量
Next Node Page Number	4 字节	下一个 XDES Entry 节点所在的页号
Next Node Offset	2 字节	下一个 XDES Entry 节点在页内的地址偏移量

XDES Entry 也是存储在页里的，通过页号+地址偏移量就可以快速定位到具体的 XDES Entry 节点。默认页大小 16KB，2 字节记录地址偏移量够用了。Tips：组由 256 个连续的区组成，对应着 256 个 XDES Entry 节点，这些 XDES Entry 节点会被固定的存储到组内的第 1 个页里，物理结构上是连续的，压根就不需要指针，该指针是根据区的 State 串联起来的逻辑上的一个链表。

Page State Bitmap

记录了区内 64 个页面是否空闲，占用 16 字节，也就是 128 位。每 2 个位代表一个页，第 1 位表示对应的页是否空闲，第 2 位暂时还没使用。

3.2 XDES 页

组由 256 个连续的区组成，也就对应着 256 个 XDES Entry 节点，那这些节点存储在哪里呢？我们之前说过，InnoDB 为了不同的目的，设计了很多不同类型的页，其中就包括专门用来存储 XDES Entry 节点的页，页类型是FIL_PAGE_TYPE_XDES，简称 XDES 页，它的页结构如下所示：

名称	大小	说明
File Header	38 字节	所有页的通用文件头信息
Empty Space	112 字节	没有使用
XDES Entry	40*256 字节	256 个 XDES Entry 节点
Empty Space	5986 字节	没有使用
File Trailer	8 字节	所有页的通用文件尾信息，校验页是否完整

XDES 页固定为每个组的第 1 个页面，也就是说，每个组都会拿出最前面的一个页面来记录组内 256 区对应的 XDES Entry 节点。

表空间第一个组的第 1 个页面类型为FIL_PAGE_TYPE_FSP_HDR，它和 XDES 页极为相似，只是多了 File Space Header 部分来记录表空间相关的状态信息。

3.3 XDES Entry 链表

现在我们已经知道，当表中数据很少时，InnoDB 会先从隶属于表空间的碎片区来分配零散页。当段使用的零散页数量超过 32 开始以区为单位来分配空间。这里有两个问题：

如何知道表空间里哪些区是 FREE？哪些是 FREE_FRAG？
隶属于段的 FSEG 区，哪些是有空闲空间的？哪些是未使用的？

这两个问题其实本质是一样的，解决方式也是一样的。当然，遍历所有的 XDES Entry 也是一种解决方案，只不过这种方案太笨了，当表中数据达到 1GB，XDES Entry 数量就上千了，遍历的效率太低了，InnoDB 当然不会这么做。还记得 XDES Entry 的 List Node 部分吗？它是两个指针，可以把多个 XDES Entry 构建成双向链表。我们可以根据区的 State 来构建链表，那么隶属于表空间的区就会形成三条链表：

FREE 链表：将所有 FREE 区串联起来的链表。
FREE_FRAG 链表：将所有 FREE_FRAG 区串联起来的链表。
FULL_FRAG 链表：将所有 FULL_FRAG 区串联起来的链表。

如此一来，当我们要分配零散页时，就从 FREE_FRAG 链表中拿出一个区开始分配，这个区用完了就将它的状态改为 FULL_FRAG，然后从 FREE_FRAG 链表移除并添加到 FULL_FRAG 链表。重复前面的过程，当 FREE_FRAG 链表没有可用的区了，就从 FREE 链表拿出一个区并把它的状态改为 FREE_FRAG，同时加入到 FREE_FRAG 链表，再重复前面的操作。

再来看第二个问题，本质是一样的，还是将 FSEG 区根据 State 串联成链表。一棵 B+树有两个段，叶子节点和非叶子节点是分开存储的，每个段又对应三条链表：

FREE 链表：隶属于同一个段的所有未使用的区自动加入到该链表。
NOT_FULL 链表：隶属于同一个段所有已使用但还有空闲空间的区自动加入到该链表。
FULL 链表：隶属于同一个段所有已经用完没有空闲空间的区自动加入到该链表。

分配方式和表空间的链表一样，这里不再赘述了。

也就是说，当我们创建一张只有主键没有二级索引的表，它内含了 9 条 XDES Entry 链表。隶属于表空间的三条，主键索引 B+树的两个段各三条，一共 9 条。

3.4 链表基节点

一张只包含主键的最简单的表也会有 9 条 XDES Entry 链表，当我们向表中插入记录时，就需要找到对应的链表，从区里面取出页来存储记录，那如何找到这些链表呢？

为了解决这个问题，InnoDB 设计了一个叫作「List Base Node」(链表基节点)的结构，每个链表基节点占用固定的 16 字节，结构如下：

名称	大小	说明
List Length	4 字节	链表节点总数
First Node Page Number	4 字节	链表头 XDES Entry 节点所在页的页号
First Node Offset	2 字节	链表头 XDES Entry 节点所在页的地址偏移量
Last Node Page Number	4 字节	链表尾 XDES Entry 节点所在页的页号
Last Node Offset	2 字节	链表尾 XDES Entry 节点所在页的地址偏移量

链表基节点结构很简单，前 4 个字节记录链表里的节点数量，后 12 个字节指向头尾节点。另一个问题又来了，链表基节点又存在哪里呢？

我们已经知道，XDES Entry 链表有两类，一种是隶属于表空间的，一种是隶属于段的。隶属于表空间的 XDES Entry 链表基节点存放在表空间第 1 组的第 1 个页面的File Space Header里，16*3个字节存储了三个链表基节点，分别指向前面说的三条链表。InnoDB 会为每个段创建一个INODE Entry节点，隶属于段的 XDES Entry 链表基节点自然也就存放在 INODE Entry 节点里了，占用16*3个字节，三个链表基节点分别指向前面说的三条链表。

4. 总结

InnoDB 索引页通过两个指针将逻辑上相邻的页串联成双向链表，使得这些索引页不需要物理上连续，但是可能会导致逻辑上相邻的页物理上距离很远，这样在读取数据时就会导致大量的随机 IO。为了将随机 IO 尽可能的优化为顺序 IO 来提升性能，InnoDB 引入了区、组、段的概念。物理上连续的 64 个页为一个区，连续的 256 个区为一组。如此一来，InnoDB 就可以以“区”为单位分配空间了。为了更好的管理这些区，InnoDB 会为每个区都创建一个 XDES Entry 节点，这些节点被专门存放在 XDES 页中，固定为每个组的第 1 个页。通过 XDES Entry 节点就可以知道区属于哪个段、区内页面的使用情况，以及将区按照 State 串联成链表，方便 InnoDB 更快的查找指定 State 的区。XDES Entry 节点根据页的使用情况可以拆分成三条链表，为了找到这些链表，InnoDB 专门设计了「链表基节点」结构，它记录了链表的节点数和头尾节点指针。这些链表基节点如果是隶属于表空间的，会存放在表空间第 1 组的第 1 个页面里；如果是隶属于段的，会存放在段对应的 INODE Entry 节点里。均占用16*3字节，分别指向了三条不同状态的链表。如此一来，当 InnoDB 要为记录分配零散页时，就去表空间对应的链表里的找到碎片区并进行分配；当段占用的零散页个数超过 32 时，InnoDB 就去段对应的链表里找到有空闲页的区并进行分配。