MySQL為什么選擇B+樹作為索引結(jié)構(gòu)？

前言

在MySQL中，無論是Innodb還是MyIsam，都使用了B+樹作索引結(jié)構(gòu)(這里不考慮hash等其他索引)。本文將從最普通的二叉查找樹開始，逐步說明各種樹解決的問題以及面臨的新問題，從而說明MySQL為什么選擇B+樹作為索引結(jié)構(gòu)。

一、二叉查找樹(BST)：不平衡

二叉查找樹(BST，Binary Search Tree)，也叫二叉排序樹，在二叉樹的基礎(chǔ)上需要滿足：任意節(jié)點的左子樹上所有節(jié)點值不大于根節(jié)點的值，任意節(jié)點的右子樹上所有節(jié)點值不小于根節(jié)點的值。如下是一顆BST(圖片來源)。

當需要快速查找時，將數(shù)據(jù)存儲在BST是一種常見的選擇，因為此時查詢時間取決于樹高，平均時間復雜度是O(lgn)。然而BST 可能長歪而變得不平衡，如下圖所示(圖片來源)，此時BST退化為鏈表，時間復雜度退化為O(n)。

為了解決這個問題，引入了平衡二叉樹。

二、平衡二叉樹(AVL)：旋轉(zhuǎn)耗時

AVL樹是嚴格的平衡二叉樹，所有節(jié)點的左右子樹高度差不能超過1；AVL樹查找、插入和刪除在平均和最壞情況下都是O(lgn)。

AVL實現(xiàn)平衡的關(guān)鍵在于旋轉(zhuǎn)操作：插入和刪除可能破壞二叉樹的平衡，此時需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。當插入數(shù)據(jù)時，最多只需要1次旋轉(zhuǎn)(單旋轉(zhuǎn)或雙旋轉(zhuǎn))；但是當刪除數(shù)據(jù)時，會導致樹失衡，AVL需要維護從被刪除節(jié)點到根節(jié)點這條路徑上所有節(jié)點的平衡，旋轉(zhuǎn)的量級為O(lgn)。

由于旋轉(zhuǎn)的耗時，AVL樹在刪除數(shù)據(jù)時效率很低 ；在刪除操作較多時，維護平衡所需的代價可能高于其帶來的好處，因此AVL實際使用并不廣泛。

三、紅黑樹：樹太高

與AVL樹相比，紅黑樹并不追求嚴格的平衡，而是大致的平衡：只是確保從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。從實現(xiàn)來看，紅黑樹最大的特點是每個節(jié)點都屬于兩種顏色(紅色或黑色)之一，且節(jié)點顏色的劃分需要滿足特定的規(guī)則(具體規(guī)則略)。紅黑樹示例如下（圖片來源）：

與AVL樹相比，紅黑樹的查詢效率會有所下降，這是因為樹的平衡性變差，高度更高。但紅黑樹的刪除效率大大提高了，因為紅黑樹同時引入了顏色，當插入或刪除數(shù)據(jù)時，只需要進行O(1)次數(shù)的旋轉(zhuǎn)以及變色就能保證基本的平衡，不需要像AVL樹進行O(lgn)次數(shù)的旋轉(zhuǎn)。總的來說，紅黑樹的統(tǒng)計性能高于AVL。

因此，在實際應(yīng)用中，AVL樹的使用相對較少，而紅黑樹的使用非常廣泛。例如，Java中的TreeMap使用紅黑樹存儲排序鍵值對；Java8中的HashMap使用鏈表+紅黑樹解決哈希沖突問題(當沖突節(jié)點較少時，使用鏈表，當沖突節(jié)點較多時，使用紅黑樹)。

對于數(shù)據(jù)在內(nèi)存中的情況（如上述的TreeMap和HashMap），紅黑樹的表現(xiàn)是非常優(yōu)異的。但是對于數(shù)據(jù)在磁盤等輔助存儲設(shè)備中的情況（如** **MySQL****等數(shù)據(jù)庫），紅黑樹并不擅長，因為紅黑樹長得還是太高了 。當數(shù)據(jù)在磁盤中時，磁盤IO會成為最大的性能瓶頸，設(shè)計的目標應(yīng)該是盡量減少IO次數(shù)；而樹的高度越高，增刪改查所需要的IO次數(shù)也越多，會嚴重影響性能。

四、B樹：為磁盤而生

B樹也稱B-樹(其中-不是減號)，是為磁盤等輔存設(shè)備設(shè)計的多路平衡查找樹，與二叉樹相比，B樹的每個非葉節(jié)點可以有多個子樹。 因此，當總節(jié)點數(shù)量相同時，B樹的高度遠遠小于AVL樹和紅黑樹(B樹是一顆“矮胖子”)，磁盤IO次數(shù)大大減少。

定義B樹最重要的概念是階數(shù)(Order)，對于一顆m階B樹，需要滿足以下條件：

每個節(jié)點最多包含 m 個子節(jié)點。

如果根節(jié)點包含子節(jié)點，則至少包含 2 個子節(jié)點；除根節(jié)點外，每個非葉節(jié)點至少包含 m/2 個子節(jié)點。

擁有 k 個子節(jié)點的非葉節(jié)點將包含 k - 1 條記錄。

所有葉節(jié)點都在同一層中。

可以看出，B樹的定義，主要是對非葉結(jié)點的子節(jié)點數(shù)量和記錄數(shù)量的限制。

下圖是一個3階B樹的例子（圖片來源）：

B樹的優(yōu)勢除了樹高小，還有對訪問局部性原理的利用。所謂局部性原理，是指當一個數(shù)據(jù)被使用時，其附近的數(shù)據(jù)有較大概率在短時間內(nèi)被使用。B樹將鍵相近的數(shù)據(jù)存儲在同一個節(jié)點，當訪問其中某個數(shù)據(jù)時，數(shù)據(jù)庫會將該整個節(jié)點讀到緩存中；當它臨近的數(shù)據(jù)緊接著被訪問時，可以直接在緩存中讀取，無需進行磁盤IO；換句話說，B樹的緩存命中率更高。

B樹在數(shù)據(jù)庫中有一些應(yīng)用，如mongodb的索引使用了B樹結(jié)構(gòu)。但是在很多數(shù)據(jù)庫應(yīng)用中，使用了是B樹的變種B+樹。

五、B+樹

B+樹也是多路平衡查找樹，其與B樹的區(qū)別主要在于：

B樹中每個節(jié)點（包括葉節(jié)點和非葉節(jié)點）都存儲真實的數(shù)據(jù)，B+樹中只有葉子節(jié)點存儲真實的數(shù)據(jù)，非葉節(jié)點只存儲鍵。在MySQL中，這里所說的真實數(shù)據(jù)，可能是行的全部數(shù)據(jù)（如Innodb的聚簇索引），也可能只是行的主鍵（如Innodb的輔助索引），或者是行所在的地址（如MyIsam的非聚簇索引）。

B樹中一條記錄只會出現(xiàn)一次，不會重復出現(xiàn)，而B+樹的鍵則可能重復重現(xiàn)——一定會在葉節(jié)點出現(xiàn)，也可能在非葉節(jié)點重復出現(xiàn)。

B+樹的葉節(jié)點之間通過雙向鏈表鏈接。

B樹中的非葉節(jié)點，記錄數(shù)比子節(jié)點個數(shù)少1；而B+樹中記錄數(shù)與子節(jié)點個數(shù)相同。

由此，B+樹與B樹相比，有以下優(yōu)勢：

更少的IO次數(shù)：B+樹的非葉節(jié)點只包含鍵，而不包含真實數(shù)據(jù)，因此每個節(jié)點存儲的記錄個數(shù)比B數(shù)多很多（即階m更大），因此B+樹的高度更低，訪問時所需要的IO次數(shù)更少。此外，由于每個節(jié)點存儲的記錄數(shù)更多，所以對訪問局部性原理的利用更好，緩存命中率更高。

更適于范圍查詢：在B樹中進行范圍查詢時，首先找到要查找的下限，然后對B樹進行中序遍歷，直到找到查找的上限；而B+樹的范圍查詢，只需要對鏈表進行遍歷即可。

更穩(wěn)定的查詢效率：B樹的查詢時間復雜度在1到樹高之間(分別對應(yīng)記錄在根節(jié)點和葉節(jié)點)，而B+樹的查詢復雜度則穩(wěn)定為樹高，因為所有數(shù)據(jù)都在葉節(jié)點。

B+樹也存在劣勢：由于鍵會重復出現(xiàn)，因此會占用更多的空間。但是與帶來的性能優(yōu)勢相比，空間劣勢往往可以接受，因此B+樹的在數(shù)據(jù)庫中的使用比B樹更加廣泛。

六、感受B+樹的威力

前面說到，B樹/B+樹與紅黑樹等二叉樹相比，最大的優(yōu)勢在于樹高更小。實際上，對于Innodb的B+索引來說，樹的高度一般在2-4層。下面來進行一些具體的估算。

樹的高度是由階數(shù)決定的，階數(shù)越大樹越矮；而階數(shù)的大小又取決于每個節(jié)點可以存儲多少條記錄。Innodb中每個節(jié)點使用一個頁(page)，頁的大小為16KB，其中元數(shù)據(jù)只占大約128字節(jié)左右(包括文件管理頭信息、頁面頭信息等等)，大多數(shù)空間都用來存儲數(shù)據(jù)。

對于非葉節(jié)點，記錄只包含索引的鍵和指向下一層節(jié)點的指針。假設(shè)每個非葉節(jié)點頁面存儲1000條記錄，則每條記錄大約占用16字節(jié)；當索引是整型或較短的字符串時，這個假設(shè)是合理的。延伸一下，我們經(jīng)常聽到建議說索引列長度不應(yīng)過大，原因就在這里：索引列太長，每個節(jié)點包含的記錄數(shù)太少，會導致樹太高，索引的效果會大打折扣，而且索引還會浪費更多的空間。

對于葉節(jié)點，記錄包含了索引的鍵和值(值可能是行的主鍵、一行完整數(shù)據(jù)等，具體見前文)，數(shù)據(jù)量更大。這里假設(shè)每個葉節(jié)點頁面存儲100條記錄(實際上，當索引為聚簇索引時，這個數(shù)字可能不足100；當索引為輔助索引時，這個數(shù)字可能遠大于100；可以根據(jù)實際情況進行估算)。

對于一顆3層B+樹，第一層(根節(jié)點)有1個頁面，可以存儲1000條記錄；第二層有1000個頁面，可以存儲10001000條記錄；第三層(葉節(jié)點)有10001000個頁面，每個頁面可以存儲100條記錄，因此可以存儲10001000100條記錄，即1億條。而對于二叉樹，存儲1億條記錄則需要26層左右。

七、總結(jié)

最后，總結(jié)一下各種樹解決的問題以及面臨的新問題：

二叉查找樹(BST)：解決了排序的基本問題，但是由于無法保證平衡，可能退化為鏈表；

平衡二叉樹(AVL)：通過旋轉(zhuǎn)解決了平衡的問題，但是旋轉(zhuǎn)操作效率太低；

紅黑樹：通過舍棄嚴格的平衡和引入紅黑節(jié)點，解決了AVL旋轉(zhuǎn)效率過低的問題，但是在磁盤等場景下，樹仍然太高，IO次數(shù)太多；

B樹：通過將二叉樹改為多路平衡查找樹，解決了樹過高的問題；

B+樹：在B樹的基礎(chǔ)上，將非葉節(jié)點改造為不存儲數(shù)據(jù)的純索引節(jié)點，進一步降低了樹的高度；此外將葉節(jié)點使用指針連接成鏈表，范圍查詢更加高效。

審核編輯：劉清