InnoDB表聚集索引層高什麼時候發生變化（2）

2.4 什麼時候發生B+樹分裂

如果我們再插入一條記錄，就會發現，t1表原本隻有一層高的B+樹，會分裂成兩層高度

[[email protected]]> 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的全覽圖

[[email protected]#] 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 條記錄。

# 檢視總記錄數
[[email protected]]> select count(*) from t1;
+----------+
| count(*) |
+----------+
|   812890 |
+----------+

# 檢視聚集索引層級
[[email protected]#] 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資料結構圖
[[email protected]#] 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資料結構圖

[[email protected]#] 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工具佐證一下

[[email protected]#] innblock innodb/t2.ibd scan 16
...
Datafile Total Size:98304
===INDEX_ID:136
level0 total block is (1)
block_no:         3,level:   0|*|

确認目前隻有一層高度，還沒分裂成兩層。

進行一次 “增長”更新一條記錄後，看能不能把預留的空間給利用起來而不是分裂出一個新page

[[email protected]]>update t2 set c1='abcdeabcde' where i=1;
Query OK, 1 row affected (0.00 sec)
Rows matched: 1  Changed: 1  Warnings: 0

# 确認還是隻有一層高度，樹沒有分裂
[[email protected]#] innblock innodb/t2.ibd scan 16
...
Datafile Total Size:98304
===INDEX_ID:136
level0 total block is (1)
block_no:         3,level:   0|*|    

# 再檢視下page資料結構圖
[[email protected]#] 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條記錄被“增長”更新了
[[email protected]]>select count(*) from t2 where c1='abcdeabcde';
+----------+
| count(*) |
+----------+
|       50 |
+----------+
1 row in set (0.00 sec)

# 繼續“增長”更新
[[email protected]]>update t2 set c1='abcdeabcde' where i=52;
Query OK, 1 row affected (0.00 sec)
Rows matched: 1  Changed: 1  Warnings: 0

# 确認更新成功
[[email protected]]>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空間延伸測試，更新資料的資料後面沒有其他資料

再做個下面的測試案例。這次表裡隻有一條記錄（在它後面沒有其他記錄“阻礙”它），那麼在後面的更新中，都可以原地更新，即便是“增長”更新，舊記錄也不需要先被删除後新寫一條記錄。

# 隻插入一條記錄
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 :)

InnoDB表聚集索引層高什麼時候發生變化（2）

2.4 什麼時候發生B+樹分裂

3、理論推演，當innodb表聚集索引達到三層高時，大概可以存儲幾條記錄

3.1 分析根節點page

3.2 補充測試：在兩層高度時，根節點最多可以存儲幾條記錄

4、疑問1：innodb page預留的1/16空閑空間做什麼用的

5、疑問2：Garbage空間可以被重用嗎

5.1 先回答問題，Garbage空間是可以被重用的

5.2 Garbage空間延伸測試，更新資料的資料後面有其他資料

5.3 Garbage空間延伸測試，更新資料的資料後面沒有其他資料

6、要點總結

繼續閱讀

轉詳解C#資料庫存取圖檔三大方式

BMP檔案結構及圖像每行位元組計算方法

磁盤結構及在Linux中的命名

mysql優化（sql優化）

資料遷移方法資料遷移原則資料遷移之雙寫方案資料遷移之級聯同步方案

redis叢集資料一緻性_RedisRaft為Redis叢集帶來強大的資料一緻性

寶塔面闆mysql恢複2018.1.8更新

Centos7 MySQL 5.7 安裝MySQL 5.7 安裝

查找入職員工時間排名倒數第三的員工所有資訊

Hibernate使用Hibernate的“3個準備，7個步驟”Hibernate API簡介操作實體對象對象識别

雲計算面試題——mysql/存儲引擎/備份

SQL語言基礎：常用的資料查詢語句

Ubuntu16.04安裝Apache+MySQL+PHP1. 安裝Apache2. 安裝MySQL3. 安裝PHP4. 安裝phpMyAdmin

MySQL的4種隔離級别？出現問題

neo4j之cypher使用文檔

mysql使用source指令導入.sql檔案