在MySQL中，無論是Innodb或MyIsam，都使用了B 樹作索引結構(這裡不考慮hash等其他索引)。本文將從最普通的二元查找樹開始，逐步說明各種樹解決的問題以及面臨的新問題，從而說明MySQL為什麼選擇B 樹作為索引結構。
一、二元尋找樹(BST)：不平衡
#二元查找樹(BST，Binary Search Tree)，也稱為二元排序樹，在二元樹的基礎上需要滿足：任意節點的左子樹上所有節點值不大於根節點的值，任意節點的右子樹上所有節點值不小於根節點的值。如下是一顆BST(圖片來源)。
當需要快速尋找時，將資料儲存在BST是常見的選擇，因為此時查詢時間取決於樹高，平均時間複雜度是O( lgn)。然而，BST可能長歪而變得不平衡，如下圖所示(圖片來源)，此時BST退化為鍊錶，時間複雜度退化為O(n)。
為了解決這個問題，引入了平衡二元樹。
二、平衡二元樹(AVL)：旋轉耗時
AVL樹是嚴格的平衡二元樹，所有節點的左右子樹高度差不能超過1；AVL樹查找、插入和刪除在平均和最壞情況下都是O(lgn)。
AVL實現平衡的關鍵在於旋轉操作：插入和刪除可能破壞二元樹的平衡，此時需要透過一次或多次樹旋轉來重新平衡這個樹。當插入資料時，最多只需要1次旋轉(單旋轉或雙旋轉)；但是當刪除資料時，會導致樹失衡，AVL需要維護從被刪除節點到根節點這條路徑上所有節點的平衡，旋轉的量級為O(lgn)。
由於旋轉的耗時，AVL樹在刪除資料時效率很低；在刪除操作較多時，維護平衡所需的代價可能高於其帶來的好處，因此AVL實際使用並不廣泛。
三、紅黑樹：樹太高
#與AVL樹相比，紅黑樹並不追求嚴格的平衡，而是大致的平衡：只是確保從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。從實作來看，紅黑樹最大的特點是每個節點都屬於兩種顏色(紅色或黑色)之一，且節點顏色的劃分需要滿足特定的規則(具體規則略)。紅黑樹範例如下（圖片來源）：
與AVL樹相比，紅黑樹的查詢效率會下降，這是因為樹的平衡性變差，高度更高。但紅黑樹的刪除效率大大提高了，因為紅黑樹同時引入了顏色，當插入或刪除資料時，只需要進行O(1)次數的旋轉以及變色就能保證基本的平衡，不需要像AVL樹進行O(lgn)次數的旋轉。總的來說，紅黑樹的統計表現高於AVL。
因此，在實際應用中，AVL樹的使用相對較少，而紅黑樹的使用非常廣泛。例如，Java中的TreeMap使用紅黑樹儲存排序鍵值對；Java8中的HashMap使用鍊錶紅黑樹解決雜湊衝突問題(當衝突節點較少時，使用鍊錶，當衝突節點較多時，使用紅黑樹)。
對於記憶體中資料的情況（如上述的TreeMap和HashMap），紅黑樹的表現是非常優異的。但是對於資料在磁碟等輔助儲存裝置中的情況（如MySQL等資料庫），紅黑樹並不擅長，因為紅黑樹長得還是太高了。當資料在磁碟中時，磁碟IO會成為最大的效能瓶頸，設計的目標應該是盡量減少IO次數；而樹的高度越高，增刪改查所需的IO次數也越多，會嚴重影響效能。
四、B樹：為磁碟而生
#B樹也稱為B- 樹(其中-不是減號)，是為磁碟等子存裝置設計的多路平衡查找樹，與二元樹相比， B樹的每個非葉節點可以有多個子樹。 因此，當總節點數量相同時，B樹的高度遠小於AVL樹和紅黑樹(B樹是一顆「矮胖子」)，磁碟IO次數大大減少。
定義B樹最重要的概念是階數(Order)，對於一顆m階B樹，需要滿足以下條件：
- 每個節點最多包含 m 個子節點。
- 如果根節點包含子節點，則至少包含 2 個子節點；除根節點外，每個非葉節點至少包含 m/2 個子節點。
- 擁有 k 個子節點的非葉節點將包含 k - 1 筆記錄。
- 所有葉節點都在同一層。
可以看出，B樹的定義，主要是對非葉結點的子節點數量和記錄數量的限制。
下圖是一個3階B樹的例子（圖片來源）：
B樹的優勢除了樹高小，還有對訪問局部性原理的利用。所謂局部性原理，是指當一個資料被使用時，其附近的資料有較大機率在短時間內被使用。 B樹將鍵相近的資料儲存在同一個節點，當存取其中某個資料時，資料庫會將該整個節點讀到快取中；當它臨近的資料緊接著被存取時，可以直接在快取中讀取，無需進行磁碟IO；換句話說，B樹的快取命中率更高。
B樹在資料庫中有一些應用，如mongodb的索引使用了B樹結構。但是在很多資料庫應用中，使用了是B樹的變種B 樹。
五、B 樹
B 樹也是多路平衡尋找樹，其與B樹的差異主要在於：
- B樹中每個節點（包括葉節點和非葉節點）都儲存真實的數據，B 樹中只有葉子節點儲存真實的數據，非葉節點只儲存鍵。在MySQL中，這裡所說的真實數據，可能是行的全部資料（如Innodb的叢集索引），也可能只是行的主鍵（如Innodb的輔助索引），或是行所在的位址（如MyIsam的非聚集索引）。
- B樹中一筆記錄只會出現一次，不會重複出現，而B 樹的鍵則可能重複重現－一定會在葉節點出現，也可能在非葉節點重複出現。
- B 樹的葉節點之間透過雙向鍊錶連結。
- B樹中的非葉節點，記錄數比子節點數少1；而B 樹中記錄數與子節點個數相同。
由此，B 樹與B樹相比，有以下優點：
-
更少的IO次數：B 樹的非葉節點只包含鍵，而不包含真實數據，因此每個節點儲存的記錄數量比B數多得多（即階m更大），因此B 樹的高度更低，訪問時所需要的IO次數更少。此外，由於每個節點儲存的記錄數更多，因此對存取局部性原理的利用更好，快取命中率更高。
-
更適合範圍查詢：在B樹中進行範圍查詢時，首先找到要尋找的下限，然後對B樹進行中序遍歷，直到找到查找的上限；而B 樹的範圍查詢，只需要對鍊錶進行遍歷即可。
-
更穩定的查詢效率：B樹的查詢時間複雜度在1到樹高之間(分別對應記錄在根節點和葉節點)，而B 樹的查詢複雜度則穩定為樹高，因為所有資料都在葉節點。
B 樹也存在劣勢：由於鍵會重複出現，因此會佔用更多的空間。但與帶來的效能優勢相比，空間劣勢往往可以接受，因此B 樹的在資料庫中的使用比B樹更廣泛。
六、感受B 樹的威力
#前面說到，B樹/B 樹與紅黑樹等二元樹相比，最大的優勢在於樹高更小。實際上，對於Innodb的B 索引來說，樹的高度一般在2-4層。下面來進行一些具體的估算。
樹的高度是由階數決定的，階數越大樹越矮；而階數的大小又取決於每個節點可以儲存多少筆記錄。 Innodb中每個節點使用一個頁(page)，頁的大小為16KB，其中元資料只佔大約128位元組左右(包括檔案管理頭資訊、頁頭資訊等等)，大多數空間都用來儲存資料。
對於一顆3層B 樹，第一層(根節點)有1個頁面，可以儲存1000筆記錄；第二層有1000個頁面，可以儲存1000*1000筆記錄；第三層(葉節點)有1000*1000個頁面，每個頁面可以儲存100筆記錄，因此可以儲存1000*1000*100筆記錄，即1億筆。而二元樹，儲存1億筆記錄則需要26層左右。
七、總結
最後，總結各種樹解決的問題以及面臨的新問題：
#1 )、二元查找樹(BST)：解決了排序的基本問題，但是由於無法保證平衡，可能退化為鍊錶；
2)、平衡二叉樹(AVL)：透過旋轉解決了平衡的問題，但是旋轉操作效率太低；
3)、紅黑樹：透過捨棄嚴格的平衡和引入紅黑節點，解決了AVL旋轉效率過低的問題，但是在磁碟等場景下，樹仍然太高，IO次數太多；
4)、B樹：透過將二元樹改為多路平衡查找樹，解決了樹過高的問題；
5)、B樹：在B樹的基礎上，將非葉節點改造為不儲存資料的純索引節點，進一步降低了樹的高度；此外將葉節點使用指標連接成鍊錶，範圍查詢更有效率。
推薦學習：MySQL教學
以上是MySQL為什麼選擇B+樹作為索引結構？ （詳解）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
