本文主要介绍InnoDB存储引擎的数据页结构

数据页结构

File Header

参考链接:Fil Header

  1. 总共38 Bytes,记录页的头信息
名称 大小(Bytes) 描述
FIL_PAGE_SPACE 4 该页的checksum
FIL_PAGE_OFFSET 4 该页在表空间中的页偏移量
FIL_PAGE_PREV 4 该页的上一个页
FIL_PAGE_NEXT 4 该页的下一个页
FIL_PAGE_LSN 8 该页最后被修改的LSN
FIL_PAGE_TYPE 2 该页的类型,0x45BF为数据页
FIL_PAGE_FILE_FLUSH_LSN 8 独立表空间中为0
FIL_PAGE_ARCH_LOG_NO 4 该页属于哪一个表空间

参考链接:Page Header

  1. 总共56 Bytes,记录页的状态信息
名称 大小(Bytes) 描述
PAGE_N_DIR_SLOTS 2 Page DirectorySlot的数量,初始值为2
PAGE_HEAP_TOP 2 堆中第一个记录的指针
PAGE_N_HEAP 2 堆中的记录数,初始值为2
PAGE_FREE 2 指向可重用空间的首指针
PAGE_GARBAGE 2 已标记为删除(deleted_flag)的记录的字节数
PAGE_LAST_INSERT 2 最后插入记录的位置
PAGE_DIRECTION 2 最后插入的方向,PAGE_LEFT(0x01)PAGE_RIGHT(0x02)PAGE_NO_DIRECTION(0x05)
PAGE_N_DIRECTION 2 一个方向上连续插入记录的数量
PAGE_N_RECS 2 该页中记录(User Record)的数量
PAGE_MAX_TRX_ID 8 修改该页的最大事务ID(仅在辅助索引中定义)
PAGE_LEVEL 2 该页在索引树中位置,0000代表叶子节点
PAGE_INDEX_ID 8 索引ID,表示该页属于哪个索引
PAGE_BTR_SEG_LEAF 10 B+Tree叶子节点所在Leaf Node Segment的Segment Header(无关紧要)
PAGE_BTR_SEG_TOP 10 B+Tree非叶子节点所在Non-Leaf Node Segment的Segment Header(无关紧要)

Infimum + Supremum Records

参考链接:The Infimum and Supremum Records

  1. 每个数据页中都有两个虚拟的行记录,用来限定记录(User Record)的边界(Infimum为下界Supremum为上界
  2. InfimumSupremum页被创建是自动创建,不会被删除
  3. CompactRedundant行记录格式下,InfimumSupremum占用的字节数是不一样

User Records

参考链接:User Records

  1. 存储实际插入的行记录
  2. Page HeaderPAGE_HEAP_TOPPAGE_N_HEAPHEAP,实际上指的是Unordered User Record List
    • InnoDB不想每次都依据B+Tree键的顺序插入新行,因为这可能需要移动大量的数据
    • 因此InnoDB插入新行时,通常是插入到当前行的后面(Free Space的顶部)或者是已删除行留下来的空间
  3. 为了保证访问B+Tree记录的顺序性,在每个记录中都有一个指向下一条记录的指针,以此构成了一条**单向有序链表**

Free Space

  1. 空闲空间,数据结构是链表,在一个记录被删除后,该空间会被加入到空闲链表中

Page Directory

参考链接:Page Directory

  1. 存放着行记录User Record)的相对位置(不是偏移量)
  2. 这里的行记录指针称SlotDirectory Slot,每个Slot占用2Byte
  3. 并不是每一个行记录都有一个Slot,一个Slot中可能包含多条行记录,通过行记录中n_owned字段标识
  4. Infimum的n_owned总是1Supremum的n_owned为[1,8]User Record的n_owned为[4,8]
  5. Slot是按照索引键值的顺序进行逆序存放(Infimum是下界,Supremum是上界),可以利用二分查找快速地定位一个粗略的结果,然后再通过next_record进行精确查找
  6. B+Tree索引本身并不能直接找到具体的一行记录,只能找到该行记录所在的页
    • 数据库把页载入到内存中,然后通过Page Directory再进行二分查找
    • 二分查找时间复杂度很低,又在内存中进行查找,这部分的时间基本开销可以忽略

File Trailer

参考链接:Fil Trailer

  1. 总共8 Bytes,为了检测页是否已经完整地写入磁盘
  2. 变量innodb_checksums,InnoDB从磁盘读取一个页时是否会检测页的完整性
  3. 变量innodb_checksum_algorithm检验和算法
名称 大小(Bytes) 描述
FIL_PAGE_END_LSN 8 前4Bytes与File Header中的FIL_PAGE_SPACE一致,后4Bytes与File Header中的FIL_PAGE_LSN的后4Bytes一致
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
mysql> SHOW VARIABLES LIKE 'innodb_checksums';
+------------------+-------+
| Variable_name | Value |
+------------------+-------+
| innodb_checksums | ON |
+------------------+-------+
1 row in set (0.01 sec)

mysql> SHOW VARIABLES LIKE 'innodb_checksum_algorithm';
+---------------------------+-------+
| Variable_name | Value |
+---------------------------+-------+
| innodb_checksum_algorithm | crc32 |
+---------------------------+-------+
1 row in set (0.00 sec)

实例

表初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
mysql> CREATE TABLE t (
-> a INT UNSIGNED NOT NULL AUTO_INCREMENT,
-> b CHAR(10),
-> PRIMARY KEY(a)
-> ) ENGINE=INNODB CHARSET=LATIN1 ROW_FORMAT=COMPACT;
Query OK, 0 rows affected (0.89 sec)

mysql> DELIMITER //
mysql> CREATE PROCEDURE load_t (count INT UNSIGNED)
-> BEGIN
-> SET @c=0;
-> WHILE @c < count DO
-> INSERT INTO t SELECT NULL,REPEAT(CHAR(97+RAND()*26),10);
-> SET @c=@c+1;
-> END WHILE;
-> END;
-> //
Query OK, 0 rows affected (0.06 sec)

mysql> DELIMITER ;
mysql> CALL load_t(100);
Query OK, 0 rows affected (0.22 sec)

mysql> SELECT * FROM t LIMIT 5;
+---+------------+
| a | b |
+---+------------+
| 1 | uuuuuuuuuu |
| 2 | qqqqqqqqqq |
| 3 | xxxxxxxxxx |
| 4 | oooooooooo |
| 5 | cccccccccc |
+---+------------+
5 rows in set (0.02 sec)
1
2
3
4
5
6
7
8
9
10
11
12
13
$ sudo python py_innodb_page_info.py -v /var/lib/mysql/test/t.ibd
page offset 00000000, page type <File Space Header>
page offset 00000001, page type <Insert Buffer Bitmap>
page offset 00000002, page type <File Segment inode>
page offset 00000003, page type <B-tree Node>, page level <0000>
page offset 00000000, page type <Freshly Allocated Page>
page offset 00000000, page type <Freshly Allocated Page>
Total number of page: 6:
Freshly Allocated Page: 2
Insert Buffer Bitmap: 1
File Space Header: 1
B-tree Node: 1
File Segment inode: 1
  1. CHARSET=LATIN1 ROW_FORMAT=COMPACT下调用存储过程load_t,插入的每个行记录大小为33 Bytes(行记录格式的相关内容请参「InnoDB备忘录 - 行记录格式」),因此CALL load_t(100)将插入3300 Bytes,这远小于页大小16KB,一个数据页内完全容纳这些数据,即完全在page offset=3B+Tree叶子节点

File Header

1
2
3
4
# Vim,:%!xxd
0000c000: d42f 4c48 0000 0003 ffff ffff ffff ffff ./LH............
0000c010: 0000 0000 4091 c84f 45bf 0000 0000 0000 [email protected].......
0000c020: 0000 0000 0120 001a 0d5c 8066 0000 0000 ..... ...\.f....
16进制 名称 描述
d4 2f 4c 48 FIL_PAGE_SPACE 该页的checksum
00 00 00 03 FIL_PAGE_OFFSET 该页page 0ffset=3
ff ff ff ff FIL_PAGE_PREV 目前只有一个数据页,无上一页
ff ff ff ff FIL_PAGE_NEXT 目前只有一个数据页,无下一页
00 00 00 00 40 91 c8 4f FIL_PAGE_LSN 该页最后被修改的LSN
45 bf FIL_PAGE_TYPE 数据页
00 00 00 00 00 00 00 00 FIL_PAGE_FILE_FLUSH_LSN 独立表空间中为0
00 00 01 20 FIL_PAGE_ARCH_LOG_NO 该页属于哪一个表空间

File Trailer

1
2
# Vim,:%!xxd
0000fff0: 01e9 0165 00e1 0063 d42f 4c48 4091 c84f ...e...c./[email protected]
16进制 名称 描述
d4 2f 4c 48 40 91 c8 4f FIL_PAGE_END_LSN 前4Bytes与File Header中的FIL_PAGE_SPACE一致,后4Bytes与File Header中的FIL_PAGE_LSN的后4Bytes一致

Page Header

1
2
3
4
5
6
7
8
# Vim,:%!xxd
0000c020: 0000 0000 0120 001a 0d5c 8066 0000 0000 ..... ...\.f....
0000c030: 0d41 0002 0063 0064 0000 0000 0000 0000 .A...c.d........
0000c040: 0000 0000 0000 0000 0164 0000 0120 0000 .........d... ..
0000c050: 0002 00f2 0000 0120 0000 0002 0032 0100 ....... .....2..
......
0000cd40: 2f00 0000 6400 0000 1409 e6a3 0000 01f9 /...d...........
0000cd50: 0110 6d6d 6d6d 6d6d 6d6d 6d6d 0000 0000 ..mmmmmmmmmm....
16进制 名称 描述
00 1a PAGE_N_DIR_SLOTS Page Directory有26个Slot,每个Slot占用2Byte,因此范围为0xffc4~0xfff7
0d 5c PAGE_HEAP_TOP Free Space开始位置的偏移量,0xc000+0x0d5c=0xcd5c
80 66 PAGE_N_HEAP Compact时,初始值为0x8002Redundant时,初始值为2),行记录数为0x8066-0x8002=0x64=100
00 00 PAGE_FREE 未执行删除操作,无可重用空间,该值为0
00 00 PAGE_GARBAGE 未执行删除操作,标记为删除的记录的字节数为0
0d 41 PAGE_LAST_INSERT 0xc000+0x0d41=0xcd41,直接指向ROWID
00 02 PAGE_DIRECTION PAGE_RIGHT,通过自增主键的方式插入行记录
00 63 PAGE_N_DIRECTION 0x63=99,通过自增主键的方式插入行记录
00 64 PAGE_N_RECS 0x64=100,与PAGE_N_HEAP中计算一致
00 00 00 00 00 00 00 00 PAGE_MAX_TRX_ID ??
00 00 PAGE_LEVEL 叶子节点
00 00 00 00 00 00 01 64 PAGE_INDEX_ID 索引ID
00 00 01 20 00 00 00 02 00 f2 PAGE_BTR_SEG_LEAF 无关紧要
00 00 01 20 00 00 00 02 00 32 PAGE_BTR_SEG_TOP 无关紧要
  1. PAGE_HEAP_TOP的计算过程:38(File Header)+56(Page Header)+13(Infimum)+13(Supremum)+33*100(User Record)=3420=0xd5c
  2. User Record向下生长Page Directory向上生长

Infimum + Supremum Records

1
2
3
4
5
# Vim,:%!xxd
0000c050: 0002 00f2 0000 0120 0000 0002 0032 0100 ....... .....2..
0000c060: 0200 1b69 6e66 696d 756d 0005 000b 0000 ...infimum......
0000c070: 7375 7072 656d 756d 0000 0010 0021 0000 supremum.....!..
0000c080: 0001 0000 0014 097f be00 0002 0401 1075 ...............u

Infimum Records

16进制 名称 描述
01 00 02 00 1b 记录头信息 0xc05e+0x1b=0xc079,指向第1个行记录的记录头n_owned=1
69 6e 66 69 6d 75 6d 00 伪列 CHAR(8),infimum

Supremum Records

16进制 名称 描述
05 00 0b 00 00 记录头信息 00,无下一个行记录;n_owned=5
73 75 70 72 65 6d 75 6d 伪列 CHAR(8),supremum

User Records

行记录格式的相关内容请参「InnoDB备忘录 - 行记录格式」,这里仅给出第1个行记录的解析

1
2
3
4
# Vim,:%!xxd
0000c070: 7375 7072 656d 756d 0000 0010 0021 0000 supremum.....!..
0000c080: 0001 0000 0014 097f be00 0002 0401 1075 ...............u
0000c090: 7575 7575 7575 7575 7500 0000 1800 2100 uuuuuuuuu.....!.
16进制 名称 描述
变长字段列表 表中没有变长字段
00 NULL标志位 该行记录没有列为NULL
00 00 10 00 21 记录头信息 0xc078+0x21=0xc099,指向第2个行记录
00 00 00 01 ROWID 表显式定义主键a
00 00 00 14 09 7f Transaction ID 事务ID
be 00 00 02 04 01 10 Roll Pointer 回滚指针
75 75 75 75 75 75 75 75 75 75 b 字符串uuuuuuuuuu

Page Directory

Page Header中的PAGE_N_DIR_SLOTS26,能推断出Page Directory的范围为0xffc4~0xfff7

1
2
3
4
5
# Vim,:%!xxd
0000ffc0: 0000 0000 0070 0cbd 0c39 0bb5 0b31 0aad .....p...9...1..
0000ffd0: 0a29 09a5 0921 089d 0819 0795 0711 068d .)...!..........
0000ffe0: 0609 0585 0501 047d 03f9 0375 02f1 026d .......}...u...m
0000fff0: 01e9 0165 00e1 0063 d42f 4c48 4091 c84f ...e...c./[email protected]

逆序放置

  1. 0xfff6~0xfff70x00630xc000+0x0063=0xc063,指向的是**Infimum Record**(逻辑下界)的伪列(CHAR(8),’infimum’)

  2. 0xffc4~0xffc50x00700xc000+0x0070=0xc070,指向的是**Supremum Record**(逻辑上界)的伪列(CHAR(8),’supremum’)

二分查找

下面以查找主键a=25为例,展示利用Page Directory进行二分查找的过程

(0xfff7+0xffc4)/2 = 0xffdd

0xffdc~0xffdd0x07110xc000+0x0711=0xc711
0xc711~0xc7140x34,由于0x34=52>25,选择0xfff7作为下一轮查找的逻辑下界

1
0000c710: 2100 0000 3400 0000 1409 b6d3 0000 0212  !...4...........

(0xfff7+0xffdd)/2 = 0xffea

0xffea~0xffeb0x03750xc000+0x0375=0xc375
0xc375~0xc3780x18,由于0x18=24<25,选择0xffdd作为下一轮查找的逻辑上界

1
0000c370: 0400 c800 2100 0000 1800 0000 1409 9ab7  ....!...........

(0xffea+0xffdd)/2 = 0xffe3

0xffe2~0xffe30x05850xc000+0x0585=0xc585
0xc585~0xc5880x18,由于0x28=40>25,选择0xffea作为下一轮查找的逻辑下界

1
0000c580: 0401 4800 2100 0000 2800 0000 1409 aac7  ..H.!...(.......

(0xffea+0xffe3)/2 = 0xffe6

0xffe6~0xffe70x047d0xc000+0x047d=0xc47d
0xc47d~0xc4800x20,由于0x20=32>25,选择0xffea作为下一轮查找的逻辑下界

1
2
0000c470: 7272 7272 7272 7200 0401 0800 2100 0000  rrrrrrr.....!...
0000c480: 2000 0000 1409 a2bf 0000 019c 0110 6565 .............ee

(0xffea+0xffe6)/2 = 0xffe8

0xffe8~0xffe90x03f90xc000+0x03f9=0xc3f9
0xc3f9~0xc3fc0x1c,由于0x1c=28>25,选择0xffea作为下一轮查找的逻辑下界

1
0000c3f0: 6666 6600 0400 e800 2100 0000 1c00 0000  fff.....!.......

(0xffea+0xffe8)/2 = 0xffe9

0xffe8~0xffe9跟上一步得到的Slot一致,目前只得到了粗略的结果,下面需要从逻辑上界0xffea开始通过next_record进行精确查找(单向链表遍历

next_record

上面二分查找的结果是0xffea0xffea~0xffeb0x03750xc000+0x0375=0xc375
0xc375~0xc3780x18=24,下一个行记录的偏移为0x21(记录头信息),0xc375+0x21=0xc396
0xc396~0xc3990x19=25,终于找到了主键a=25的行记录!!

1
2
3
0000c370: 0400 c800 2100 0000 1800 0000 1409 9ab7  ....!...........
0000c380: 0000 0194 0110 6666 6666 6666 6666 6666 ......ffffffffff
0000c390: 0000 00d0 0021 0000 0019 0000 0014 099b .....!..........

参考资料

  1. MySQL技术内幕 - InnoDB存储引擎 V2
  2. InnoDB Page Structure