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，得出兩千萬左右條數據。

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