面試官：InnoDB一棵B +樹可以存放多少行資料？

一個問題？

InnoDB一棵B +樹可以存放多少行資料？這個問題的簡單回答是：約2千萬，為什么是這么多呢？因為這是可以算出來的，要搞清楚這個問題，我們先從InnoDB索引資料結構，資料組織方式說起，

我們都知道計算機在存盤資料的時候，有最小存盤單元，這就好比我們今天進行現金的流通最小單位是一毛，在計算機中磁盤存盤資料最小單元是旋轉，一個體積的大小是512位元組，而檔案系統（例如XFS / EXT4）他的最小單元是塊，一個塊的大小是4k，而對于我們的InnoDB存盤引擎也有自己的最小存盤單元-頁（頁），一個頁面的大小是16K，

下面幾張圖可以幫你理解最小存盤單元：

檔案系統中一個檔案大小只有1個位元組，但必須占磁盤上4KB的空間，

innodb的所有資料檔案（后綴為ibd的檔案），他的大小始終都是16384（16k）的整數倍，

磁盤，檔案系統，InnoDB存盤引擎都有各自的最小存盤單元，

在MySQL中我們的InnoDB頁的大小替換是16k，當然也可以通過引數設定：

 mysql> show variables like 'innodb_page_size';
 ?
 +------------------+-------+
 ?
 | Variable_name | Value |
 ?
 +------------------+-------+
 ?
 | innodb_page_size | 16384 |
 ?
 +------------------+-------+
 ?
 1 row in set (0.00 sec)  

資料表中的資料都是存盤在頁面中的，所以一個頁面中能存盤多少行資料呢？假設一行資料的大小是1k，那么一個頁面可以存放16行這樣的資料，

B +樹

如果資料庫只按這樣的方式存盤，那么如何查找資料就成為一個問題，因為我們不知道要查找的資料存在該頁中，也不可能把所有的頁遍歷一遍，那樣太慢了，所以人們想了一個辦法，用B +樹的方式組織這些資料，如下所示：

我們先將資料記錄按主鍵進行排序，分別放置在不同的頁面中（為了便于理解我們這里一個頁面中只存放3條記錄，實際情況可以放置很多），除了存放資料的頁面以外，還有存放鍵值+指標的頁面，則中頁 號= 3的頁面，該頁面放置鍵值和指向資料頁的指標，這樣的頁面由N個鍵值+指標組成，當然它也是排好序的，這樣的資料組織形式，我們稱為索引組織表，現在來看下，要查找一條資料，怎么查？

如select * from user where id=5;

這里id是主鍵，我們通過這棵棵B +樹來查找，首先找到根頁，你怎么知道用戶表的根頁在哪呢？其實每張表的根頁位置在表空間檔案中是固定的，即頁 number = 3的頁面（這點我們逐步獲得進一步證明），找到根頁面后通過二分查找法，定位到id = 5的資料應該在指標P5指向的頁面中，那么進一步去頁面 number = 5的頁面中查找，同樣通過二分查詢法即可找到id = 5的記錄：

 5  |  zhao2  |  27    

現在我們清楚了InnoDB中主鍵索引B +樹是如何組織資料，查詢資料的，我們總結一下：

• 1，InnoDB存盤引擎的最小存盤單元是頁，頁可以用于存放資料也可以用于存放鍵值+指標，在B +樹中葉子放置的資料，非葉子存放的存放鍵值+指標，

• 2，索引組織表通過非葉子癌細胞的二分查找法以及指標確定資料在該頁中，且在去資料頁中查找到需要的資料；

那么回到我們開始的問題，通常一棵B +樹可以存放多少行資料？

一棵B +樹可以存放多少行資料？

這里我們先假定B +樹高為2，即存在一個根節點和幾個個葉子計數器，那么這棵B +樹的存放總記錄數為：根指標指標*單個葉子例程記錄行數，

上文我們已經說明了片段葉子暫存器（頁）中的記錄數= 16K / 1K = 16，（此處假設一行記錄的資料大小為1k，實際上現在很多互聯網業務資料記錄大小通常就是1K左右），

那么現在我們需要計算出非葉子節點能量放置多少指標，其實這也很好算，我們假設主鍵ID為bigint型別，長度為8位元組，而指標大小在InnoDB原始碼中設定為6位元組，這樣一共14位元組，我們一個頁面中能存放多少這樣的單元，實際上就代表有多少指標，即16384/14 = 1170，那么可以算出一棵高度為2的B +樹，能存放1170 * 16 = 18720條這樣的資料記錄，

根據同樣的原理我們可以算出一個高度為3的B +樹可以存放：1170 1170 16 = 21902400條這樣的記錄，所以在InnoDB中B +樹高度一般為1-3層，它可以滿足千萬級的資料存盤，在查找資料時一次頁的查找代表一次IO，所以通過主鍵索引查詢通常只需要1-3次IO操作即可查找到資料，

怎么得到InnoDB主鍵索引B +樹的高度？

在InnoDB的表空間檔案中，約定的 頁碼為3 的代表主鍵索引的根頁，而在根頁偏移量為 64 的地方存放了該B +樹的頁級別如果頁級別為1，樹高為2，頁， 級別為2，則樹高為3，即B +樹的高度=頁面級+ 1;下面我們重置實際環境中嘗試找到這個頁面級別，

在實際操作之前，您可以通過InnoDB元資料表確認主鍵索引根頁的頁碼為3，您也可以從《 InnoDB存盤引擎》這本書中得到確認，

 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; 

執行結果：

可以修剪資料庫dbt3下的customer表，lineitem表主鍵索引根頁的頁碼改為3，而其他的二級索引頁 號為4，不在此介紹，

下面我們對資料庫表空間檔案做想相關的決議：

因為主鍵索引B +樹的根頁在整個表空間檔案中的第3個頁開始，所以可以算出它在檔案中的偏移量：16384*3=49152（16384為頁大小），

另外根據《 InnoDB存盤引擎》中的描述在根頁的64偏移量位置前2個位元組，保存了頁面級別的值，因此我們想要的頁面 級別的值在整個檔案中的替換量為：16384*3+64=49152+64=49216，前2個位元組中，

接下來我們用hexdump工具，查看表空間檔案指定重新量上的資料：

linetem表的頁面級別為2，B +樹高度為頁面級別+ 1 = 3；

region表的頁面級別為0，B +樹高度為頁面級別+ 1 = 1；

客戶表的頁面級別為2，B +樹高度為頁面級別+ 1 = 3；

這三張表的資料量如下：

總結：

lineitem表的資料行數為600多萬，B +樹高度為3，客戶表資料行數只有15萬，B +樹高度也為3，都是3，換句話說這兩個表通過索引查詢效率并沒有太大差異，因為都只需要做3次IO，那么如果有一張表行數是一千萬，那么他的B +樹高度依舊是3，查詢效率仍然不會相差太大，

region表只有5行資料，當然他的B +樹高度為1，

最后回顧一道面試題

某些道MySQL的面試題，為什么MySQL的索引要使用B +樹而不是其他樹形結構？某些B樹？

現在這個問題的復雜版本可以參考本文；

他的簡單版本回答是：

因為B樹不管葉子例程還是非葉子例程，都會保存資料，這樣導致在非葉子例程中能保存的指標數量變少（某些資料也稱為扇出），指標少的情況下要保存大量資料，只能增加樹的高度，導致IO操作變多，查詢性能變低；

小結

本文從一個問題出發，逐步介紹InnoDB索引組織表的原理，查詢方式，并結合現有知識，回答該問題，結合實踐來證明，當然為了表述簡單易懂，文中忽略了一些細枝末節，其中一個頁面中不可能所有空間都用作存放資料，它會放置一些少量的其他變數替換page level，等等index number，另外還有頁面的填充因子也導致一個頁面無法全部保存資料，關于二級索引資料存盤取方式可以參考MySQL相關書籍，他的要點是結合主鍵索引進行回表查詢，

最后我把我收集的各大廠經典高頻面試題和Java高級進階、架構師視頻教程送予大家，部分資料如下圖所示：

獲取地址：java進階學習資料，面試題，電子書籍免費獲取

標籤：Java

上一篇：哈夫曼編碼—檔案的壓縮與解壓（Java）

下一篇：Java自學-圖形界面 容器