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我話說完

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。