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 Offset ╭────────────────────────────────────────────────────────────────╮ 0 │█████████████████████████████████████▋██████████████████████████│ 64 │█████████▋███████████████████▋████████████▋████████████▋████▋███│ 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'; 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空间延伸测试，更新数据的数据后面没有其他数据
再做个下面的测试案例。这次表里只有一条记录（在它后面没有其他记录“阻碍”它），那么在后面的更新中，都可以原地更新，即便是“增长”更新，旧记录也不需要先被删除后新写一条记录。
6、要点总结
- InnoDB聚集索引由非叶子节点（non leaf page）和叶子节点（leaf page）组成
- 在叶子节点中需要存储整行数据（除了overflow的部分列），因此可存储的记录数一般更少些
- 在non leaf page中只需要存储聚集索引列（主键键值），因此可存储的记录数一般更多些
- 对变长列，尽量（比如从业务上想办法）不要反复变长（无论是增长还是缩短）更新
- innodb_ruby不错，不过解析5.6及以上版本可能有些地方会不准确，可以用innblock工具辅助配合
我不是源码级MySQL内核开发者，水平有限，文中难免有误之处，还请多指教。Enjoy MySQL :)