一個(gè)問題****1答倡、InnoDB一棵B+樹可以存放多少行數(shù)據(jù)轰传？這個(gè)問題的簡單回答是：約2千萬。2瘪撇、為****什么是這么多呢获茬？因?yàn)檫@是可以算出來的港庄。

要搞清楚這個(gè)問題，我們先從InnoDB索引數(shù)據(jù)結(jié)構(gòu)恕曲、數(shù)據(jù)組織方式說起鹏氧。
我們都知道計(jì)算機(jī)在存儲(chǔ)數(shù)據(jù)的時(shí)候，有最小存儲(chǔ)單元佩谣。在計(jì)算機(jī)中磁盤存儲(chǔ)數(shù)據(jù)最小單元是扇區(qū)把还，一個(gè)扇區(qū)的大小是512字節(jié)，而文件系統(tǒng)（例如XFS/EXT4）他的最小單元是塊茸俭，一個(gè)塊的大小是4k吊履，而對于我們的InnoDB存儲(chǔ)引擎也有自己的最小儲(chǔ)存單元——頁（Page），一個(gè)頁的大小是16K瓣履。下面幾張圖可以幫你理解最小存儲(chǔ)單元：文件系統(tǒng)中一個(gè)文件大小只有1個(gè)字節(jié)率翅，但不得不占磁盤上4KB的空間。

圖片

圖片

圖片

img在MySQL中我們的InnoDB頁的大小默認(rèn)是16k，當(dāng)然也可以通過參數(shù)設(shè)置：

<pre class="code-snippet__js" data-lang="ruby" style="margin: 0px; padding: 1em 1em 1em 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important; overflow-x: auto; white-space: normal; -webkit-box-flex: 1; flex: 1 1 0%;">mysql> show variables like 'innodb_page_size';``+------------------+-------+``| Variable_name | Value |``+------------------+-------+``| innodb_page_size | 16384 |``+------------------+-------+``1 row in set (0.00 sec)</pre>

數(shù)據(jù)表中的數(shù)據(jù)都是存儲(chǔ)在頁中的归形，所以一個(gè)頁中能存儲(chǔ)多少行數(shù)據(jù)呢托慨？假設(shè)一行數(shù)據(jù)的大小是1k，那么一個(gè)頁可以存放16行這樣的數(shù)據(jù)暇榴。如果數(shù)據(jù)庫只按這樣的方式存儲(chǔ)厚棵，那么如何查找數(shù)據(jù)就成為一個(gè)問題剧辐，因?yàn)槲覀儾恢酪檎业臄?shù)據(jù)存在哪個(gè)頁中歉摧，也不可能把所有的頁遍歷一遍蛾号，那樣太慢了展氓。所以人們想了一個(gè)辦法，用B+樹的方式組織這些數(shù)據(jù)策治。如圖所示：

圖片

img我們先將數(shù)據(jù)記錄按主鍵進(jìn)行排序拐云，分別存放在不同的頁中（為了便于理解我們這里一個(gè)頁中只存放3條記錄田炭，實(shí)際情況可以存放很多）查吊，除了存放數(shù)據(jù)的頁以外谐区，還有存放鍵值+指針的頁，如圖中page number=3的頁逻卖，該頁存放鍵值和指向數(shù)據(jù)頁的指針宋列，這樣的頁由N個(gè)鍵值+指針組成。當(dāng)然它也是排好序的评也。這樣的數(shù)據(jù)組織形式炼杖，我們稱為索引組織表「曷常現(xiàn)在來看下，要查找一條數(shù)據(jù)嘹叫，怎么查？如：

<pre class="code-snippet__js" data-lang="sql" style="margin: 0px; padding: 1em 1em 1em 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important; overflow-x: auto; white-space: normal; -webkit-box-flex: 1; flex: 1 1 0%;">select * from user where id=5;</pre>

這里id是主鍵,我們通過這棵B+樹來查找诈乒，首先找到根頁罩扇，你怎么知道user表的根頁在哪呢？其實(shí)每張表的根頁位置在表空間文件中是固定的怕磨，即page number=3的頁（這點(diǎn)我們下文還會(huì)進(jìn)一步證明）喂饥，找到根頁后通過二分查找法，定位到id=5的數(shù)據(jù)應(yīng)該在指針P5指向的頁中肠鲫，那么進(jìn)一步去page number=5的頁中查找员帮，同樣通過二分查詢法即可找到id=5的記錄：

| 5
| zhao2
| 27
|
| --- | --- | --- |
|
|
|
|

現(xiàn)在我們清楚了InnoDB中主鍵索引B+樹是如何組織數(shù)據(jù)、查詢數(shù)據(jù)的导饲，我們總結(jié)一下：

• InnoDB存儲(chǔ)引擎的最小存儲(chǔ)單元是頁捞高，頁可以用于存放數(shù)據(jù)也可以用于存放鍵值+指針，在B+樹中葉子節(jié)點(diǎn)存放數(shù)據(jù)渣锦，非葉子節(jié)點(diǎn)存放鍵值+指針硝岗。

• 索引組織表通過非葉子節(jié)點(diǎn)的二分查找法以及指針確定數(shù)據(jù)在哪個(gè)頁中，進(jìn)而在去數(shù)據(jù)頁中查找到需要的數(shù)據(jù)袋毙；

那么回到我們開始的問題型檀，通常一棵B+樹可以存放多少行數(shù)據(jù)？這里我們先假設(shè)B+樹高為2听盖，即存在一個(gè)根節(jié)點(diǎn)和若干個(gè)葉子節(jié)點(diǎn)胀溺，那么這棵B+樹的存放總記錄數(shù)為：根節(jié)點(diǎn)指針數(shù)單個(gè)葉子節(jié)點(diǎn)記錄行數(shù)。上文我們已經(jīng)說明單個(gè)葉子節(jié)點(diǎn)（頁）中的記錄數(shù)=16K/1K=16皆看。（這里假設(shè)一行記錄的數(shù)據(jù)大小為1k仓坞，實(shí)際上現(xiàn)在很多互聯(lián)網(wǎng)業(yè)務(wù)數(shù)據(jù)記錄大小通常就是1K左右）。那么現(xiàn)在我們需要計(jì)算出非葉子節(jié)點(diǎn)能存放多少指針悬蔽，其實(shí)這也很好算扯躺，我們假設(shè)主鍵ID為bigint類型，長度為8字節(jié)蝎困，而指針大小在InnoDB源碼中設(shè)置為6字節(jié)录语，這樣一共14字節(jié)，我們一個(gè)頁中能存放多少這樣的單元禾乘，其實(shí)就代表有多少指針澎埠，即16384/14=1170。那么可以算出一棵高度為2的B+樹始藕，能存放117016=18720條這樣的數(shù)據(jù)記錄蒲稳。根據(jù)同樣的原理我們可以算出一個(gè)高度為3的B+樹可以存放：1170117016=21902400條這樣的記錄氮趋。所以在InnoDB中B+樹高度一般為1-3層，它就能滿足千萬級的數(shù)據(jù)存儲(chǔ)江耀。在查找數(shù)據(jù)時(shí)一次頁的查找代表一次IO剩胁，所以通過主鍵索引查詢通常只需要1-3次IO操作即可查找到數(shù)據(jù)。怎么得到InnoDB主鍵索引B+樹的高度祥国？上面我們通過推斷得出B+樹的高度通常是1-3昵观，下面我們從另外一個(gè)側(cè)面證明這個(gè)結(jié)論。在InnoDB的表空間文件中舌稀，約定page number為3的代表主鍵索引的根頁啊犬，而在根頁偏移量為64的地方存放了該B+樹的page level。如果page level為1壁查，樹高為2觉至，page level為2，則樹高為3睡腿。即B+樹的高度=page level+1语御；下面我們將從實(shí)際環(huán)境中嘗試找到這個(gè)page level。在實(shí)際操作之前席怪，你可以通過InnoDB元數(shù)據(jù)表確認(rèn)主鍵索引根頁的page number為3沃暗，你也可以從《InnoDB存儲(chǔ)引擎》這本書中得到確認(rèn)。

<pre class="code-snippet__js" data-lang="sql" style="margin: 0px; padding: 1em 1em 1em 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important; overflow-x: auto; white-space: normal; -webkit-box-flex: 1; flex: 1 1 0%;">SELECT b.name, a.name, index_id, type, a.space, a.PAGE_NO ``FROM information_schema.INNODB_SYS_INDEXES a, information_schema.INNODB_SYS_TABLES b WHERE a.table_id = b.table_id `` AND a.space <> 0;</pre>

執(zhí)行結(jié)果：

圖片

圖片

img因?yàn)橹麈I索引B+樹的根頁在整個(gè)表空間文件中的第3個(gè)頁開始，所以可以算出它在文件中的偏移量：163843=49152（16384為頁大幸呤辍）盛撑。另外根據(jù)《InnoDB存儲(chǔ)引擎》中描述在根頁的64偏移量位置前2個(gè)字節(jié)，保存了page level的值捧搞，因此我們想要的page level的值在整個(gè)文件中的偏移量為：163843+64=49152+64=49216抵卫，前2個(gè)字節(jié)中。接下來我們用hexdump工具胎撇，查看表空間文件指定偏移量上的數(shù)據(jù)：

圖片

img

• linetem表的page level為2介粘，B+樹高度為page level+1=3；

• region表的page level為0晚树，B+樹高度為page level+1=1姻采；

• customer表的page level為2，B+樹高度為page level+1=3爵憎；

圖片

img總結(jié)lineitem表的數(shù)據(jù)行數(shù)為600多萬慨亲，B+樹高度為3婚瓜，customer表數(shù)據(jù)行數(shù)只有15萬，B+樹高度也為3刑棵“涂蹋可以看出盡管數(shù)據(jù)量差異較大，這兩個(gè)表樹的高度都是3蛉签，換句話說這兩個(gè)表通過索引查詢效率并沒有太大差異冈涧，因?yàn)槎贾恍枰?次IO。那么如果有一張表行數(shù)是一千萬正蛙，那么他的B+樹高度依舊是3，查詢效率仍然不會(huì)相差太大营曼。region表只有5行數(shù)據(jù)乒验，當(dāng)然他的B+樹高度為1。最后回顧一道面試題：有一道MySQL的面試題蒂阱，為什么MySQL的索引要使用B+樹而不是其它樹形結(jié)構(gòu)?比如B樹锻全？現(xiàn)在這個(gè)問題的復(fù)雜版本可以參考本文；簡單版本回答是：因?yàn)锽樹不管葉子節(jié)點(diǎn)還是非葉子節(jié)點(diǎn)录煤，都會(huì)保存數(shù)據(jù)鳄厌，這樣導(dǎo)致在非葉子節(jié)點(diǎn)中能保存的指針數(shù)量變少（有些資料也稱為扇出），指針少的情況下要保存大量數(shù)據(jù)妈踊，只能增加樹的高度了嚎，導(dǎo)致IO操作變多，查詢性能變低廊营；本文從一個(gè)問題出發(fā)歪泳，逐步介紹了InnoDB索引組織表的原理、查詢方式露筒，并結(jié)合已有知識呐伞，回答該問題，結(jié)合實(shí)踐來證明慎式。當(dāng)然為了表述簡單易懂伶氢，文中忽略了一些細(xì)枝末節(jié)，比如一個(gè)頁中不可能所有空間都用于存放數(shù)據(jù)瘪吏，它還會(huì)存放一些少量的其他字段比如page level癣防，index number等等，另外還有頁的填充因子也導(dǎo)致一個(gè)頁不可能全部用于保存數(shù)據(jù)掌眠。關(guān)于二級索引數(shù)據(jù)存取方式可以參考MySQL相關(guān)書籍劣砍，他的要點(diǎn)是結(jié)合主鍵索引進(jìn)行回表查詢。參考資料：

• 《MySQL技術(shù)內(nèi)幕:InnoDB存儲(chǔ)引擎》

• http://www.innomysql.com/查看-innodb表中每個(gè)的索引高度/