文章/答案/技术大牛

发布

社区首页 >专栏 >InnoDB Page结构详解

InnoDB Page结构详解

jeanron100

发布于 2020-03-19 08:36:57

2.1K00

代码可运行

文章被收录于专栏：杨建荣的学习笔记杨建荣的学习笔记

运行总次数：0

代码可运行

1导读

本文花了比较多的时间梳理了InnoDB page的结构以及对应的分裂测试，其中测试部分大部分是参考了叶老师在《InnoDB表聚集索引层什么时候发生变化》一文中使用的方法，其次，本文中的测试工具用到了如下两个工具：

innblock：https://github.com/gaopengcarl/innblock
innodbruby：https://github.com/jeremycole/innodbruby

本文篇幅较长，强烈建议使用电脑阅读本文。

一、page结构

InnoDB Page结构图

1、File Header结构，记录了page页的一些头信息，一共38字节

innodb存储页类型

2、page header，记录页的状态信息，共56字节

3、虚拟最大最小记录(Infimum and Supremum Records)

最大记录是这个数据页中逻辑上最大的记录，所有用户的记录都小于它。最小记录是数据页上最小的记录，所有用户记录都大于它。他们在数据页被创建的时候创建，而且不能被删除。引入他们主要是方便页内操作。

4、用户记录

用户所有插入的记录都存放在这里，默认情况下记录跟记录之间没有间隙，但是如果重用了已删除记录的空间，就会导致空间碎片。每个记录都有指向下一个记录的指针，但是没有指向上一个记录的指针。记录按照主键顺序排序。即，用户可以从数据页最小记录开始遍历，直到最大的记录，这包括了所有正常的记录和所有被delete-marked记录，但是不会访问到被删除的记录(PAGE_FREE)。

5、Free Space

从PAGEHEAPTOP开始，到最后一个数据目录，这之间的空间就是空闲空间，都被重置为0，当用户需要插入记录时候，首先在被删除的记录的空间中查找，如果没有找到合适的空间，就从这里分配。空间分配给记录后，需要递增PAGENRECS和PAGENHEAP。

6、Page Directory

用户的记录是从低地址向高地址扩展，而数据目录则相反。在数据页被初始化的时候，就会在数据页最后(当然在checksum之前)创建两个数据目录，分别指向最大和最小记录。之后插入新的数据的时候，需要维护这个目录，例如必要的时候增加目录的个数。每个数据目录占用两个字节，存储对应记录的页内偏移量。假设目录N，这个目录N管理目录N-1(不包括)和目录N之间的记录，我们称目录N own 这些记录。在目录N指向的记录中，会有字段记录own记录的数量。由此可见，目录own的记录不能太多，因为太多的话，即意味着目录太过稀疏，不能很好的提高查询效率，但同时也不能own太少，这会导致目录数量变多，占用过多的空间。在InnoDB的实现中，目录own的记录数量在4-8之间，包括4和8，平均是6个记录。如果超过这个数量，就需要重新均衡目录的数量。目录的增加和删除可能需要进行内存拷贝，但是由于目录占用的总体空间很小，开销可以忽略不计。

7、File Trailer

这个部分处于数据页最后的位置，只有8个字节。低地址的四个字节存储checksum的值，高地址的四个字节存储FILPAGELSN的低位四字节。注意这里的checksum的值不一定与FILPAGESPACEORCHKSUM的相同，这个依赖不同的checksum计算方法。

找到一张比较不错的page结构图

二、行记录格式

Record Header

从这个图中可以看到，一条记录的Record Header至少为5字节，对Record Header长度取决于边长字段及字段是否可为空简言之，记住几条关键规则一条记录的record header，至少是5字节对record header影响最大的是变长列数量，及其是否允许为NULL的属性

关于变长列

每个变长列，如果列长度 <128 字节，则需要额外1字节
每个变长列，如果列长度 >=128 字节，则需要额外2字节
如果没有任何变长列，则无需这额外的1-2字节
变长类型为char/varchar/text/blob等
同学们可能会诧异，char为什么也当做变长类型了？这是因为，当字符集非latin1时，最大存储长度可能会超过255字节，例如 char(65) utf8mb4 最长就可以存储260字节，此时在record header中需要用2字节来表示其长度，因此也被当做变长类型了

关于列允许为NULL

每个列如果允许为NULL，则增加 1bit，不足8bit也需要额外1字节
例如只有2个列允许为NULL，只需要2bit来表示，但也需要占用1字节
P.S，在InnoDB的存储结构里，从tablespace到segment，再到extent、page，还是file层面，总有各种必要的header或trailer信息需要消耗额外的字节数，不像MyISAM那么简单。

三、数据page结构

主键非叶子节点

Record Header，根据主键类型不同占用字节数不同，例如一个int主键，Record Header为5字节，另外需要考虑变长类型、是否为空
聚集索引key的长度，比如int为4字节
指向子节点指针，固定4字节

主键叶子节点

Record Header，根据主键类型不同占用字节数不同，例如一个int主键，Record Header为5字节，另外需要考虑变长类型、是否为空
聚集索引key的长度，比如int为4字节
事务ID，固定6字节
回滚段指针，固定7字节
其他列占用空间

二级索引非叶子节点

Record Header，根据主键类型不同占用字节数不同，例如一个int主键，Record Header为5字节，另外需要考虑变长类型、是否为空
二级索引列长度
主键索引列长度
指向子节点指针，固定4字节

二级索引叶子节点

Record Header，根据主键类型不同占用字节数不同，例如一个int主键，Record Header为5字节，另外需要考虑变长类型、是否为空
二级索引key大小
主键索引列长度

四、一个只有1个page的B+树page

Index ID：索引ID，可在informationschema下的INNODBSYS_INDEXES表查到
Level：索引高度
Prev：上一个page指针
Next：下一个page指针
N_Heap：表内所有记录数（包含虚拟最大最小记录）
N_Recs：表内用户记录数
NDirSlots：slots数量
Directory：分别记录每个slot的最后一条数据的便宜量，是一个列表
MaxTrxD：page内所有记录的最大事务ID
Direction：上一条记录的插入方向
N_Direction：同一个方向连续插入记录数
Garbage Size：可回收空间
Garbage off：可回收空间的最近一条记录的偏移量

五、InnoDB表高度计算

相信这是一个面试经常会被问到的问题，那么以三层高度的B树来说，这也是日常生活中最常碰到树的高度了。对于一棵三层高度的B树计算最多存储记录数非常好计算，无非就是根节点最大存储记录数N1中间节点最大存储记录数N2叶子节点最大存储记录数N3得到N，这个N就是当前数据存储结构下的三层高度B树的最大存储记录数。

那么问题来了，对于这个N1、N2、N3分别应该怎么来计算呢？

N1

根节点单行长度计算公式 page大小（16*1024=16384）- 必要信息（File Header38字节+page header56字节+虚拟最大最小记录26字节+Page Directory4字节+File Trailer8字节）=16252字节
每行需要一个指向下一层page的节点的指针，占用4字节
约每4条记录占用一个slot，一个slot大小占用2字节
单行长度计算公式为：row header5字节 + 主键索引列4字节 + 指针4字节 = 13字节

那么单个page最多能容纳最多行数为单行长度N1+N1/4*2 = 16252，N1为1203

N2

中间节点的计算方式等同于根节点

N3

不同于非叶子节点，叶子节点需要保留1/16的空间用做变长更新的保留空间，因此，叶子节点的真实可用空间约为15228字节
row header（5字节+可变长+非空占位符）+ 主键key长度（如果没有显示声明默认会创建6字节row id）+ trxid6字节+ rollptr7字节
以一个只有一个int列的主键表来说，这个单行长度就为5+4+6+7=22字节
约每4条记录占用一个slot，一个slot大小占用2字节

单行长度N3+N3/4*2 =15228，N3为676

六、测试及分析过程

       15872 │                                                                │
       15936 │                                                                │
       16000 │                                      █▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋│
       16064 │█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋│
       16128 │█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋│
       16192 │█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋│
       16256 │█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋│
       16320 │█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋███████▋│
             ╰────────────────────────────────────────────────────────────────╯

Legend (█ = 1 byte):
  Region Type                         Bytes    Ratio
  █ FIL Header                           38    0.23%
  █ Index Header                         36    0.22%
  █ File Segment Header                  20    0.12%
  █ Infimum                              13    0.08%
  █ Supremum                             13    0.08%
  █ Record Header                      3380   20.63%
  █ Record Data                       11492   70.14%
  █ Page Directory                      340    2.08%
  █ FIL Trailer                           8    0.05%
  ░ Garbage                               0    0.00%
    Free                               1044    6.37%

分析如下：

固定开销（38字节+36字节+20字节+13字节+13字节+8字节）
记录头部3380字节（676*5）
记录大小11492字节（676*17）
共170个slot（2*170占340字节）
free space大小为1044字节（保留1024字节+20空闲）

此时B树高度为1

[root@izbp13wpxafsmeraypddyvz data]# innodb_space -s ibdata1 -T xucl/t1 -p 3 space-indexes
id          name                            root        fseg        fseg_id     used        allocated   fill_factor 
2063        PRIMARY                         3           internal    1           1           1           100.00%     
2063        PRIMARY                         3           leaf        2           0           0           0.00%

再次插入一条数据，这个时候树的结构就发生变化了

[root@izbp13wpxafsmeraypddyvz data]# innodb_space -s ibdata1 -T xucl/t1 -p 3 space-indexes
id          name                            root        fseg        fseg_id     used        allocated   fill_factor 
2063        PRIMARY                         3           internal    1           1           1           100.00%     
2063        PRIMARY                         3           leaf        2           2           2           100.00%

可以看到，这个时候树的高度就变成了二层，page no=3为根节点，page no=4和page no=5是它的叶子节点

[root@izbp13wpxafsmeraypddyvz data]# innodb_space -s ibdata1 -T xucl/t1 space-summary
page        type                prev        next        lsn                 
0           FSP_HDR             0           0           70484631053         
1           IBUF_BITMAP         0           0           70484571536         
2           INODE               0           0           70484631053         
3           INDEX               0           0           70484631053         
4           INDEX               0           5           70484631053         
5           INDEX               4           0           70484631053

我们仍然扫描page no=3这个page

       16256 │                                                                │
       16320 │                                                      █▋█▋█████▋│
             ╰────────────────────────────────────────────────────────────────╯

Legend (█ = 1 byte):
  Region Type                         Bytes    Ratio
  █ FIL Header                           38    0.23%
  █ Index Header                         36    0.22%
  █ File Segment Header                  20    0.12%
  █ Infimum                              13    0.08%
  █ Supremum                             13    0.08%
  █ Record Header                        10    0.06%
  █ Record Data                          16    0.10%
  █ Page Directory                        4    0.02%
  █ FIL Trailer                           8    0.05%
  ░ Garbage                               0    0.00%
    Free                              16226   99.04%

可以看到这个page含有2条记录，每条记录record header5字节，数据部分8字节（id列4字节+4字节指针）扫描page no=4这个page

Legend (█ = 1 byte):
  Region Type                         Bytes    Ratio
  █ FIL Header                           38    0.23%
  █ Index Header                         36    0.22%
  █ File Segment Header                  20    0.12%
  █ Infimum                              13    0.08%
  █ Supremum                             13    0.08%
  █ Record Header                      1690   10.31%
  █ Record Data                        5746   35.07%
  █ Page Directory                      172    1.05%
  █ FIL Trailer                           8    0.05%
  ░ Garbage                            7436   45.39%
    Free                               1212    7.40%

从统计信息可以分析出，这个page共338条数据，Garbage size为7436（注意一下，这个后面会有用到）

Legend (█ = 1 byte):
  Region Type                         Bytes    Ratio
  █ FIL Header                           38    0.23%
  █ Index Header                         36    0.22%
  █ File Segment Header                  20    0.12%
  █ Infimum                              13    0.08%
  █ Supremum                             13    0.08%
  █ Record Header                      1695   10.35%
  █ Record Data                        5763   35.17%
  █ Page Directory                      170    1.04%
  █ FIL Trailer                           8    0.05%
  ░ Garbage                               0    0.00%
    Free                               8628   52.66%

从统计信息可以分析出，这个page共339条数据，两个page加起来共677条数据，也符合我们的结果。

到这里，二层分裂我们已经测试完了，我们继续往下测试三层高度，按照我们先前的理论基础，2层高度最多可以容纳约813228条数据（实际上并不是这个值，至于原因我后面再讲），我们利用以下脚本构造t1（我把t1表truncate了），我插入了812890条数据

#!/bin/env python
#coding:utf-8

import pymysql


def insert_mysql():
    conn = pymysql.connect(host='127.0.0.1', user='xucl',
                           password='xuclxucl123', database='xucl', charset='utf8')
    cursor = conn.cursor()

    for i in range(812890):
        sql = "insert into t1 values({});".format(i)
        cursor.execute(sql)
    conn.commit()
    conn.close()

if __name__ == "__main__":
    insert_mysql()

此时树高度为2层

[root@izbp13wpxafsmeraypddyvz data]# innblock xucl/t1.ibd scan 16
----------------------------------------------------------------------------------------------------
Welcome to use this block analyze tool:
[Author]:gaopeng [Blog]:blog.itpub.net/7728585/abstract/1/ [QQ]:22389860
[Review]:yejinrong@zhishutang [Blog]:imysql.com [QQ]:4700963
----------------------------------------------------------------------------------------------------
Datafile Total Size:28311552
===INDEX_ID:2063
level1 total block is (1)
block_no:         3,level:   1|*|
level0 total block is (1203)

根节点存储了1203条数据

我用如下方法扫描并统计了每个叶子page内的数据量

[root@izbp13wpxafsmeraypddyvz data]# cat test.sh 
#!/bin/bash
for i in {3..1235};
do
    innblock xucl/t1.ibd ${i} 16|grep n_rows
done

扫描结果如下：

[root@izbp13wpxafsmeraypddyvz data]# sh test.sh 
slot_nums:301       heaps_rows:1205       n_rows:1203      
slot_nums:86        heaps_rows:678        n_rows:338       
slot_nums:170       heaps_rows:678        n_rows:676       
slot_nums:170       heaps_rows:678        n_rows:676       
slot_nums:170       heaps_rows:678        n_rows:676       
slot_nums:170       heaps_rows:678        n_rows:676       
slot_nums:170       heaps_rows:678        n_rows:676       
slot_nums:170       heaps_rows:678        n_rows:676       
slot_nums:170       heaps_rows:678        n_rows:676       
slot_nums:170       heaps_rows:678        n_rows:676       
slot_nums:170       heaps_rows:678        n_rows:676 
...

我们注意到page no=4这个page，只存储了338条记录，我们用innodb_space扫描这个page

Legend (█ = 1 byte):
  Region Type                         Bytes    Ratio
  █ FIL Header                           38    0.23%
  █ Index Header                         36    0.22%
  █ File Segment Header                  20    0.12%
  █ Infimum                              13    0.08%
  █ Supremum                             13    0.08%
  █ Record Header                      1690   10.31%
  █ Record Data                        5746   35.07%
  █ Page Directory                      172    1.05%
  █ FIL Trailer                           8    0.05%
  ░ Garbage                            7436   45.39%
    Free                               1212    7.40%

很清楚地可以看到，Garbage size为7436，恰好为338条记录大小，至于原因我个人的猜测是因为在一层变二层高度时，由原先page内数据逐条删除，插入新的page，删除的空间变成了Garbage，新page由于是新插入的，所以不存在Garbage（以上未经求证），这里比较细节。

这样一算，插入812890条数据以后，所有的page都已经占满，这也就解释了最大记录数不是理论值813228了。接着我们再插入一条数据

root@mysqldb 20:12:  [xucl]> select count(*) from t1;
+---------+
| max(id) |
+---------+
|  812890 |
+---------+
1 row in set (0.00 sec)

root@mysqldb 20:21:  [xucl]> insert into t1 values(812890);
Query OK, 1 row affected (0.01 sec)

B树变成了三层高度

[Review]:yejinrong@zhishutang [Blog]:imysql.com [QQ]:4700963
----------------------------------------------------------------------------------------------------
Datafile Total Size:28311552
===INDEX_ID:2063
level2 total block is (1)
block_no:         3,level:   2|*|
level1 total block is (2)
block_no:        36,level:   1|*|block_no:        37,level:   1|*|
level0 total block is (1204)