本文主要介绍InnoDB存储引擎的数据页结构
数据页结构
参考链接：Fil Header
- 总共
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
- 总共
56 Bytes，记录页的状态信息
| 名称 |
大小（Bytes） |
描述 |
| PAGE_N_DIR_SLOTS |
2 |
在Page Directory中Slot的数量，初始值为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
- 每个数据页中都有两个
虚拟的行记录，用来限定记录（User Record）的边界（Infimum为下界，Supremum为上界）
Infimum和Supremum在页被创建是自动创建，不会被删除- 在
Compact和Redundant行记录格式下，Infimum和Supremum占用的字节数是不一样的
User Records
参考链接：User Records
- 存储
实际插入的行记录
- 在
Page Header中PAGE_HEAP_TOP、PAGE_N_HEAP的HEAP，实际上指的是Unordered User Record List
- InnoDB不想每次都
依据B+Tree键的顺序来插入新行，因为这可能需要移动大量的数据
- 因此InnoDB插入新行时，通常是插入到当前行的后面（
Free Space的顶部）或者是已删除行留下来的空间
- 为了保证访问B+Tree记录的
顺序性，在每个记录中都有一个指向下一条记录的指针，以此构成了一条**单向有序链表**
Free Space
- 空闲空间，数据结构是
链表，在一个记录被删除后，该空间会被加入到空闲链表中
Page Directory
参考链接：Page Directory
- 存放着
行记录（User Record）的相对位置（不是偏移量）
- 这里的
行记录指针称为Slot或Directory Slot，每个Slot占用2Byte
并不是每一个行记录都有一个Slot，一个Slot中可能包含多条行记录，通过行记录中n_owned字段标识Infimum的n_owned总是1，Supremum的n_owned为[1,8]，User Record的n_owned为[4,8]Slot是按照索引键值的顺序进行逆序存放（Infimum是下界，Supremum是上界），可以利用二分查找快速地定位一个粗略的结果，然后再通过next_record进行精确查找B+Tree索引本身并不能直接找到具体的一行记录，只能找到该行记录所在的页
- 数据库把页载入到
内存中，然后通过Page Directory再进行二分查找
- 二分查找时间复杂度很低，又在内存中进行查找，这部分的时间基本开销可以忽略
File Trailer
参考链接：Fil Trailer
- 总共
8 Bytes，为了检测页是否已经完整地写入磁盘
- 变量
innodb_checksums，InnoDB从磁盘读取一个页时是否会检测页的完整性
- 变量
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
|
CHARSET=LATIN1 ROW_FORMAT=COMPACT下调用存储过程load_t，插入的每个行记录大小为33 Bytes(行记录格式的相关内容请参「InnoDB备忘录 - 行记录格式」)，因此CALL load_t(100)将插入3300 Bytes，这远小于页大小16KB，一个数据页内完全容纳这些数据，即完全在page offset=3的B+Tree叶子节点中
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一致 |
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时，初始值为0x8002（Redundant时，初始值为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 |
无关紧要 |
PAGE_HEAP_TOP的计算过程：38(File Header)+56(Page Header)+13(Infimum)+13(Supremum)+33*100(User Record)=3420=0xd5cUser 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_SLOTS为26，能推断出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]
|
逆序放置
0xfff6~0xfff7为0x0063，0xc000+0x0063=0xc063，指向的是**Infimum Record**（逻辑下界）的伪列（CHAR(8),’infimum’）
0xffc4~0xffc5为0x0070，0xc000+0x0070=0xc070，指向的是**Supremum Record**（逻辑上界）的伪列（CHAR(8),’supremum’）
二分查找
下面以查找主键a=25为例，展示利用Page Directory进行二分查找的过程
(0xfff7+0xffc4)/2 = 0xffdd
0xffdc~0xffdd为0x0711，0xc000+0x0711=0xc711
0xc711~0xc714为0x34，由于0x34=52>25，选择0xfff7作为下一轮查找的逻辑下界
1
| 0000c710: 2100 0000 3400 0000 1409 b6d3 0000 0212 !...4...........
|
(0xfff7+0xffdd)/2 = 0xffea
0xffea~0xffeb为0x0375，0xc000+0x0375=0xc375
0xc375~0xc378为0x18，由于0x18=24<25，选择0xffdd作为下一轮查找的逻辑上界
1
| 0000c370: 0400 c800 2100 0000 1800 0000 1409 9ab7 ....!...........
|
(0xffea+0xffdd)/2 = 0xffe3
0xffe2~0xffe3为0x0585，0xc000+0x0585=0xc585
0xc585~0xc588为0x18，由于0x28=40>25，选择0xffea作为下一轮查找的逻辑下界
1
| 0000c580: 0401 4800 2100 0000 2800 0000 1409 aac7 ..H.!...(.......
|
(0xffea+0xffe3)/2 = 0xffe6
0xffe6~0xffe7为0x047d，0xc000+0x047d=0xc47d
0xc47d~0xc480为0x20，由于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~0xffe9为0x03f9，0xc000+0x03f9=0xc3f9
0xc3f9~0xc3fc为0x1c，由于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
上面二分查找的结果是0xffea，0xffea~0xffeb为0x0375，0xc000+0x0375=0xc375
0xc375~0xc378为0x18=24，下一个行记录的偏移为0x21(记录头信息)，0xc375+0x21=0xc396
0xc396~0xc399为0x19=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 .....!..........
|
参考资料
- MySQL技术内幕 - InnoDB存储引擎 V2
- InnoDB Page Structure
