一、前言
在MySQL中，無論是Innodb還是MyIsam，都使用了B+樹作索引結構(這裡不考慮hash等其他索引)。本文将從最普通的二叉查找樹開始，逐漸說明各種樹解決的問題以及面臨的新問題，進而說明MySQL為什麼選擇B+樹作為索引結構。
二、二叉查找樹(BST)：不平衡
二叉查找樹(BST，Binary Search Tree)，也叫二叉排序樹，在二叉樹的基礎上需要滿足：任意節點的左子樹上所有節點值不大于根節點的值，任意節點的右子樹上所有節點值不小于根節點的值。如下是一顆BST。
當需要快速查找時，将資料存儲在BST是一種常見的選擇，因為此時查詢時間取決于樹高，平均時間複雜度是O(logn)。然而，BST可能長歪而變得不平衡，如下圖所示(圖檔來源)，此時BST退化為連結清單，時間複雜度退化為O(n)。
為了解決這個問題，引入了平衡二叉樹。
三、平衡二叉樹(AVL)：旋轉耗時
AVL樹是嚴格的平衡二叉樹，所有節點的左右子樹高度差不能超過1；AVL樹查找、插入和删除在平均和最壞情況下都是O(logn)。
從圖中可以看到，我們為 user 表（使用者資訊表）建立了一個二叉查找樹的索引。圖中的圓為二叉查找樹的節點，節點中存儲了鍵（key）和資料（data）。鍵對應 user 表中的 id，資料對應 user 表中的行資料。如果我們需要查找 id=12 的使用者資訊，利用我們建立的二叉查找樹索引，查找流程如下：
- 将根節點作為目前節點，把 12 與目前節點的鍵值 10 比較，12 大于 10，接下來我們把目前節點>的右子節點作為目前節點。
- 繼續把 12 和目前節點的鍵值 13 比較，發現 12 小于 13，把目前節點的左子節點作為目前節點。
- 把 12 和目前節點的鍵值 12 對比，12 等于 12，滿足條件，我們從目前節點中取出 data，即 id=12，name=xm。
利用二叉查找樹我們隻需要 3 次即可找到比對的資料。如果在表中一條條的查找的話，我們需要 6 次才能找到。該二叉查找樹也是一個平衡二叉樹。
AVL實作平衡的關鍵在于旋轉操作：插入和删除可能破壞二叉樹的平衡，此時需要通過一次或多次樹旋轉來重新平衡這個樹。當插入資料時，最多隻需要1次旋轉(單旋轉或雙旋轉)；但是當删除資料時，會導緻樹失衡，AVL需要維護從被删除節點到根節點這條路徑上所有節點的平衡，旋轉的量級為O(logn)。
由于旋轉的耗時，AVL樹在删除資料時效率很低；在删除操作較多時，維護平衡所需的代價可能高于其帶來的好處，是以AVL實際使用并不廣泛。
四、紅黑樹：樹太高
與AVL樹相比，紅黑樹并不追求嚴格的平衡，而是大緻的平衡：隻是確定從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。從實作來看，紅黑樹最大的特點是每個節點都屬于兩種顔色(紅色或黑色)之一，且節點顔色的劃分需要滿足特定的規則(具體規則略)。紅黑樹示例如下：
與AVL樹相比，紅黑樹的查詢效率會有所下降，這是因為樹的平衡性變差，高度更高。但紅黑樹的删除效率大大提高了，因為紅黑樹同時引入了顔色，當插入或删除資料時，隻需要進行O(1)次數的旋轉以及變色就能保證基本的平衡，不需要像AVL樹進行O(lgn)次數的旋轉。總的來說，紅黑樹的統計性能高于AVL。
是以，在實際應用中，AVL樹的使用相對較少，而紅黑樹的使用非常廣泛。例如，Java中的TreeMap使用紅黑樹存儲排序鍵值對；Java8中的HashMap使用連結清單+紅黑樹解決哈希沖突問題(當沖突節點較少時，使用連結清單，當沖突節點較多時，使用紅黑樹)。
對于資料在記憶體中的情況（如上述的TreeMap和HashMap），紅黑樹的表現是非常優異的。但是對于資料在磁盤等輔助儲存設備中的情況（如MySQL等資料庫），紅黑樹并不擅長，因為紅黑樹長得還是太高了。當資料在磁盤中時，磁盤IO會成為最大的性能瓶頸，設計的目标應該是盡量減少IO次數；而樹的高度越高，增删改查所需要的IO次數也越多，會嚴重影響性能。
五、選用哪種資料結構讀取磁盤
因為記憶體的易失性。一般情況下，我們都會選擇将 user 表中的資料和索引存儲在磁盤這種外圍裝置中。但是和記憶體相比，從磁盤中讀取資料的速度會慢上百倍千倍甚至萬倍，是以，我們應當盡量減少從磁盤中讀取資料的次數。
另外，從磁盤中讀取資料時，都是按照磁盤塊來讀取的，并不是一條一條的讀。如果我們能把盡量多的資料放進磁盤塊中，那一次磁盤讀取操作就會讀取更多資料，那我們查找資料的時間也會大幅度降低。
如果我們用樹這種資料結構作為索引的資料結構，那我們每查找一次資料就需要從磁盤中讀取一個節點，也就是我們說的一個磁盤塊。我們都知道平衡二叉樹可是每個節點隻存儲一個鍵值和資料的。那說明什麼？說明每個磁盤塊僅僅存儲一個鍵值和資料！那如果我們要存儲海量的資料呢？
可以想象到二叉樹的節點将會非常多，高度也會極其高，我們查找資料時也會進行很多次磁盤 IO，我們查找資料的效率将會極低！為了解決平衡二叉樹的這個弊端，我們應該尋找一種單個節點可以存儲多個鍵值和資料的平衡樹，也就是我們接下來要說的 B 樹。
六、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+ 樹一個節點可以存儲 1000 個鍵值，那麼 3 層 B+ 樹可以存儲 1000×1000×1000=10 億個資料。一般根節點是常駐記憶體的，是以一般我們查找 10 億資料，隻需要 2 次磁盤 IO。
由此，B+樹與B樹相比，有以下優勢：
- 更少的IO次數：B+樹的非葉節點隻包含鍵，而不包含真實資料，是以每個非葉子節點會存儲更多的鍵值，相應的樹的階數（節點的子節點數）就會更大，樹就會更矮更胖，是以B+樹的高度更低，通路時所需要的IO次數更少。此外，由于每個節點存儲的鍵值更多，是以對通路局部性原理的利用更好，緩存命中率更高。
- 更适于範圍查詢：在B樹中進行範圍查詢時，首先找到要查找的下限，然後對B樹進行中序周遊，直到找到查找的上限；而B+樹的範圍查詢，隻需要對連結清單進行周遊即可。
- 更穩定的查詢效率：B樹的查詢時間複雜度在1到樹高之間(分别對應記錄在根節點和葉節點)，而B+樹的查詢複雜度則穩定為樹高，因為所有資料都在葉節點。
B+樹也存在劣勢：由于鍵會重複出現，是以會占用更多的空間。但是與帶來的性能優勢相比，空間劣勢往往可以接受，是以B+樹的在資料庫中的使用比B樹更加廣泛。
MyISAM 中的 B+ 樹索引實作與 InnoDB 中的略有不同，在 MyISAM 中B+ 樹索引的葉子節點并不存儲資料，而是存儲資料的檔案位址。
八、總結
最後，總結一下各種樹解決的問題以及面臨的新問題：
- 二叉查找樹(BST)：解決了排序的基本問題，但是由于無法保證平衡，可能退化為連結清單；
- 平衡二叉樹(AVL)：通過自旋解決了平衡的問題，但是旋轉操作效率太低；
- 紅黑樹：通過舍棄嚴格的平衡和引入紅黑節點，解決了AVL旋轉效率過低的問題，但是在磁盤等場景下，樹仍然太高，IO次數太多；
- B樹：通過将二叉樹改為多路平衡查找樹，單個非頁節點可以存儲多個鍵值和資料，解決了樹過高的問題；
- B+樹：在B樹的基礎上，将非葉節點改造為不存儲資料的純索引節點，進一步降低了樹的高度；此外将葉節點使用指針連接配接成連結清單，範圍查詢更加高效。