04-25 02:46 阅读 156

InnoDB表聚集索引层高什么时候发生变化

导读

本文略长，主要解决以下几个疑问

1、聚集索引里都存储了什么宝贝

2、什么时候索引层高会发生变化

3、预留的1/16空闲空间做什么用的

4、记录被删除后的空间能回收重复利用吗

1、背景信息

1.1 关于innodb_fill_factor

有个选项 innodb_fill_factor 用于定义InnoDB page的填充率，默认值是100，但其实最高只能填充约15KB的数据，因为InnoDB会预留1/16的空闲空间。在InnoDB文档中，有这么一段话

An innodb_fill_factor setting of 100 leaves 1/16 of the space in clustered index pages free for future index growth.

另外，文档中还有这样一段话

When new records are inserted into an InnoDB clustered index, InnoDB tries to leave 1/16 of the page free for future insertions and updates of the index records. If index records are inserted in a sequential order (ascending or descending), the resulting index pages are about 15/16 full. If records are inserted in a random order, the pages are from 1/2 to 15/16 full.

上面这两段话，综合起来理解，就是

即便 innodb_fill_factor=100，也会预留1/16的空闲空间，用于现存记录长度扩展用

在最佳的顺序写入数据模式下，page填充率有可能可以达到15/16

在随机写入新数据模式下，page填充率约为 1/2 ~ 15/16

预留1/16这个规则，只针对聚集索引的叶子节点有效。对于聚集索引的非叶子节点以及辅助索引（叶子及非叶子）节点都没有这个规则

不过 innodb_fill_factor 选项对叶子节点及非叶子节点都有效，但对存储text/blob溢出列的page无效

1.2 关于innodb_ruby项目

innodb_ruby 项目是由Jeremy Cole 和 Davi Arnaut 两位大神开发的项目，可用于解析InnoDB数据结构，用ruby开发而成。他们还维护了另一个众所周知的项目叫 InnoDB Diagrams，相信稍微资深一点的MySQL DBA都应该知道这个项目。

1.3 关于innblock工具

由八怪开发，用于扫描和分析InnoDB page，详见 innblock | InnoDB page观察利器

1.4 阅读本文背景信息

需要假设您对InnoDB的数据结构已经有了一定了解，包括B+树、聚集索引、辅助索引，以及innodb page的一些简单结构。

Clustered and Secondary Indexes

The Physical Structure of an InnoDB Index

InnoDB Row Formats

InnoDB Record Structure

InnoDB Page Structure

2、测试验证：一层高的InnoDB表聚集索引，最多能存多少条数据

从上面我们知道，一个page最大约能存储15/16容量，扣掉用于存储page header、trailer信息，以及index header、File Segment Header、Infimum&Supremum（两条虚拟记录）等必要的固定消耗之后，实际大约只有15212字节可用于存储用户数据。

这样一来，我们就可以简单测算出一个page大约能存储多少条记录了。

本次用到的测试表，只有一个INT列，同时作为主键（建议横版观看，可左右滑动。或者复制链接到PC端打开观看，效果更佳。下同）

# MySQL的版本是Percona Server 5.7.22-22，我自己下载源码编译的

[root@yejr.me#] mysql -Smysql.sock innodb

...

Server version: 5.7.22-22-log Source distribution

...

[root@yejr.me]> \s

...

Server version: 5.7.22-22-log Source distribution

# 创建测试表

[root@yejr.me]> CREATE TABLE `t1` (

`i` int(10) unsigned NOT NULL AUTO_INCREMENT,

PRIMARY KEY (`i`)

) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 ROW_FORMAT=DYNAMIC;

另外，我们知道每条记录都要几个额外存储的数据

DB_TRX_ID，6字节

DB_ROLL_PTR，7字节

Record Header，至少5字节（用上面这个测试表，只需要5字节，不同数据类型需要的header长度也不同，详见浅析InnoDB Record Header及page overflow

因此，一条数据需要消耗 4(INT列) + 6 + 7 + 5 = 22字节

此外，大约每4条记录就需要一个directory slot，每个slot需要2字节

综上，假设可以存储N条记录，则 N*22 + N/4*2 = 15212，可求得N约等于676

接下来我们验证一下，往该表中持续插入 676 条数据

[root@yejr.me]> insert into t1 select 0;

...

# 逐次反复执行676次

然后，我们利用 innodb_ruby 工具查看其数据结构

2.1 查看聚集索引page结构

此时t1表的聚集索引树只有一层高，一个page即pageno=3

[root@yejr]# innodb_space -s ibdata1 -T innodb/t1 space-indexes

再用innblock工具扫描佐证一下

[root@yejr]# innblock innodb/t1.ibd scan 16

...

level0 total block is (1)

block_no: 3,level: 0|*|

2.2 查看其directory slot

可以看到170个slot，其中Infimum记录的owned=1，Supremum记录的owned=5

[root@yejr]# innodb_space -s ibdata1 -T innodb/t1 \

-p 3 page-directory-summary|grep -c -v slot

170

2.3 查看整个page的全览图

前面是一堆头信息

[root@yejr]# innodb_space -s ibdata1 -T innodb/t1 -p 3 page-illustrate

Offset ╭────────────────────────────────────────────────────────────────╮

0 │█████████████████████████████████████▋██████████████████████████│

64 │█████████▋███████████████████▋████████████▋████████████▋████▋███│

# 大概从这里开始是第一条记录

128 │█████████████▋████▋████████████████▋████▋████████████████▋████▋█│

192 │███████████████▋████▋████████████████▋████▋████████████████▋████│

...

# 中间是用户数据

...

# 这里是预留的1/16空闲空间

15872 │ │

15936 │ │

# 这里是page directory slot，逆序存储

# trailer占用8字节，此后每个slot占用2字节

# 共170个slot

16000 │ █▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋█▋│

...

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%

可以得到几点信息

Record Data共占用11492字节，共676条记录，每条记录17字节（4+6+7）

Page Directory共340字节，170个slot，每个slot占用2字节

两条虚拟记录，均占用13字节（含5字节的record header）

Record Header共3380字节，共676条记录，每条记录需要5字节头信息（再次提醒，表里字段类型各异，Record Header也会随之不同，仅在本例中只需要5字节。详见浅析InnoDB Record Header及page overflow）

提醒：本次测试是顺序写入，如果是随机写入或批量写入，可能就没办法把15/16的page空间填充的满满当当了

2.4 什么时候发生B+树分裂

如果我们再插入一条记录，就会发现，t1表原本只有一层高的B+树，会分裂成两层高度

[root@yejr.me]> insert into t1 select 0;

再次查看数据结构，注意到此时leaf节点的page数为2，也就是分裂成两层高度了

[root@yejr]# innodb_space -s ibdata1 -T innodb/t1 space-indexes

id name root fseg fseg_id used allocated fill_factor

128 PRIMARY 3 internal 1 1 1 100.00%

128 PRIMARY 3 leaf 2 2 2 0.00%

用 innblock 工具扫描佐证

[root@yejr]# innblock innodb/t1.ibd scan 16

...

Datafile Total Size:98304

===INDEX_ID:121

level1 total block is (1)

block_no: 3,level: 1|*|

level0 total block is (2)

block_no: 4,level: 0|*|block_no: 5,level: 0|*|

确认此时发生分裂了，由一层高度分裂成两层，根节点（level=1）pageno=3，叶子节点（level=0）分别为pageno=[4, 5]。

3、理论推演，当innodb表聚集索引达到三层高时，大概可以存储几条记录

3.1 分析根节点page

上述测试表此时是一个两层高的聚集索引，分别是根节点（level=1，pageno=3），叶子节点（level=0，pageno=[4,5]）。

此时根节点里只有两条记录，分别指向两个叶子节点pageno=[4, 5]

[root@yejr]# innodb_space -s ibdata1 -T innodb/t1 -p 3 page-records

Record 125: (i=2) → #4

Record 138: (i=382) → #5

再查看根节点详细数据

[root@yejr]# innodb_space -s ibdata1 -T innodb/t1 -p 3 page-dump

#<Innodb::Page::Index:0x00000001a5eb40>:

fil header:

{:checksum=>4010521133,

:offset=>3,

:prev=>nil,

:next=>nil,

:lsn=>4316394,

:type=>:INDEX,

:flush_lsn=>0,

:space_id=>104}

fil trailer:

{:checksum=>4010521133, :lsn_low32=>4316394}

page header:

{:n_dir_slots=>2,

:heap_top=>146,

:garbage_offset=>0,

:garbage_size=>0,

:last_insert_offset=>138,

:direction=>:right,

:n_direction=>1,

:n_recs=>2,

:max_trx_id=>0,

:level=>1,

:index_id=>121,

:n_heap=>4,

:format=>:compact}

fseg header:

{:leaf=>

<Innodb::Inode space=<Innodb::Space file="innodb/t1.ibd", page_size=16384, pages=6>, fseg=2>,

:internal=>

<Innodb::Inode space=<Innodb::Space file="innodb/t1.ibd", page_size=16384, pages=6>, fseg=1>}

sizes:

header 120

trailer 8

directory 4

free 16226

used 158

record 26

per record 13.00

page directory:

[99, 112]

# 2条系统记录，即infimum、supremum这两条虚拟记录

system records:

{:offset=>99,

:header=>

{:next=>125,

:type=>:infimum,

:heap_number=>0,

:n_owned=>1,

:min_rec=>false,

:deleted=>false,

:length=>5},

:next=>125,

:data=>"infimum\x00",

:length=>8}

{:offset=>112,

:header=>

{:next=>112,

:type=>:supremum,

:heap_number=>1,

:n_owned=>3,

:min_rec=>false,

:deleted=>false,

:length=>5},

:next=>112,

:data=>"supremum",

:length=>8}

garbage records:

# 物理记录

records:

{:format=>:compact,

:offset=>125,

:header=>

{:next=>138,

:type=>:node_pointer,

:heap_number=>2,

:n_owned=>0,

# 是聚集索引的min_key

:min_rec=>true,

:deleted=>false,

:nulls=>[],

:lengths=>{},

:externs=>[],

:length=>5},

:next=>138,

:type=>:clustered,

# i=2这条记录（该表第一条记录，我此前把i=1记录给删了）

:key=>[{:name=>"i", :type=>"INT UNSIGNED", :value=>2}],

:row=>[],

:sys=>[],

# 指针指向叶子节点pageno=4，该记录消耗8字节，含4字节的指针

:child_page_number=>4,

:length=>8}

{:format=>:compact,

:offset=>138,

:header=>

{:next=>112,

:type=>:node_pointer,

:heap_number=>3,

:n_owned=>0,

:min_rec=>false,

:deleted=>false,

:nulls=>[],

:lengths=>{},

:externs=>[],

:length=>5},

:next=>112,

:type=>:clustered,

# i=382这条记录

:key=>[{:name=>"i", :type=>"INT UNSIGNED", :value=>382}],

:row=>[],

:sys=>[],

# 指针指向叶子节点pageno=5，该记录消耗8字节，含4字节的指针

:child_page_number=>5,

:length=>8}

查看根节点整个page的全览图

[root@yejr.me#] innodb_space -s ibdata1 -T innodb/t1 -p 3 page-illustrate

0 │█████████████████████████████████████▋██████████████████████████│

128 │████▋████▋███████▋ │

192 │ │

256 │ │

...

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 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%

可以得到几点结论

根节点里共有两条记录，每条记录占用8字节

由于整型只需要4字节，因此我们可推断出指向叶子节点的指针需要占用4字节

每条记录同样需要5字节的record header（不同聚集索引列数据类型，需要的record header也不一样）

减去必要的FIL Header、Index Header等头信息后，非叶子节点可用空间约 16241 字节

综上，假设非叶子节点可以存储N条记录，则 N*13 + N/4*2 = 16241，可求得N约等于1203

既然每个非叶子节点可存储1203条记录，每个叶子节点可存储676条记录，则一个三层高度的InnoDB表聚集索引可以存储 1203*1203*676= 978313284，也就是约9.7亿条记录

所以说，如果表足够“窄”的话，一个三层高的表足够存储上亿条数据，其平均搜索效率并不差，常规的存取效率也不会太差

当然了，如果因为索引使用不当，导致检索效率低下，或者频繁发生锁等待，那要另当别论

3.2 补充测试：在两层高度时，根节点最多可以存储几条记录

我们对上面的t1表持续写入数据，验证在两层高度时，根节点最多可以存储几条记录。

我们继续使用上面的测试表，经验证：在两层高度时，根节点可以存储 1203 条记录，整个表最多 812890 条记录。

# 查看总记录数

[root@yejr.me]> select count(*) from t1;

+----------+

| count(*) |

+----------+

| 812890 |

+----------+

# 查看聚集索引层级

[root@yejr.me#] innblock innodb/t1.ibd scan 16

...

# 存储81万条数据，数据表空间文件大小为27MB

# 换算下，如果是3层高度的表存满，表空间文件大小约3.25GB

Datafile Total Size:28311552

===INDEX_ID:131

level1 total block is (1)

block_no: 3,level: 1|*|

level0 total block is (1203)

block_no: 4,level: 0|*|block_no: 5,level: 0|*|block_no: 6,level: 0|*|

...

block_no: 1232,level: 0|*|block_no: 1233,level: 0|*|block_no: 1234,level: 0|*|

# 查看根节点page数据结构图

[root@yejr.me#] innodb_space -s ibdata1 -T innodb/t1 -p 3 page-illustrate

...

Legend (█ = 1 byte):（固定长度的头信息部分我都给去掉了，下同）

Region Type Bytes Ratio

...

█ Record Header 6015 36.71%

█ Record Data 9624 58.74%

█ Page Directory 602 3.67%

█ FIL Trailer 8 0.05%

░ Garbage 0 0.00%

Free 15 0.09%

#最后只剩15字节空闲，而不像叶子节点那样有1/16空闲空间

再再次提醒，这都是基于只有一个INT列并作为主键的测试结果。如果是其他主键类型，或者不是顺序追加写入的模式，则结论可能就不是这个了。

4、疑问1：innodb page预留的1/16空闲空间做什么用的

测试到上面时，我们可能会个疑问：什么情况下，能把预留的1/16那部分空闲空间给用上呢？

我们再回顾下前面的文档说明：

An innodb_fill_factor setting of 100 leaves 1/16 of the space in clustered index pages free for future index growth.

凭直觉，我认为是用于需要“增长(读cháng)/扩充”方式更新某条记录时所需，而不是用于写入新记录。例如，c1列定义为VARCHAR(10)，第一次存储时只写了5个字节，后来做了一次更新，把它从5个字节增长到10个字节，称为“增长”更新。像下面这样

# c1列原值是 'abcde'

update t1 set c1='abcdeabcde' where i=1;

我们创建一个新的测试表t2，这次增加一个可变长字符串列c1

CREATE TABLE `t2` (

`i` int(10) unsigned NOT NULL AUTO_INCREMENT,

`c1` varchar(10) NOT NULL DEFAULT '',

PRIMARY KEY (`i`)

) ENGINE=InnoDB;

计算一条记录大概需要多少字节

DB_TRX_ID，6字节

DB_ROLL_PTR，7字节

Record Header，6字节（基础是5字节，外加有个变长列还需要1个字节，共6字节）

因此，一条数据需要消耗 4(INT列) + 6（VARCHAR(10)，但目前只存了5个字符）+6+7+5=28字节

此外，大约每4条记录就需要一个directory slot，每个slot需要2字节

综上，假设可以存储N条记录，则 N*28 + N/4*2 = 15212，可求得N约等于534

插入534条记录后，查看page数据结构图

[root@yejr.me#] innodb_space -s ibdata1 -T innodb/t2 -p 3 page-illustrate

...

Legend (█ = 1 byte):

Region Type Bytes Ratio

...

█ Record Header 3204 19.56%

█ Record Data 11748 71.70%

█ Page Directory 268 1.64%

█ FIL Trailer 8 0.05%

░ Garbage 0 0.00%

Free 1036 6.32%

用innblock工具佐证一下

[root@yejr.me#] innblock innodb/t2.ibd scan 16

...

Datafile Total Size:98304

===INDEX_ID:136

level0 total block is (1)

block_no: 3,level: 0|*|

确认当前只有一层高度，还没分裂成两层。

进行一次 “增长”更新一条记录后，看能不能把预留的空间给利用起来而不是分裂出一个新page

[root@yejr.me]>update t2 set c1='abcdeabcde' where i=1;

Query OK, 1 row affected (0.00 sec)

Rows matched: 1 Changed: 1 Warnings: 0

# 确认还是只有一层高度，树没有分裂

[root@yejr.me#] innblock innodb/t2.ibd scan 16

...

Datafile Total Size:98304

===INDEX_ID:136

level0 total block is (1)

block_no: 3,level: 0|*|

# 再查看下page数据结构图

[root@yejr.me#] innodb_space -s ibdata1 -T innodb/t2 -p 3 page-illustrate

...

Legend (█ = 1 byte):

Region Type Bytes Ratio

...

█ Record Header 3204 19.56%

█ Record Data 11753 71.73%

█ Page Directory 266 1.62%

█ FIL Trailer 8 0.05%

░ Garbage 28 0.17%

Free 1005 6.13%

从上面这个结果可以看到几点

看到Garbage是28字节，也就是i=1的那条旧数据（长度不够存储新记录，需要新写入并删除旧记录）

看到Record Data增加了5字节，因为我们对i=1那条记录的c1列增加了5字节

看到Free少了31字节，那是因为“增长”更新后的i=1记录总长度是31字节，它需要从Free里分配新空间来存储

因此我们确认：聚集索引没有分裂，而是优先把Free空间给利用起来了。

5、疑问2：Garbage空间可以被重用吗

5.1 先回答问题，Garbage空间是可以被重用的

在我们做逐次“增长”更新了50条记录后，这时发现Garbage比较大，但Free已经几乎用完了

Region Type Bytes Ratio

...

█ Record Header 3204 19.56%

█ Record Data 11998 73.23%

█ Page Directory 268 1.64%

█ FIL Trailer 8 0.05%

░ Garbage 756 4.61%

Free 30 0.18%

也就是在这时，如果按照常理，再做一次“增长”更新，就会造成当前的page存储不下，会进行分裂，但事实上真是如此吗？

在继续做一次“增长”更新后，我们发现，实际上此时会把Garbage的空间给重整了，然后继续利用起来，而不是立即进行分裂

# 已有50条记录被“增长”更新了

[root@yejr.me]>select count(*) from t2 where c1='abcdeabcde';

+----------+

| count(*) |

+----------+

| 50 |

+----------+

1 row in set (0.00 sec)

# 继续“增长”更新

[root@yejr.me]>update t2 set c1='abcdeabcde' where i=52;

Query OK, 1 row affected (0.00 sec)

Rows matched: 1 Changed: 1 Warnings: 0

# 确认更新成功

[root@yejr.me]>select count(*) from t2 where c1='abcdeabcde';

+----------+

| count(*) |

+----------+

| 51 |

+----------+

# 查看数据结构

Region Type Bytes Ratio

...

█ Record Header 3204 19.56%

█ Record Data 12003 73.26%

█ Page Directory 268 1.64%

█ FIL Trailer 8 0.05%

░ Garbage 0 0.00%

Free 781 4.77%

# 此时发现Garbage为0，而Free值增大了，明显是把Garbage的空间给重整后再次利用了，很好

我们可以再次得到几条结论

一条记录被“增长”更新后，旧记录会被放到Garbage队列中，除非此时插入新记录的长度小于等于旧记录的长度，否则该记录总是不会被重用起来（也可参考这篇文章 innblock | InnoDB page观察利器）

当空闲空间全部用完后，若此时Garbage队列不为0的话，则会对其进行重整后，变成可用空间再次被分配

如果是“缩短”的更新方式，缩减的空间并不会进入Garbage队列，而是被标记为碎片空间，这种无法被重用（除非全表重建）

5.2 Garbage空间延伸测试，更新数据的数据后面有其他数据

再来看个更为神奇的案例（这次更新的记录，在它后面有其他记录“阻碍”它）

# 插入两条记录

insert into t2 select 0, 'abcde';

# 观察数据结构（只保留几个有用信息）

█ Record Header 12 0.07%

█ Record Data 44 0.27%

░ Garbage 0 0.00%

Free 16196 98.85%

# 对第一条记录先做一次“增长”更新

update t2 set c1='abcdeabcde' where i=1;

# 观察数据结构（只保留几个有用信息）

█ Record Data 49 0.30%

░ Garbage 28 0.17%

Free 16163 98.65%

# 再做一次“缩短”更新

update t2 set c1='abcdeabc' where i=1;

# 观察数据结构（只保留几个有用信息）

█ Record Data 47 0.29%

░ Garbage 28 0.17%

Free 16165 98.66%

# 又做一次“增长”更新

update t2 set c1='abcdeabcde' where i=1;

# 观察数据结构（只保留几个有用信息）

█ Record Data 49 0.30%

░ Garbage 59 0.36%

Free 16132 98.46%

最后发现Garbage队列中有两条记录，也就是两次“增长”更新都导致旧记录被删除，无法被重用。即便第二次是“缩短”更新后产生了剩余碎片，然后再次被“增长”更新，也无法原地更新，需要新写入一条记录。

5.3 Garbage空间延伸测试，更新数据的数据后面没有其他数据

再做个下面的测试案例。这次表里只有一条记录（在它后面没有其他记录“阻碍”它），那么在后面的更新中，都可以原地更新，即便是“增长”更新，旧记录也不需要先被删除后新写一条记录。

# 只插入一条记录

insert into t2 select 0, 'abcde';

# 观察数据结构（只保留几个有用信息）

█ Record Data 22 0.13%

░ Garbage 0 0.00%

Free 16224 99.02%

# 先做一次“增长”更新

update t2 set c1='abcdeabcde' where i=1;

# 观察数据结构

█ Record Data 27 0.16%

░ Garbage 0 0.00%

Free 16219 98.99%

# 再做一次“缩短”更新（缩短了两个字节）

update t2 set c1='abcdeabc' where i=1;

# 观察数据结构

█ Record Data 25 0.15%

░ Garbage 0 0.00%

Free 16221 99.01%

# 又做一次“增长”更新

update t2 set c1='abcdeabcde' where i=1;

# 观察数据结构（和第一次被“增长”更新后一样了）

█ Record Data 27 0.16%

░ Garbage 0 0.00%

Free 16219 98.99%

6、要点总结

InnoDB聚集索引由非叶子节点（non leaf page）和叶子节点（leaf page）组成

在叶子节点中需要存储整行数据（除了overflow的部分列），因此可存储的记录数一般更少些

在non leaf page中只需要存储聚集索引列（主键键值），因此可存储的记录数一般更多些

对变长列，尽量（比如从业务上想办法）不要反复变长（无论是增长还是缩短）更新

innodb_ruby不错，不过解析5.6及以上版本可能有些地方会不准确，可以用innblock工具辅助配合

我不是源码级MySQL内核开发者，水平有限，文中难免有误之处，还请多指教。

Enjoy MySQL :)