歡迎關注筆者的公眾號：【阿飛的博客】黄鳍，首發(fā)都在這里＝嬲酢：沙选葫松！

這篇文章深入講解InnoDB如何在邏輯上構造它的索引，并深入了解索引上的葉子節(jié)點的結構胁艰，然后幾乎精確的計算索引樹高度款筑，深度好文，你一定不要錯過腾么。

一些術語

在深入了解索引以及葉子節(jié)點結構之前奈梳，我們先提前了解一些專業(yè)術語：B+Tree, ROOT, leaf和level，為了接下來更好的掌握InnoDB的索引解虱。

• B+Tree

InnoDB用B+Tree構造它的索引（MyISAM也是一樣的）颈嚼，當數據不能完全加載到內存中，需要從磁盤讀取時饭寺，這時候B+Tree結構是非常有效的。它能保證訪問任何數據的效率叫挟，查找索引過程中每次讀取事實上就是一次IO艰匙，整個查找過程主要與索引樹的高度有關。

• ROOT

每一個索引樹都是從一個ROOT頁開始抹恳，它的位置是固定的员凝，永遠被保存在InnoDB的數據字典中，ROOT頁就是訪問索引樹的起點奋献。索引樹可能只有一個ROOT頁健霹，也可能有成百上千個頁旺上，這時候就是多級樹，并且樹的高度超過1糖埋。

• leaf

索引樹的每個頁都與葉子（leaf）頁或者非葉子（non-leaf）頁相關聯宣吱。葉子頁包含實際的行數據，非葉子頁只包含指向非葉子頁或者葉子頁的指針瞳别。索引樹是平衡的征候，B+Tree中的B是Balance的意思，而不是Binary祟敛。所以疤坝，索引樹的所有分支有相同的深度。

• level

InnoDB索引樹中每個頁都有一個level值馆铁，其中：葉子頁level=0跑揉，從葉子頁往ROOT頁，level值遞增埠巨。ROOT頁的level值加1就是樹的深度（例如葉子頁level=0历谍；ROOT頁level=1，那么索引樹高度為2）乖订。那些既不是葉子頁扮饶，也不是ROOT頁的頁被稱為內部（internal）頁。

• page directory

即頁目錄（就跟樹目錄的原理差不多）乍构，它是一個大小為2個字節(jié)的指向4~8個記錄的指針甜无，它的作用是為了改進遍歷一個索引頁的性能。如果沒有頁目錄哥遮，即使二分法查詢岂丘，如果是擁有大概1000個記錄的非葉子頁，最多需要近10次的比較（2^10≈1000）眠饮，并且索引頁有多少級奥帘，這樣的比較要成倍增加。

有了頁目錄后仪召，我們就可以先用二分法從頁目錄中找到目標KEY所在的目錄寨蹋，然后通過頁目錄這個指針，找到目標KEY所在的只有4~8個記錄的數組中扔茅。我們假設每個頁目錄平均指向5個記錄已旧，那么，1000個記錄的非葉子頁召娜，需要200個頁目錄运褪，二分法查找只需要8次（2^8=256），整個遍歷過程少了20%的開銷。

葉子&非葉子頁

對于葉子頁和非葉子頁秸讹，每個記錄都包含一個指向下一個記錄的指針檀咙。它存儲了下一個記錄的offset值（相對當前頁的offset）。一個索引頁以下確界（Infimum）開始璃诀，以KEY遞增的方式連接所有記錄弧可，并以上確界（Supremum）結束。

• 葉子頁

葉子頁包含了其他非KEY的值文虏，這些值也是每個記錄中的部分數據（假設表有3列：id, name, age侣诺。那么id就是KEY，name和age都是非KEY氧秘。KEY和非KEY組成完整的記錄）：

簡化的B+Tree葉子頁

如上圖所示年鸳，這個葉子頁有兩個Record：一個Record的Key是0，并且還有非Key的值A丸相；另一個Record的Key是1搔确，并且還有非Key的值B。

• 非葉子頁

非葉子頁的結構與葉子頁的結構大同小異灭忠，不同的地方是膳算，非葉子頁中保存是子頁的頁號。而且并不保存一個明確的KEY弛作，而是保存一個Min Key涕蜂，這個字段表示的是他們指向的子頁的最小KEY：

簡化的B+Tree非葉子頁

如上圖所示，這個非葉子頁有兩個Record：其中一個Record的Min Key為0映琳，并且Page為4机隙，表示它指向的子頁的頁號為4，并且它的最小記錄為0萨西；我們根據這個視圖可以得出結論有鹿，這個索引樹對應的表的id最小值肯定是0（因為這個頁的頁號是3，page 3表示ROOT頁）谎脯。

• 相同等級的索引頁

許多索引遠不止一個頁葱跋，那么就會有很多級（level）。所以源梭，許多頁會被以升序和降序的方式用雙向鏈表串聯起來娱俺，每個頁都包含了指向前一頁和下一頁的指針。需要注意的是废麻，只有l(wèi)evel相同的頁才會被串聯起來矢否，例如葉子頁相互串聯成雙向鏈表，level 1 的頁相互串聯成雙向鏈表脑溢。如下圖所示，是level=0即葉子頁相互串聯成的雙向鏈表：

0 level leaf page

剖析一個索引頁

接下來讓我們深入研究一個B+Tree索引頁的內部，完全掌握一個默認16k大小的索引頁里面都保存了一些什么數據屑彻，索引頁的細節(jié)圖如下所示：

索引頁細節(jié)圖

我們可以通過前文《innodb_ruby：窺探InnoDB的神器》提供的SQL和存儲過程稍微修改验庙，然后創(chuàng)建一張名為tk_afei的InnoDB表，并插入1000條數據社牲，然后借助innodb_ruby命令的一些模式可以驗證上面的B+TREE索引頁視圖粪薛。

space-index-pages-summary模式能夠得到整個索引樹的概要信息，結果如下所示：

[afei@afei mysql]# innodb_space -s ibdata1 -T afei/tk_afei space-index-pages-summary
page        index   level   data    free    records 
3           54      1       39      16213   3       
4           54      0       7462    8648    287     
5           54      0       14924   1044    574     
6           54      0       3614    12572   139     
7           0       0       0       16384   0

這個結果可以得出一些結論：

• 頁號為3的是ROOT頁（因為它的level是1）搏恤，并且ROOT頁只有3個記錄违寿；
• 頁號為4、5和6的是葉子節(jié)點（level為0）熟空，每個葉子頁都有上百個記錄藤巢，葉子頁總計有287+574+139=1000個記錄；
• 頁號7總計16384即16k空間還沒有任何數據息罗。

通過page-records模式查看頁號為3的索引頁內容掂咒，由結果可知，只有3個記錄迈喉，且指針分別指向#4绍刮，#5，#6（#N表示頁號N）：

[afei@afei mysql]# innodb_space -s ibdata1 -T afei/tk_afei -p 3 page-records
Record 125: (id=1) → #4
Record 138: (id=288) → #5
Record 151: (id=862) → #6

俗話說的好：一圖勝前言挨摸。在講解一個索引頁的內容時孩革，我們通過命令：innodb_space -s ibdata1 -T afei/tk_afei -p 6 page-illustrate查看頁號為6的索引頁的完整可視化試圖（其中offset在896~15936之間的空間省略，否則圖片太長）：

innodb index page

從這張圖中得运，我們能清晰的看到一個16k的索引頁到底包含了哪些內容膝蜈。從這張圖得到的一些信息如下（色彩對應即可，比如綠色就知道是Index Header）：

• 第一行offset為[0, 63]中的茶色部分就是FIL Header澈圈，即這個索引頁的頭指針彬檀，并且占用38字節(jié)。
• 第一行與第二行的綠色就是Index Header瞬女，占用36字節(jié)窍帝。
• 接下來就是File Segment Header，占用20個字節(jié)诽偷。
• 然后就是下確界和上確界坤学，都是占用13個字節(jié)。
• 中間最多的就是Record Header和Record Data即索引頁里的指針和數據（主鍵）报慕。
• 最后兩行總計34個小方塊就是Page Directory深浮。
• 最后一行的最后一小部分就是FIL Trailer，也就是當前索引頁的尾指針眠冈，占用8個指針飞苇。

計算索引樹高度

我在之前的文章中初略的講解了如何計算索引樹高度菌瘫，方法比較粗糙，不夠嚴謹布卡。今天雨让，我們根據剛才對索引頁的深入剖析，以及索引頁結構視圖忿等，以更加精確的方式計算索引樹高度栖忠。

我們知道一個索引樹是由葉子頁和非葉子頁組成。所以贸街，計算索引樹高度的關鍵就是如果計算一個16k大小的葉子頁和非葉子上能保存多少個記錄庵寞。

通過上面的page-illustrate模式結果，我們能夠知道每個索引頁都有一些固定的數據：

• 38個字節(jié)的FIL Header
• 36個字節(jié)的Index Header
• 20個字節(jié)的File Segment Header
• 13個字節(jié)的Infimum
• 13個字節(jié)的Supremum
• 8個字節(jié)的FIL Trailer

總計128個字節(jié)薛匪。

剩下的空間全部用來保存Record Header捐川，Record Data和Page Directory。之前我們已經得知ROOT頁信息如下：

page    index   level   data    free    records 
3       54      1       39      16213   3

所以一個16k大小的索引頁內容為：128（固定數據占用字節(jié)數）+ 39（數據） + 4（Page Directory） + 16213（Free空間蛋辈，即還沒填滿） = 16384（每個索引頁的大惺羰啊）。

到了這里冷溶，要計算一個葉子頁和非葉子頁能保存多少記錄的關鍵就剩下如何計算每個記錄的大小了渐白。

• 葉子頁

對于任意一個葉子葉子，其記錄尺寸計算公式如下：

Record Size = 5（header）+ 4（int類型的PK）+ 6（TRX_ID）+ 7（ROLL_PTR）+ N（Non-key fields）

這個公式可以通過如下方式進行驗證：

-- 創(chuàng)建一張表
CREATE TABLE tk3_afei (
  id INT UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
  num int not null,
  age int not null
) ENGINE=InnoDB;

-- 用存儲過程插入1004條數據后逞频，再插入1條數據纯衍，對比前后，我們發(fā)現page為6的free值從8446減少到了8416（records數從256增加到257）：
[root@mysql]# innodb_space -s ibdata1 -T afei/tk3_afei space-index-pages-summary
page        index   level   data    free    records 
3           58      1       39      16213   3       
4           58      0       7470    8658    249     
5           58      0       14970   1036    499     
6           58      0       7680    8446    256     
7           0       0       0       16384   0       
[root@mysql]# innodb_space -s ibdata1 -T afei/tk3_afei space-index-pages-summary
page        index   level   data    free    records 
3           58      1       39      16213   3       
4           58      0       7470    8658    249     
5           58      0       14970   1036    499     
6           58      0       7710    8416    257     
7           0       0       0       16384   0

也就是說一條記錄（1005, 1005, 26）占用了8446-8416=30個字節(jié)苗胀。這30個字節(jié)計算公式如下：

5（header）+ 4（int類型的PK）+ 6（TRX_ID）+ 7（ROLL_PTR）+ 4*2（2個int類型的Non-key fields）= 30 個字節(jié)襟诸。

所以，葉子頁能保存的記錄數B計算方式如下：

1. 先計算每個記錄大谢：5+4+6+7+8=30個字節(jié)歌亲；
2. 再計算每個葉子頁能保存的記錄數B：那么30*B+2*B/5+128=16384（2*B/5表示每5個記錄需要一個頁目錄，每個頁目錄大小是2個字節(jié)）澜驮，所以B≈535陷揪；

• 非葉子頁

非葉子頁由于不需要保存非KEY字段的值，所以計算方式略有不同杂穷。對于任意一個非葉子節(jié)點悍缠，其能保存的記錄數B計算方式如下：

1. 先計算每個記錄大小（Record Data）：4+4=8字節(jié)（需要保存指向子葉的頁號耐量，以及Min Key兩個int類型字段的值）飞蚓；
2. 每個指針的大小（Record Header）為8廊蜒；
3. 計算每個非葉子頁能保存的記錄數B：那么(8+8)*B+2*B/5+128=16384趴拧，所以B≈991溅漾；

• 索引樹高度

計算索引樹高度時，我們做如下假設：

表擁有16個列著榴，其中主鍵是int類型樟凄，并且還有5個int類型和10個varchar類型的其他列，平均每個varchar保存10個字節(jié)長度的字符串兄渺。那么這張表的每個記錄大小是：5+4+6+7+(4*5+10*10)=142≈150

另外，通過上面的計算可知汰现，一個非葉子頁可以保存1000左右的記錄挂谍，而一個葉子頁只可以保存150個左右記錄（與我們的表保存的記錄有很大的關系）。我們假設有一個完美的B+Tree索引瞎饲，每一個頁都填滿了口叙，那么索引樹的高度和表能容納的最大數據量關系如下（其中：k表示千，m表示百萬嗅战，b表示十億）：

所以妄田，主鍵要設計的盡可能的小。如果用一個大的主鍵可能引起B(yǎng)+Tree低效驮捍，因為無論如何疟呐，主鍵值會被保存在非葉子頁中，主鍵越大东且，非葉子頁中的主鍵占用的空間就越大启具，這就意味著，非葉子頁存儲的指針更小珊泳，從而導致索引樹越高鲁冯。

一個完整的索引樹

最后，我們能得出一個多級索引樹的大概示意圖如下圖所示色查，正如前面所描述的薯演，所有l(wèi)evel相同的頁通過雙向鏈表相互串聯，在每個頁中秧了，記錄按照遞增的方式單向鏈表串聯跨扮，非葉子頁包含的是指針（包含了指向它的子葉的頁號和Min Key），而不是非KEY的行數據：

B+Tree Structure