MySql的InnoDB的三層B+樹可以儲存兩千萬左右條資料的計算邏輯

總結/朱季謙

B+樹是一種在非葉子節點存放排序好的索引而在葉子節點存放資料的資料結構，值得注意的是，在葉子節點中，儲存的並非只是一行表資料，而是以頁為單位儲存，一個頁可以包含多行表記錄。非葉子節點存放的是索引鍵值和頁指標。

那麼，在MySql資料庫裡，一個頁的大小是多少呢？

可以通過查詢語句進行檢視：show variables like 'innodb_page_size'

查詢結果16384位元組，可以通過1kb等於1024位元組方式，計算出16384/1024 = 16kb，說明MySql資料庫預設頁大小是16kb。

假設一行資料佔用1kb的空間大小，然而實際上，除去欄位很多的寬表外，其實很多簡單的錶行記錄都遠達不到1kb空間佔比。這裡我們用最壞的情況來假設一行記錄大小為1kb，那麼，一個16kb的頁就可以儲存16行資料。

接下來，我們先畫一個只要兩層高的B+樹結構圖。

假設第一層根節點存在以下情況：索引1對應頁指標地址10，索引5對應頁指標地址30，索引8對應頁指標地址50。

既然已經知道一個葉子節點的頁中可以存放16條資料，那麼，只需要知道根節點存在多少頁地址指標即可，就能通過 “根節點頁地址指標數量 * 單個葉子節點記錄行數”。

那麼，根節點能存放多少個 索引：頁地址指標的資料呢？

在一個節點大小為16kb的情況下，我們只需要知道索引鍵值和頁地址指標兩者大小總和即可。

根據一些資料得知，在MySql資料庫當中，指標地址大小為6位元組，若索引是bigint型別，那麼就為8位元組，兩者加起來總共是14位元組。

接下來，通過以下計算步驟，就可以統計出兩層的B+數大概可以儲存多少條記錄資料——

一、先計算一個節點的位元組大小：16kb * 1024 = 16384 位元組。

二、16384 位元組 / 14 位元組 = 1170 ，意味著，根節點有1170個頁地址指標，然後，每個頁地址指標指向的葉子節點可以存放16條資料。

三、那麼，根據“根節點頁地址指標數量 * 單個葉子節點記錄行數”，計算1170 * 16 = 18720 條記錄，可見，兩層B+數可以存放18720條記錄，當然，這個數字是存在出入的，只是作為參考。

既然已經知道兩層B+數可以存放18720條資料，那麼，三層不就可以進一步算出了嗎？

一、根節點最多有1170個指標數；

二、說明第二層最多會有1170個子節點，同時，每個子節點裡最多有1170個指標數；

三、那麼，第三層葉節點數量，可以通過 “第二層最多有1170個節點數量 * 每個節點裡最多有1170個指標數量”，也就是1170 * 1170

四、最後，計算第三層所有葉子數量 * 各個葉子節點存放的16條資料；

最後，1170 * 1170 * 16 = 21902400，得出兩千萬左右條資料。

綜上所述，若面試當中遇到這樣問題，可以按照這個流程計算回答。