【Java面試】Mysql為什麼使用B+Tree作為索引結構
- 2022 年 6 月 14 日
- 筆記
一個工作8年的粉絲私信了我一個問題。
他說這個問題是去阿裏面試的時候被問到的，自己查了很多資料也沒搞明白，希望我幫他解答。
問題是： 「Mysql為什麼使用B+Tree作為索引結構」
關於這個問題，看看普通人和高手的回答。
普通人：
B+數它的特徵就是相對B數來說他的這個非葉子節點不存數據，所有的數據都存在葉子節點
相對於B數來說他的查詢次數IO次數會更穩。
高手：
關於這個問題 ，我從幾個方面來回答。
首先，常規的數據庫存儲引擎，一般都是採用B樹或者B+樹來實現索引的存儲。
因為B樹是一種多路平衡樹，用這種存儲結構來存儲大量數據，它的整個高度會相比二叉樹來說，會矮很多。
而對於數據庫來說，所有的數據必然都是存儲在磁盤上的，而磁盤IO的效率實際上是很低的，特別是在隨機磁盤IO的情況下效率更低。
所以樹的高度能夠決定磁盤IO的次數，磁盤IO次數越少，對於性能的提升就越大，這也是為什麼採用B樹作為索引存儲結構的原因。
但是在Mysql的InnoDB存儲引擎裏面，它用了一種增強的B樹結構，也就是B+樹來作為索引和數據的存儲結構。
相比較於B樹結構，B+樹做了幾個方面的優化。
- B+樹的所有數據都存儲在葉子節點，非葉子節點只存儲索引。
- 葉子節點中的數據使用雙向鏈表的方式進行關聯。
使用B+樹來實現索引的原因，我認為有幾個方面。
- B+樹非葉子節點不存儲數據，所以每一層能夠存儲的索引數量會增加，意味着B+樹在層高相同的情況下存儲的數據量要比B樹要多，使得磁盤IO次數更少。
- 在Mysql裏面，範圍查詢是一個比較常用的操作，而B+樹的所有存儲在葉子節點的數據使用了雙向鏈表來關聯，所以在查詢的時候只需查兩個節點進行遍歷就行，而B樹需要獲取所有節點，所以B+樹在範圍查詢上效率更高。
- 在數據檢索方面，由於所有的數據都存儲在葉子節點，所以B+樹的IO次數會更加穩定一些。
- 因為葉子節點存儲所有數據，所以B+樹的全局掃描能力更強一些，因為它只需要掃描葉子節點。但是B樹需要遍歷整個樹。
另外，基於B+樹這樣一種結構，如果採用自增的整型數據作為主鍵，還能更好的避免增加數據的時候，帶來葉子節點分裂導致的大量運算的問題。
總的來說，我認為技術方案的選型，更多的是去解決當前場景下的特定問題，並不一定是說B+樹就是最好的選擇，就像MongoDB裏面採用B樹結構，本質上來說，其實是關係型數據庫和非關係型數據庫的差異。
以上就是我對這個問題的理解。
總結
對於「為什麼要選擇xx技術」的問題，其實很好回答。
只要你對這個技術本身的特性足夠了解，那麼自然就知道為什麼要這麼設計。
就像，我們在業務開發中，知道什麼時候使用List，什麼時候使用Map，道理是一樣的。
如果有任何面試問題、職業發展問題、學習問題，都可以私信我。
版權聲明：本博客所有文章除特別聲明外，均採用 CC BY-NC-SA 4.0 許可協議。轉載請註明來自
Mic帶你學架構！
如果本篇文章對您有幫助，還請幫忙點個關注和贊，您的堅持是我不斷創作的動力。歡迎關注「跟着Mic學架構」公眾號公眾號獲取更多技術乾貨！
