InnoDB 数据页结构

Posted on 2020-07-06 In 数据库

InnoDB 有很多页类型，数据页的页类型为 B-tree Node，存放的是表中行的实际数据。InnoDB 的数据页由 7 部分组成，其中文件头（File Header）、页头（Page Header）和文件尾（File Trailer）的大小是固定的，分别为 38、56 和 8 个字节，这些空间用来标记该页的一些信息。行记录（User Records）、Free Space（空闲空间）和页目录（Page Directory）的大小是动态的，这些空间为实际的行记录存储空间。

在页的 7 个组成部分中，行记录会按照我们指定的行格式存储到 User Records 中。但是在一开始生成页的时候，其实并没有 User Records 这个部分，每当我们插入一条记录，都会从 Free Space，也就是尚未使用的存储空间中申请一个记录大小的空间划分到 User Records，当 Free Space 的空间全部被 User Records 使用后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页了。

行记录在页中的分配

文件头

File Header 用来记录页的一些头信息，共由 8 个部分组成，共占用 38 个字节。不同类型的页的第一个部分都是文件头。

名称	大小	描述
FIL_PAGE_SPACE_OR_CHKSUM	4	MySQL 4.0.14 之前为 0，之后的版本中该值代表页的 checksum 值（总和检验码）
FIL_PAGE_OFFSET	4	页号，表空间中页的偏移值，起始值为 0。如果某独立表空间 a.ibd 的大小为 1 GB，如果页的大小为 16 KB，那么总共有 65536 个页。偏移值代表该页在所有页中的位置。同时通过该部分的长度 4 个字节可以算出一个表空间最大支持 `2^32 * 16 KB = 64 TB`
FIL_PAGE_PREV	4	上一页的页号，B+Tree 的特性决定了叶子节点必须是双向列表
FIL_PAGE_NEXT	4	下一页的页号，B+Tree 的特性决定了叶子节点必须是双向列表
FIL_PAGE_LSN	8	最后被修改的日志序列的 LSN（Log Sequence Number）
FIL_PAGE_TYPE	2	页的类型，数据页对应的类型为 FIL_PAGE_INDEX，值为 0x45BF
FIL_PAGE_FILE_FLUSH_LSN	8	仅在系统表空间的一个页中定义，代表文件成功刷新到磁盘的 LSN。独立表空间中该值都是 0
FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID	4	从 MySQL 4.1 开始，该值代表页属于哪个表空间（存放的是表空间 ID）

InnoDB 是以页为单位存放数据的，有时候我们存放某种类型的数据占用的空间非常大，InnoDB 可能不会一次性为这么多数据分配一块非常大的存储空间，如果分散到多个不连续的页中存储的话就需要把这些页关联起来，使用 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 就可以建立一个双向链表把许许多多的页就串联起来，而无需它们在物理上真正连续。需要注意的是，并不是所有类型的页都有这两个属性。

页头

Page Header 用来记录数据页的状态信息，由 14 个部分组成，共占用 56 个字节。

名称	大小	描述
PAGE_N_DIR_SLOTS	2	在 Page Directory 中 Slot 的数量
PAGE_HEAP_TOP	2	堆中第一个记录的指针（记录在页中是以堆的形式存放的），该地址之后就是 Free Space
PAGE_N_HEAP	2	堆中的记录数（包括最小记录和最大记录以及标记为删除的记录），但是第 15 位表示行记录格式
PAGE_FREE	2	指向可重用空间的首指针，即第一个标记为删除的记录的地址（已删除的记录通过 next_record 组成一个链表），如果这个页上有记录要插入，可以先从这里分配空间，如果空间不够，再从 Free Space 分配。
PAGE_GARBAGE	2	已删除的字节数，即行记录中 delete_mask 为 1 的记录大小的总和
PAGE_LAST_INSERT	2	最后插入记录的位置（指向最近一个被插入的记录，主要用来方便后续的插入操作）
PAGE_DIRECTION	2	最后一个记录插入的方向。假如新插入的一条记录的主键值比上一条记录的主键值大，那么这条记录的插入方向是从右插入，反之则是从左插入。
PAGE_N_DIRECTION	2	一个方向连续插入的记录个数，如果最后一条记录的插入方向发生了改变，那么这个该值会被清零重新统计
PAGE_N_RECS	2	该页中记录的数量（不包括最小记录和最大记录以及标记为删除的记录)
PAGE_MAX_TRX_ID	8	修改当前页的最大事务 ID，该值仅在二级索引中定义
PAGE_LEVEL	2	当前页在索引树中的位置，0x00 代表叶子节点，即叶子节点总是在第 0 层
PAGE_INDEX_ID	8	索引 ID，表示当前页属于哪个索引
PAGE_BTR_SEG_LEAF	10	B+树数据页非叶子节点所在段的 segment header。该值仅在 B+树的 Root 页中定义
PAGE_BTR_SEG_TOP	10	B+树数据页所在段的 segment header。该值仅在 B+树的 Root 页中定义

最小记录和最大记录

在 InnoDB 中，每个数据页中都有两个虚拟的行记录，用来限定记录的边界。Infimum 记录比该页中任何记录都要小（对比主键值），而 Supremum 记录则比该页中任何可能大的记录都要大。这两个记录在页创建的时候建立，且在任何情况下都不会被删除。在 Compact 行格式和 Redundant 行格式中，两者占用的字节数不同。

最小记录和最大记录

这里需要提到行记录中的 next_record。它表示从当前记录的真实数据到下一条记录的真实数据的地址（即记录头信息和列数据的中间位置）偏移量。比如第一条记录的 next_record 为 32，那么就表示从第一条记录的真实数据的地址处向后找 32 个字节就是下一条记录的真实数据地址。同时需要注意的是，下一条记录并不是按照插入顺序，而是按照主键值由小到大的顺序，Infimum 记录的下一条就是本页中主键值最小的用户记录，而本页中主键值最大的用户记录的下一条就是 Supremum 记录。为了展示清楚，这里先创建一张表。

CREATE TABLE page_demo (
    c1 INT,
    c2 INT,
    c3 VARCHAR(10000),
    PRIMARY KEY (c1)
) ENGINE = InnoDB CHARSET = ascii ROW_FORMAT = Compact;

INSERT INTO page_demo VALUES (1, 100, 'aaaa'), (2, 200, 'bbbb'), (3, 300, 'cccc'), (4, 400, 'dddd');

next_record

用户记录和空闲空间

User Records 就是实际存储行记录的部分，Free Space 指的是空闲空间，它是一个链表结构。在一条记录被删除后，该记录的空间会加入到空闲链表中（与其说是加入，不如说是先从可重用链表中分配空间，空间不足再从空闲空间分配）。

页目录

我们知道记录在页中是按照主键值从小到大的顺序组成了一个单链表，如果我们想根据主键值查找页中的某条记录，那么最笨的办法就是从 Infimum 记录开始，沿着链表向后查找（next_record）。这种线性查找的方式在页中存储了很多条记录时性能较差，InnoDB 的设计者们实现了一种更好的查询方式。

他们将页中所有的记录（包括最大和最小记录，但不包括标记为已删除的记录）划分为几个组。每个组的最后一条记录，也就是组内最大的那条记录的头信息中的 n_owned 属性表示组内一共有几条记录。最后将每个组的最后一条记录的地址偏移量（页面从 0 开始数，到该记录时的字节数）单独提取出来按照顺序存储到页目录中，页目录中的这些地址偏移量也被称为槽（Slot）。

页目录

在这个页目录中有两个槽，0 号槽的值为 99，代表最小记录的地址偏移量，1 号槽的值为 112，代表最大记录的地址偏移量。在最小记录的头信息中，n_owned 的值为 1，表示该分组中只有 1 条记录，也就是最小记录本身。最大记录的头信息中，n_owned 的值为 5，表示该分组中有 5 条记录。

InnoDB 中规定，对于最小记录所在的分组只能有 1 条记录，对于最大记录所在的分组拥有的记录数只能在 1 到 8 条之间，剩下的分组中记录的条数只能在 4 到 8 条之间。即在初始情况下，数据页中只有最小和最大两条记录，它们分为两个组。之后每插入一条记录，都会从页目录中找到主键值比插入记录的主键值大且差值最小的槽（确定该记录应该处于哪个分组中），然后把该槽对应记录的 n_owned 值加 1，直到该组中的记录数等于 8 个。接下来再插入记录时，会将最大记录所在的组拆分成两个，新分离出来的组中有 4 条记录，最大记录所在的组中有 5 条记录。接着上面的例子，我们再插入多条数据。

页目录分组

接下来我们再看一开始提出的问题，在页中查找指定主键值对应的记录。由于各个槽对应的记录的主键值都是按照从小到大的顺序排列的，因此我们可以用二分法进行快速查找。有 0 到 4 共五个槽，初始情况下最小的槽 low = 0，最大的槽 high = 4，假设需要查找的主键值为 6。那么首先计算中间槽的位置：(0 + 4) / 2 = 2，查看 2 号槽中对应的主键值为 8，而 6 又小于 8，所以设置 high = 2，low 保持不变。然后重新计算中间槽的位置为 1，查看槽位对应的主键值为 4，所以设置 low = 1，high 保持不变。由于此时 high 与 low 的差值为 1，所以可以确定主键值为 6 的记录在 2 号槽对应的分组中。此时可以从 1 号槽最大的记录向后查找，该条记录的下一条就是 2 号槽的最小记录，直到找到为止。

所以在一个数据页中查找指定主键值的记录可以分为两个步骤：首先通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最小的那条记录。接下来就可以通过该记录的 next_record 属性遍历所在分组的各个记录，直到找到为止。同时需要牢记的是，B+树索引本身并不能找到具体的一条记录，能找到的只是该记录所在的页。数据库把页载入内存，然后通过 Page Directory 再进行二叉查找。而在内存进行二分查找是很快的，通常会忽略这部分查找的时间开销。

文件尾

数据在内存中被修改后再同步回磁盘，这个同步的过程相对较慢。如果在同步过程中出现了异常情况，比如机器宕机、断电、磁盘损坏等，数据就有可能会丢失。因此为了检测页的完整性，InnoDB 在页中设置了 File Trailer。文件尾中只有一个 FIL_PAGE_END_LSN，占用 8 个字节。前 4 个字节代表该页的 checksum 值，后 4 个字节与 File Header 中的 FIL_PAGE_LSN 相同。InnoDB 通过将这两个值与 File Header 中的 FIL_PAGE_SPACE_OR_CHKSUM 和 FIL_PAGE_LSN 进行比较（checksum 的比较需要使用 checksum 函数，不是简单的等值比较），看是否一致，以此来保证页的完整性。

参考

《MySQL 技术内幕：InnoDB 存储引擎》