InnoDB数据页结构

InnoDB为了不同的目的而设计了许多种不同种类的页，页是InnoDB存储引擎管理数据库的最小磁盘单位，默认每个页的大小为16KB；

InnoDB数据页结构

InnoDB数据页由以下7个部分组成；

参考：[https://dev.mysql.com/doc/internals/en/innodb-page-overview.html]

File Header

File Header用来记录页的一些头信息，8个部分组成，共占用38字节；

• FIL_PAGE_TYPE

这个代表当前页的类型，具体如下：

• FIL_PAGE_PREV和FIL_PAGE_NEXT

InnoDB以页为单位存放数据，有时候存放某种类型的数据占用的空间非常大，InnoDB可能不可以一次性为这么多数据分配这么大的存储空间，如果分散到多个不连续的页中，需要把这些页关联起来，FIL_PAGE_PREV和FIL_PAGE_NEXT分别代表本页的上一个和下一个页号；这样通过建立一个双向链表把这些页连接起来，而无需这些页在物理上真正连着；

注：不是所有类型的页都有上一页和下一页的属性，而类型FIL_PAGE_INDEX的页是有这两个属性的，所有的数据其实是一个双向链表，如下：

Page Header

接着File Header部分的是Page Header，该部分用来记录数据页的状态信息，由14个部分组成，共占用56字节；

• Page Header组成部分

Infimum和Supremum Record

在InnoDB存储引擎中，每个数据页中有两个虚拟的行记录，用来限定记录的边界；Infimum记录是比该页中比该任何主键值都要小的值，Supremum指比任何可能大的值还要大的值；这两个值在页创建时被建立，并且在任何情况下不会被删除；在Compact行格式和Redundant行格式下，两者占用的字节数各不相同；

User Records 和 Free Space

User Records是实际存储行记录的内容；

Free Space指的是空闲空间，是一个链表的数据结构；在一条记录被删除后，该空间会被加入到空闲链表中；

Page Directory

Page Directory（页目录）中存放了记录的相对位置（这里存放的是页相对位置，而不是偏移量），有些时候这些记录指针称为Slots（槽）或者目录槽（Directory Slots），与其他数据库系统不同的是，在InnoDB中并不是每个记录拥有一个槽，InnoDB存储引擎的槽是一个稀疏目录（sparse directory），即一个槽中可能包含多个记录；伪记录Infimum的n_owned值总是为1，而伪记录Supremum的n_owned的取值范围为[1, 8]，其他用户记录n_owned的取值范围为[4, 8]；当记录被插入或删除时需要对槽进行分裂或平衡的维护操作；

如何根据主键查找页中的某条记录，在InnoDB中的查找过程如下：

• 将所有正常的记录，包括最大和最小记录，不包括标记为已删除的记录，划分为几个组；
• 每个组的最后一条记录的头信息的n_owned属性表示该组内有几条记录；
• 而将每个分组的最后一条的地址偏移量单独提取出来按顺序存储到靠近页尾部的地方，这个地方就是Page Directory（页目录），页目录中的这些地址偏移量称为Slots（槽）或目录槽；

根据上面所说的伪记录Infimum的n_owned值总是为1，而伪记录Supremum的n_owned的取值范围为[1, 8]，其他用户记录n_owned的取值范围为[4, 8]，因此对于最小记录所在的分组只能有1条记录，最大记录所在的分组拥有的记录条数只能在1~8条之间，剩下的分组中的记录范围只能是4~8条之间；分组按照下面的步骤进行：

• 初始情况下下一个数据页里只有最小记录和最大记录两条记录，它们属于两个分组；
• 之后没插入一条记录，都会从页目录中找到主键值比本记录的主键值大并且差值最小的槽，然后把该槽对应的记录的n_owned值加1，表示本组内又添加了一条记录，直到该组中的记录数等于8；
• 在一个组中的记录数等于8个后再插入一条记录时，会将组中的记录拆分成两个组，一个组中4条记录，另一个5条记录，这个过程会在页目录中新增页目录中新增一个槽来记录这个新增分组中最大的那条记录的偏移量；

File Trailer

为了检测页是否已经完整地写入磁盘（如可能发生地写入过程中磁盘损坏，机器关机等），InnoDB存储引擎地页中设置了File Trailer部分；

File Trailer只有一个FIL_PAGE_END_LSN部分，占用8字节；前4字节代表该页的checksum值，最后4字节和File Header中的FIL_PAGE_LSN相同，将这两个值越File Header中的FIL_PAGE_SPACE_OR_CHKSUM和FIL_PAGE_LSN值进行比较，看是否一致（checksum的比较需要通过InnoDB的checksum函数来进行比较，不是简单的等值比较），以此来保证页的完整性；

分析记录在页中的存储

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

Free Space划分User Records过程如下：

行记录如何按照指定的行格式一条一条的存放在User Records？

脚本准备如下：

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

page_demo表使用的是Compact的行格式，该表的行格式示意图如下：

往page_demo表插入几条数据：

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

插入记录的示意图大致如下：

使用下面的工具分析InnoDB数据页

import os

def get_innodb_page_type():
    f=open("page_demo.ibd",'rb')
    # 计算该表空间有多少页,以一页16K计算
    fsize=os.path.getsize(f.name) // (1024 * 16)
    # 遍历页数
    for i in range(fsize):
        # 每次读16K
        page=f.read(1024 * 16)
        # 取File Header中的FIL_PAGE_OFFSET
        page_offset=page[4:(4+4)].hex()
        # 取File Header中FIL_PAGE_TYPE
        page_type=page[24:(24+2)].hex()
        # 判断是否为数据页
        if page_type == '45bf':
            page_level=page[(38+26):(38+26+2)]
            print("page offset %s, page type <%s>, page level <%s>" %(page_offset,page_type,page_level))
        else:
            print("page offset %s, page type <%s>" %(page_offset,page_type))

if __name__ == '__main__':
	get_innodb_page_type()

MySQL File Page Type：[https://dev.mysql.com/doc/internals/en/innodb-fil-header.html]

从上图可以发现第四页（page offset 3）是数据页，然后通过hexdump对page_demo.ibd文件进行分析；

数据页从0x0000c000（16K * 3 = 0xc000）处开始，得到以下内容：

分析File Header的38字节

• 62 A7 FA E0，数据页的checksum值；
• 00 00 00 03，页的偏移量，从0开始；
• FF FF FF FF，前一个页，因为这里只有一个数据页，所以为0xFFFFFFFF；
• FF FF FF FF，下一个页，因为只有当前一个数据页，所以为0xFFFFFFFF；
• 00 00 00 00 01 43 A0 1B，页的LSN；
• 45 BF，页类型，0x45BF代表数据页；
• 00 00 00 00 00 00 00 00，独立表空间为0；
• 00 00 00 CC，表空间的Space ID；

MySQL一个数据页默认为16K = 16384（16 * 1024）bit = 0x4000，而File Trailer占数据页中末尾的8字节，File Trailer起始位置为（0xC000 + 0x4000）- 0x08 = 0xFFF8；

• 62 A7 FA E0，File Trailer的前4字节代表该页的checksum值，该值通过checksum函数与File Header中数据页的checksum值比较；
• 01 43 A0 1B，该值与File Header中页的LSN的后4个值是相等的；

分析Page Header的56字节

• PAGE_N_DIR_SLOTS

PAGE_N_DIR_SLOTS = 0x0002，代表Page Directory有2个槽，每个槽占2字节；(0xC000 + 0x4000）- 0x08 - 0x02 * 2 = 0xFFF4，其中Page Directory后面是File Trailer，而File Trailer占8字节； 0xFFF4 ~ 0xFFF7如下：

Page Directory是逆序存放的，每个槽占2字节，因此00 63是最初行的相对位置，即0xC063，00 70是最后一行记录的相对位置，即0xC070，分别对应的是Infimum和Supremum；

• PAGE_HEAP_TOP 

PAGE_HEAP_TOP = 0x00F8，代表空闲空间开始位置的偏移量，在（0xC000 + 0x00F8）0xC0F8处开始，可以发现这个是最后一行的结束，接下去的部分都是空闲空间；

• PAGE_N_HEAP 

PAGE_N_HEAP = 0x8006；当行格式为Compact时，初始值为0x0802，当行格式为Redundant时，初始值为2；这些值表示页初始化时就已经有Infinimum和Supremeum的伪记录行，0x0806 - 0x0802 = 0x04，代表页初始化时就有4条记录；

• PAGE_FREE 

PAGE_FREE = 0x0000，代表可重用的空间首地址，这里没有进行过任何删除操作，因此为0；

• PAGE_GARBAGE 

PAGE_GARBAGE = 0x000，代表删除的记录字节为0，这里没有删除操作，值依然为0；

• PAGE_LAST_INSERT 

PAGE_LAST_INSERT = 0x00DF，表示页最后插入的位置的偏移量，即最后的插入位置应该在0xC000 + 0x00DF = 0xC0DF；

该位置如下：

从上图可以看出最后插入c1列值为4的行记录，直接指向行记录的内容，不是指向行记录变长字段长度的列表位置；

• PAGE_DIRECTION 

PAGE_DIRECTION = 0x0002，因为通过自增长的方式进行行记录的插入，所以PAGE_DIRECTION的方向是向右，为0x0002；

• PAGE_N_DIRECTION 

PAGE_N_DIRECTION = 0x0003，表示同一个方向连续插入的记录数，主要用来加速后续插入操作，这里是自增长插入了4条记录，因此该值为3；

• PAGE_N_RECS 

PAGE_N_RECS = 0x0004，表示当前数据页中用户的记录，不包括最大和最小记录，与PAGE_N_HEAP不同的是，如果记录被标记为delete-marked，这个值就会递减；该页的行记录数为4；

• PAGE_MAX_TRX_ID 

PAGE_MAX_TRX_ID = 0x0000000000000000，表示修改此数据页的当前最大事务ID；

• PAGE_LEVEL 

PAGE_LEVEL = 0x0000，表示这个页是否是B树中的叶子节点，如果是0，就是叶子节点；

• PAGE_INDEX_ID 

PAGE_INDEX_ID = 0x0000000000000241，表示索引页的索引ID；

• PAGE_BTR_SEG_LEAF 

PAGE_BTR_SEG_LEAF = 0x000000CC0000000200F2，表示叶子节点的段头页地址；

• PAGE_BTR_SEG_TOP 

PAGE_BTR_SEG_TOP = 0x000000CC000000020032，表示非叶子节点的段头页地址；

参考：[http://mysql.taobao.org/monthly/2018/04/03/

   https://dev.mysql.com/doc/internals/en/innodb-page-header.html]

Infimum和Supremum分析

File Header占38字节，Page Header占56字节，0xc000偏移（38 + 56）字节，得到0xc05e，即从位置0x05e开始是（Infimum + Supremum）部分的数据；

Infimum + Supremum这两个伪行记录，在InnoDB存储引擎中设置伪行只有1个列，且类型为char(8)，结果如下：

Infimum伪行记录

# Infimum伪行记录
# recorder header
01 00 02 00 1C
#只有一个列的伪行记录，行记录内容就是Infimum（多了一个0x00字节）
69 6E 66 69 6D 75 6D 00

Supremum伪行记录

# Supremum伪行记录
# record header
05 00 0B 00 00
#只有一个列的伪行记录，记录内容就是supremum
73 75 70 72 65 6D 75 6D

即在Compact行格式下，（record header + 8）* 2 = 26，其中记录头信息record header占5字节，而Infimum和Supremum各占8个字节；

行记录分析

在Infimum伪行记录的record header部分，最后两个字节为001C，表示下一个记录的位置的偏移量，即当前行记录内容的位置（0xC063）+ 下一个记录的相对位置的偏移量（0x001C）= 0xC07F；

记录头信息：00 00 10 00 20，而记录头信息占5个字节，40bit，如下：

0000 0000 0000 0000 0001 0000 0000 0000 0010 0000

第一条行记录

# 建表时设置了主键,ROWID为c1列的值1
80 00 00 01
# Transaction ID
00 00 00 00 36 D2
# Roll Pointer
B2 00 00 01 26 01 10
# c2列
80 00 00 64
# c3列
61 61 61 61

第二条记录的位置：第一条记录的行记录内容的位置（0xC07F）+ 下一个记录的相对位置的偏移量（0x20） = 0xC09F；

记录头信息：00 00 18 00 20，二进制如下：

0000 0000 0000 0000 0001 1000 0000 0000 0010 0000

第二条行记录

# 建表时设置了主键,ROWID为c1列的值2
80 00 00 02
# Transaction ID
00 00 00 00 36 D2
# Roll Pointer
B2 00 00 01 26 01 1D
# c2列
80 00 00 C8
# c3列
62 62 62 62

第三条记录的位置：第二条记录的行记录内容的位置（0xC09F）+ 下一个记录的相对位置的偏移量（0x20） = 0xC0BF；

记录头信息：00 00 20 00 20，二进制如下：

0000 0000 0000 0000 0010 0000 0000 0000 0010 0000

第三条行记录

# 建表时设置了主键,ROWID为c1列的值3
80 00 00 03
# Transaction ID
00 00 00 00 36 D2
# Roll Pointer
B2 00 00 01 26 01 2A
# c2列
80 00 01 2C
# c3列
63 63 63 63

第四条记录的位置：第二条记录的行记录内容的位置（0xC0BF）+ 下一个记录的相对位置的偏移量（0x20） = 0xC0DF；

记录头信息：00 00 28 FF 91，二进制如下：

0000 0000 0000 0000 0010 1000 1111 1111 1001 0001

而第四条记录是当前插入的最大一条记录，而本页中主键最大的用户记录的下一条记录就是Supremeum记录；

第四条行记录

# 建表时设置了主键,ROWID为c1列的值4
80 00 00 04
# Transaction ID
00 00 00 00 36 D2
# Roll Pointer
B2 00 00 01 26 01 37
# c2列
80 00 01 90
# c3列
64 64 64 64

存储情况大致如下图：

Supremum最大记录的next_record的值为0，这就说明最大记录是没有下一条记录，它是单链表中最后一个节点；

如果把其中第2条记录删除，上图会变成如下：

删除第2条记录主要发生了以下变化：

• 第2条记录并没有从存储空间中移除，而是把该记录的deleted_flag值设置为1；
• 第2条记录的next_record值变为0，即没有下一条记录；
• 第1条记录的next_record执行第3条记录；
• 最大记录的n_owned值从5变成了4；

不论怎么对页中的记录做增删改操作，InnoDB始终会维护一条记录的单链表，链表中的各个节点是按照主键值由小到大的顺序连接起来的；

而且从上面的图可以看出，next_record指向记录头信息和真实数据之间，不直接指向整条记录的开头位置是因为这个位置向左读是记录头信息，向右读是真实数据，这样可以使记录中位置靠前的字段和它们对应的字段长度信息在内存中的距离更近，可能会提高高速缓存的命中率；

再次插入主键值为2的记录，存储情况大致如下：

InnoDB并没有因为新记录的插入而为它申请新的存储空间，而是直接复用了原来被删除记录的存储空间；当数据页中存在多条被删除掉的记录时，这些记录的next_record属性将会把这些被删除掉的记录组成一个垃圾链表，以备之后重用这部分存储空间；

由于现在page_demo表中的记录太少，无法演示添加了页目录之后查找速递的过程，往page_demo表添加一些记录：

INSERT INTO page_demo VALUES(5, 500, 'eeee'), (6, 600, 'ffff'), (7, 700, 'gggg'), (8, 800, 'hhhh'), (9, 900, 'iiii'), (10, 1000, 'jjjj'), (11, 1100, 'kkkk'), (12, 1200, 'llll'), (13, 1300, 'mmmm'), (14, 1400, 'nnnn'), (15, 1500, 'oooo'), (16, 1600, 'pppp');

添加完数据后，目前数据页中有18条记录，这些记录被分成了5组，如下图：

各个槽代表的记录的主键都是从小到大排序的，这时可在页目录中使用二分查找对应的行记录；

5个编号分别是：0，1，2，3，4，初始情况下最低的槽是0，最高的槽是4，如找主键为6的记录，过程如下：

• 计算中间槽的位置：(0 + 4) / 2 = 2，槽2对应记录的主键为8，8 > 6，将high设置为2，low保持不变；
• 重新计算中间槽的位置：(0 + 2) / 2 = 1，槽1对应的主键为4，4 < 6，设置low为1，high保持不变；
• high - low 的值为1，所以确定主键为6的记录在槽2对应的组中，需要找到槽2中主键值最小的那条记录，然后沿着单向链表遍历槽2中的记录；

在一个数据页中查找指定主键值的记录的过程分为两步：

• 通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最小的那条记录；
• 通过记录的next_record属性遍历该槽所在的组中的各个记录；