B+樹是一種在非葉子節(jié)點存放排序好的索引而在葉子節(jié)點存放數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，值得注意的是，在葉子節(jié)點中，存儲的并非只是一行表數(shù)據(jù)，而是以頁為單位存儲，一個頁可以包含多行表記錄。非葉子節(jié)點存放的是索引鍵值和頁指針。
那么，在MySQL數(shù)據(jù)庫里，一個頁的大小是多少呢？
可以通過查詢語句進行查看：show variables like 'innodb_page_size'
查詢結(jié)果16384字節(jié)，可以通過1kb等于1024字節(jié)方式，計算出16384/1024 = 16kb，說明MySql數(shù)據(jù)庫默認(rèn)頁大小是16kb。
假設(shè)一行數(shù)據(jù)占用1kb的空間大小，然而實際上，除去字段很多的寬表外，其實很多簡單的表行記錄都遠(yuǎn)達(dá)不到1kb空間占比。這里我們用最壞的情況來假設(shè)一行記錄大小為1kb，那么，一個16kb的頁就可以存儲16行數(shù)據(jù)。
接下來，我們先畫一個只要兩層高的B+樹結(jié)構(gòu)圖。
假設(shè)第一層根節(jié)點存在以下情況：索引1對應(yīng)頁指針地址10，索引5對應(yīng)頁指針地址30，索引8對應(yīng)頁指針地址50。
第二層節(jié)點作為葉子節(jié)點，存放的是大小為16kb的頁數(shù)據(jù)，頁數(shù)據(jù)里每一行記錄大小為1kb，那么，一個葉子節(jié)點的頁里就可以存放16條數(shù)據(jù)。
既然已經(jīng)知道一個葉子節(jié)點的頁中可以存放16條數(shù)據(jù)，那么，只需要知道根節(jié)點存在多少頁地址指針即可，就能通過 “根節(jié)點頁地址指針數(shù)量 * 單個葉子節(jié)點記錄行數(shù)”。
那么，根節(jié)點能存放多少個 索引：頁地址指針的數(shù)據(jù)呢？
在一個節(jié)點大小為16kb的情況下，我們只需要知道索引鍵值和頁地址指針兩者大小總和即可。
根據(jù)一些資料得知，在MySql數(shù)據(jù)庫當(dāng)中，指針地址大小為6字節(jié)，若索引是bigint類型，那么就為8字節(jié)，兩者加起來總共是14字節(jié)。
接下來，通過以下計算步驟，就可以統(tǒng)計出兩層的B+數(shù)大概可以存儲多少條記錄數(shù)據(jù)——
一、先計算一個節(jié)點的字節(jié)大小：16kb * 1024 = 16384 字節(jié)。
二、16384 字節(jié) / 14 字節(jié) = 1170 ，意味著，根節(jié)點有1170個頁地址指針，然后，每個頁地址指針指向的葉子節(jié)點可以存放16條數(shù)據(jù)。
三、那么，根據(jù)“根節(jié)點頁地址指針數(shù)量 * 單個葉子節(jié)點記錄行數(shù)”，計算1170 * 16 = 18720 條記錄，可見，兩層B+數(shù)可以存放18720條記錄，當(dāng)然，這個數(shù)字是存在出入的，只是作為參考。
既然已經(jīng)知道兩層B+數(shù)可以存放18720條數(shù)據(jù)，那么，三層不就可以進一步算出了嗎？
簡單畫一個三層B+數(shù)的存放數(shù)據(jù)計算邏輯——
一、根節(jié)點最多有1170個指針數(shù)；
二、說明第二層最多會有1170個子節(jié)點，同時，每個子節(jié)點里最多有1170個指針數(shù)；
三、那么，第三層葉節(jié)點數(shù)量，可以通過 “第二層最多有1170個節(jié)點數(shù)量 * 每個節(jié)點里最多有1170個指針數(shù)量”，也就是1170 * 1170
四、最后，計算第三層所有葉子數(shù)量 * 各個葉子節(jié)點存放的16條數(shù)據(jù)；
最后，1170 * 1170 * 16 = 21902400，得出兩千萬左右條數(shù)據(jù)。
綜上所述，若面試當(dāng)中遇到這樣問題，可以按照這個流程計算回答。
