B+樹

B+樹在節點訪問時間遠遠超過節點內部訪問時間的時候，比可作為替代的實現有著實在的優勢。這通常在多數節點在次級存儲比如硬碟中的時候出現。通過最大化在每個內部節點內的子節點的數目減少樹的高度，平衡操作不經常發生，而且效率增加了。這種價值得以確立通常需要每個節點在次級存儲中佔據完整的磁碟塊或近似的大小。

B+背後的想法是內部節點可以有在預定範圍內的可變數目的子節點。因此，B+樹不需要象其他自平衡二叉查找樹那樣經常的重新平衡。對於特定的實現在子節點數目上的低和高邊界是固定的。例如，在2-3B樹（常簡稱為2-3樹）中，每個內部節點只可能有2或3個子節點。如果節點有無效數目的子節點則被當作處於違規狀態。

B+樹的創造者Rudolf Bayer沒有解釋B代表什麼。最常見的觀點是B代表平衡(balanced)，因為所有的葉子節點在樹中都在相同的級別上。B也可能代表Bayer，或者是波音（Boeing），因為他曾經工作于波音科學研究實驗室。

在B+樹中的節點通常被表示為一組有序的元素和子指針。如果此B+樹的序數（order）是m，則除了根之外的每個節點都包含最少個元素最多個元素，對於任意的節點有最多m個子指針。對於所有內部節點，子指針的數目總是比元素的數目多一個。因為所有葉子都在相同的高度上，節點通常不包含確定它們是葉子還是內部節點的方式。

每個內部節點的元素充當分開它的子樹的分離值。例如，如果內部節點有三個子節點（或子樹）則它必須有兩個分離值或元素a和a。在最左子樹中所有的值都小於等於a，在中間子樹中所有的值都在a和a之間((a，a]），而在最右子樹中所有的值都大於a。

查找以典型的方式進行，類似於二叉查找樹。起始於根節點，自頂向下遍歷樹，選擇其分離值在要查找值的任意一邊的子指針。在節點內部典型的使用是二分查找來確定這個位置。

節點要處於違規狀態，它必須包含在可接受範圍之外數目的元素。

1.首先，查找要插入其中的節點的位置。接著把值插入這個節點中。

2.如果沒有節點處於違規狀態則處理結束。

3.如果某個節點有過多元素，則把它分裂為兩個節點，每個都有最小數目的元素。在樹上遞歸向上繼續這個處理直到到達根節點，如果根節點被分裂，則創建一個新根節點。為了使它工作，元素的最小和最大數目典型的必須選擇為使最小數不小於最大數的一半。

1.首先，查找要刪除的值。接著從包含它的節點中刪除這個值。

2.如果沒有節點處於違規狀態則處理結束。

3.如果節點處於違規狀態則有兩種可能情況：

4.它的兄弟節點，就是同一個父節點的子節點，可以把一個或多個它的子節點轉移到當前節點，而把它返回為合法狀態。如果是這樣，在更改父節點和兩個兄弟節點的分離值之後處理結束。

5.它的兄弟節點由於處在低邊界上而沒有額外的子節點。在這種情況下把兩個兄弟節點合併到一個單一的節點中，而且我們遞歸到父節點上，因為它被刪除了一個子節點。持續這個處理直到當前節點是合法狀態或者到達根節點，在其上根節點的子節點被合併而且合併后的節點成為新的根節點。

假定L是節點允許擁有子節點的最小數目，而U是最大數目。則每個節點總是有在L和U之間（包含它們在內）個子節點，除了一個例外：根節點有從2到U（包含它們在內）個子節點。換句話說，根節點豁免於低邊界限制，而擁有它自己的低邊界2。這允許樹持有小數目的元素。根有一個子節點沒有意義，因為附著在這個子節點上的子樹可以簡單的附著在根節點上。允許根節點沒有子節點也是不需要的，因為沒有元素的樹典型的表示為沒有根節點。

Robert Tarjan證明了均攤的分裂/合併數目是2。

B+樹是B樹的一種變形形式，B+樹上的葉子結點存儲關鍵字以及相應記錄的地址，葉子結點以上各層作為索引使用。一棵m階的B+樹定義如下：

(1)每個結點至多有m個子女；

(2)除根結點外，每個結點至少有個子女，根結點至少有兩個子女；

(3)有k個子女的結點必有k個關鍵字。

B+樹的查找與B樹不同，當索引部分某個結點的關鍵字與所查的關鍵字相等時，並不停止查找，應繼續沿著這個關鍵字左邊的指針向下，一直查到該關鍵字所在的葉子結點為止。

B+樹是B樹的一種變形，比B樹具有更廣泛的應用，m階B+樹有如下特徵：

(1)每個結點的關鍵字個數與孩子個數相等，所有非最下層的內層結點的關鍵字是對應子樹上的最大關鍵字，最下層內部結點包含了全部關鍵字。

(2)除根結點以外，每個內部結點有到m個孩子。

(3)所有葉結點在樹結構的同一層，並且不含任何信息(可看成是外部結點或查找失敗的結點)，因此，樹結構總是樹高平衡的。

B+樹是應文件系統所需而產生的一種B-樹的變形樹。一棵m階的B+樹和m階的B樹的差異在於：

(1)有n棵子樹的結點中含有n個關鍵碼；

(2)所有的葉子結點中包含了全部關鍵碼的信息，及指向含有這些關鍵碼記錄的指針，且葉子結點本身依關鍵碼的大小自小而大的順序鏈接；

(3)所有的非終端結點可以看成是索引部分，結點中僅含有其子樹根結點中最大(或最小)關鍵碼。