為什麼MySQL索引結構採用B+樹?

語言: CN / TW / HK

一位6年經驗的小夥伴去位元組面試的時候被問到這樣一個問題,為什麼MySQL索引結構要採用B+樹?這位小夥伴從來就沒有思考過這個問題。只因為現在都這麼卷,後面還特意查了很多資料,他也希望聽聽我的見解。

另外,我花了1個多星期把往期的面試題解析配套文件準備好了,一共有10萬字,想獲取的小夥伴可以在我的煮葉簡介中找到。

1、B樹和B+樹

一般來說,資料庫的儲存引擎都是採用B樹或者B+樹來實現索引的儲存。首先來看B樹,如圖所示。

B樹是一種多路平衡樹,用這種儲存結構來儲存大量資料,它的整個高度會相比二叉樹來說,會矮很多。

而對於資料庫而言,所有的資料都將會儲存到磁碟上,而磁碟I/O的效率又比較低,特別是在隨機磁碟I/O的情況下效率更低。

所以 高度決定了磁碟I/O的次數,磁碟I/O次數越少,對於效能的提升就越大,這也是為什麼採用B樹作為索引儲存結構的原因,如圖所示。

而MySQL的InnoDB儲存引擎,它用了一種增強的B樹結構,也就是B+樹來作為索引和資料的儲存結構。

相比較於B樹結構來說,B+樹做了兩個方面的優化,如圖所示。

1、B+樹的所有資料都儲存在葉子節點,非葉子節點只儲存索引。

2、葉子節點中的資料使用雙向連結串列的方式進行關聯。

2、原因分析

我認為,MySQL索引結構採用B+樹,有以下4個原因:

1、從磁碟I/O效率方面來看:B+樹的非葉子節點不儲存資料,所以樹的每一層就能夠儲存更多的索引數量,也就是說,B+樹在層高相同的情況下,比B樹的儲存資料量更多,間接會減少磁碟I/O的次數。

2、從範圍查詢效率方面來看:在MySQL中,範圍查詢是一個比較常用的操作,而B+樹的所有儲存在葉子節點的資料使用了雙向連結串列來關聯,所以B+樹在查詢的時候只需查兩個節點進行遍歷就行,而B樹需要獲取所有節點,因此,B+樹在範圍查詢上效率更高。

3、從全表掃描方面來看:因為,B+樹的葉子節點儲存所有資料,所以B+樹的全域性掃描能力更強一些,因為它只需要掃描葉子節點。而B樹需要遍歷整個樹。

4、從自增ID方面來看:基於B+樹的這樣一種資料結構,如果採用自增的整型資料作為主鍵,還能更好的避免增加資料的時候,帶來葉子節點分裂導致的大量運算的問題。

3、總結

總體來說,我認為技術方案的選型,更多的要根據具體的業務場景來決定,並不一定是說B+樹就是最好的選擇,就像MongoDB裡面採用B樹結構,本質上來說,其實是關係型資料庫和非關係型資料庫的差異。

以上就是我對為什麼MySQL索引結構採用B+樹 的理解。

關注我,面試不再難!

本文為“Tom彈架構”原創,轉載請註明出處。技術在於分享,我分享我快樂!\ 如果本文對您有幫助,歡迎關注和點贊;如果您有任何建議也可留言評論或私信,您的支援是我堅持創作的動力。 關注微信公眾號『 Tom彈架構 』回覆“666”可獲取200頁的PDF面試文件!

我是被程式設計耽誤的文藝Tom