InnoDB数据页结构之页目录

前言回顾

InnoDB存储引擎的数据页结构如下所示

之前有聊过最小记录、最大记录、用户记录结构，其中用户记录中的记录头信息存在n_owned值，当时的解释是为了单链表检索效率，所以将链表分为若干组，每个组的最大记录的n_owned值用于记录该组的记录数量，测试表结构和测试数据如下所示

-- 测试表建表语句
CREATE TABLE page_demo(
     c1 INT,
     c2 INT,
     c3 VARCHAR(10000),
     PRIMARY KEY (c1)
) CHARSET=ascii ROW_FORMAT=Compact;

-- 测试表数据
+----+------+------+
| c1 | c2   | c3   |
+----+------+------+
|  1 |  100 | aaaa |
|  2 |  200 | bbbb |
|  3 |  300 | cccc |
|  4 |  400 | dddd |
+----+------+------+
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

测试表数据记录头结构如下所示

测试表包含两个数据组

• 最小记录infimum所在记录，只有自身一条记录。

• 最大记录supremum所在记录，自身一条记录和四条业务记录所以n_owned才为5

从这里并不能很明确的看出分组后对于检索后有何优势，那具体如何做的呢？这时候就要引出页目录也就是所谓的Page Directory。

页目录Page Directory

以测试表为例，在将测试表的记录分组后，会将每个组的最后一条记录也就是最大的一条记录的偏移量（注意这里并不是指记录的next_record）这里的偏移量理解为从页面的第0字节位置开始数到距离每个组的最后一条记录的位置的字节数，所以记录头结构应该如下所示

了解完这个，我们思考为什么最小记录只有一条记录，而最大记录是五条呢？

其实这是InnoDB中的一种规则，总共三条

• 最小记录必定是独立的一组，也就是说最小记录的n_owned一定为1。

• 最大记录所在的分组记录数一定是1~8。

• 剩余记录的分组数量一定为4~8。

下面来验证这个规则，在剩余测试记录的基础上新增8条数据如下所示

INSERT INTO page_demo VALUES(5, 500, 'eeee'), (6, 600, 'ffff'), (7, 700, 'gggg'), (8, 800, 'hhhh');
INSERT INTO page_demo VALUES(9, 900, 'iiii'), (10, 1000, 'jjjj'), (11, 1100, 'kkkk'), (12, 1200, 'llll');
1
2

为了图更好的展示这里只分析记录头的n_owned属性，ibd文件如下所示

                ....省略部分数据                       01 00  |.......h.....2..|
0000c060  02 00 1c 69 6e 66 69 6d  75 6d 00 05 00 0b 00 00  |...infimum......|
0000c070  73 75 70 72 65 6d 75 6d  04 00 00 00 10 00 20 80  |supremum...... .|
0000c080  00 00 01 00 00 00 00 8f  5b c2 00 00 01 56 01 10  |........[....V..|
0000c090  80 00 00 64 61 61 61 61  04 00 00 00 18 00 20 80  |...daaaa...... .|
0000c0a0  00 00 02 00 00 00 00 8f  5b c2 00 00 01 56 01 1c  |........[....V..|
0000c0b0  80 00 00 c8 62 62 62 62  04 00 00 00 20 00 20 80  |....bbbb.... . .|
0000c0c0  00 00 03 00 00 00 00 8f  5b c2 00 00 01 56 01 28  |........[....V.(|
0000c0d0  80 00 01 2c 63 63 63 63  04 00 04 00 28 00 20 80  |...,cccc....(. .|
0000c0e0  00 00 04 00 00 00 00 8f  5b c2 00 00 01 56 01 34  |........[....V.4|
0000c0f0  80 00 01 90 64 64 64 64  04 00 00 00 30 00 20 80  |....dddd....0. .|
0000c100  00 00 05 00 00 00 00 8f  60 c5 00 00 01 59 01 10  |........`....Y..|
0000c110  80 00 01 f4 65 65 65 65  04 00 00 00 38 00 20 80  |....eeee....8. .|
0000c120  00 00 06 00 00 00 00 8f  60 c5 00 00 01 59 01 1c  |........`....Y..|
0000c130  80 00 02 58 66 66 66 66  04 00 00 00 40 00 20 80  |...Xffff....@. .|
0000c140  00 00 07 00 00 00 00 8f  60 c5 00 00 01 59 01 28  |........`....Y.(|
0000c150  80 00 02 bc 67 67 67 67  04 00 04 00 48 00 20 80  |....gggg....H. .|
0000c160  00 00 08 00 00 00 00 8f  60 c5 00 00 01 59 01 34  |........`....Y.4|
0000c170  80 00 03 20 68 68 68 68  04 00 00 00 50 00 20 80  |... hhhh....P. .|
0000c180  00 00 09 00 00 00 00 8f  65 c8 00 00 01 5c 01 10  |........e....\..|
0000c190  80 00 03 84 69 69 69 69  04 00 00 00 58 00 20 80  |....iiii....X. .|
0000c1a0  00 00 0a 00 00 00 00 8f  65 c8 00 00 01 5c 01 1c  |........e....\..|
0000c1b0  80 00 03 e8 6a 6a 6a 6a  04 00 00 00 60 00 20 80  |....jjjj....`. .|
0000c1c0  00 00 0b 00 00 00 00 8f  65 c8 00 00 01 5c 01 28  |........e....\.(|
0000c1d0  80 00 04 4c 6b 6b 6b 6b  04 00 00 00 68 fe 91 80  |...Lkkkk....h...|
0000c1e0  00 00 0c 00 00 00 00 8f  65 c8 00 00 01 5c 01 34  |........e....\.4|
0000c1f0  80 00 04 b0 6c 6c 6c 6c  00 00 00 00 00 00 00 00  |....llll........|
....省略部分数据
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

提取所有记录包含最大记录和最小记录的记录头信息，如下所示

最小记录：01 00 02 00 1c  n_owned=0001(1)
最大记录：05 00 0b 00 00  n_owned=0101(5)
第一条记录：00 00 10 00 20 n_owned=0000(0)
第二条记录：00 00 18 00 20 n_owned=0000(0)
第三条记录：00 00 20 00 20 n_owned=0000(0)
第四条记录：04 00 28 00 20 n_owned=0100(4)
第五条记录：00 00 30 00 20 n_owned=0000(0)
第六条记录：00 00 38 00 20 n_owned=0000(0)
第七条记录：00 00 40 00 20 n_owned=0000(0)
第八条记录：04 00 48 00 20 n_owned=0100(4)
第九条记录：00 00 50 00 20 n_owned=0000(0)
第十条记录：00 00 58 00 20 n_owned=0000(0)
第十一条记录：00 00 60 00 20 n_owned=0000(0)
第十二条记录：00 00 68 fe 91 n_owned=0000(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

将所有记录关联起来如下所示

根据上图就来聊聊分组规则

• 初始情况下数据页就存在两个分组，这两个分组分别保存最小记录和最大记录。

• 后续每插入一条记录，都会先从页目录中查找比主键值大并且差距最小的槽，同时向槽中新增一条记录，该槽中的n_owned就会加一，如果在插入前该槽中的记录数为8个，会将该分组的记录拆分为两个组，一个组中4条记录，另一个分组5条记录，同时页目录中将新增一个槽，用于存放新分组的最大一条记录。

根据页目录查询过程

在查询前我们应该知道每个组都是根据主键来进行排序，在页目录中的槽也是根据主键顺序排列，在进行查询时采用二分法，定位到查询的值对应具体的槽，虽然槽中保存的是每个组最大的记录，但很容易能拿到相邻槽的最大记录值，这样就可以通过next_record遍历分组的所有记录。