B+樹層數計算（面試官直呼内行）

B+樹結構簡述

跟其它tree結構一樣，根節點隻有一個，根節點可以為葉子節點或者非葉子節點，B+樹的非葉子節點(包括根節點)可以有多個子節點，它的非葉子節點僅儲存索引列和指針，不儲存具體行記錄；

啥是根節點

最上面那個就叫根節點

啥是非葉子節點

不是葉子節點的節點都叫非葉子節點

啥是葉子節點

最下面那些最終節點就叫葉子節點

如何計算層數

首先搞清楚一個常識，我們都知道計算機在存儲資料的時候，有最小存儲單元，這就好比我們今天進行現金的流通最小機關是一毛

在計算機中磁盤存儲資料最小單元是扇區，一個扇區的大小是 512 位元組，而檔案系統（例如XFS/EXT4）他的最小單元是塊，一個塊的大小是 4k

而對于我們的 InnoDB 存儲引擎也有自己的最小儲存單元——頁（Page），一個頁的預設大小是 16K，page可以儲存指針，也可以儲存行記錄，其中指針指向下一個page的位址

好，知道這個，計算層數就簡單了，我們先假設有兩層，第一層為非葉子節點，儲存指針，第二層為葉子節點，儲存具體行記錄

那麼兩層高度的b+樹能存儲的數量 = 根節點指針數*每個指針對應第二層的行記錄數

ok建議你先捋捋，不着急

根節點指針數

怕你沒認真看上面，我再說一遍，B+樹的非葉子節點僅儲存索引字段和指針，假設主鍵為bigint類型，InnoDB 的bigint占用8個位元組，指針占用6個位元組，8+6=14，是以我們可以得出，一個page能存放的指針個數為16k/(8+6)約等于1170

每個指針對應第二層的行記錄數

再來說說一個page能存儲多少條行記錄，正常的網際網路項目單條行記錄大小約為1k，那麼一個page能存儲的行記錄數為16k/1k=16

是以一個2層高的b+樹能存儲的行記錄數大約為1170*16=18720

3層為1170*1170*16約等于2190w

ok我話說完