B樹

  提示：此條目的主題不是二叉樹（binary tree）。

B樹
類型	樹
發明時間	1972
發明者	Rudolf Bayer, Edward M. McCreight
用大O符號表示的時間複雜度
演算法 平均 最差 空間 O(n) O(n) 搜尋 O(log n) O(log n) 插入 O(log n) O(log n) 刪除 O(log n) O(log n)

B樹（英語：B-tree），是一種在電腦科學自平衡的樹，能夠保持資料有序。這種資料結構能夠讓尋找數據、順序訪問、插入數據及刪除的動作，都在對數時間內完成。B樹，概括來說是一個一般化的二元搜尋樹（binary search tree）一個節點可以擁有2個以上的子節點。與自平衡二元搜尋樹不同，B樹適用於讀寫相對大的資料塊的儲存系統，例如磁碟。B樹減少定位記錄時所經歷的中間過程，從而加快存取速度。B樹這種資料結構可以用來描述外部儲存。這種資料結構常被應用在資料庫和檔案系統的實現上。

概述

B樹 (Bayer & McCreight 1972) (order為5) (Knuth 1998).

在B樹中，內部（非葉子）節點可以擁有可變數量的子節點（數量範圍預先定義好）。當資料被插入或從一個節點中移除，它的子節點數量發生變化。為了維持在預先設定的數量範圍內，內部節點可能會被合併或者分離。因為子節點數量有一定的允許範圍，所以B樹不需要像其他自平衡尋找樹那樣頻繁地重新保持平衡，但是由於節點沒有被完全填充，可能浪費了一些空間。子節點數量的上界和下界依特定的實現而設定。例如，在一個2-3 B樹（通常簡稱2-3樹），每一個內部節點只能有2或3個子節點。

B樹中每一個內部節點會包含一定數量的鍵，鍵將節點的子樹分開。例如，如果一個內部節點有3個子節點（子樹），那麼它就必須有兩個鍵： a₁ 和 a₂ 。左邊子樹的所有值都必須小於 a₁ ，中間子樹的所有值都必須在 a₁ 和a₂ 之間，右邊子樹的所有值都必須大於 a₂ 。

通常，鍵的數量被選定在 $d$ 和 $2d$ 之間。其中 $d$ 是鍵的最小數量，$d+1$ 是樹最小的 度 或 分支因子 。在實際中，鍵值占用了節點中大部分的空間。因數2將保證節點可以被拆分或組合。如果一個內部節點有 $2d$ 個鍵，那麼要添加一個鍵值給此節點，只需要拆分這 $2d+1$ 個鍵為2個 擁有 $d$ 個鍵的節點，並把中間值節點移動到父節點。每一個拆分的節點需要擁有足夠數目的鍵。相似地，如果一個內部節點和他的鄰居兩者都有 $d$ 個鍵，那麼將通過它與鄰居的合併來刪除一個鍵。刪除此鍵將導致此節點擁有 $d-1$ 個鍵;與鄰居的合併則加上 $d$ 個鍵，再加上從鄰居節點的父節點移來的一個鍵值。結果為完全填充的 $2d$ 個鍵。

一個節點的分支（或子節點）的數量會比儲存在節點內部鍵值的數量大1。在 2-3 B樹中，內部節點將會儲存1個鍵值（帶有2個子節點）或2個鍵值（帶有3個子節點）。一個B樹有時會被描述為 $(d+1)-(2d+1)$ 或簡單地使用最高分支 $(2d+1)$ 。

一個Ｂ樹通過約束所有葉子節點在相同深度來保持平衡。深度在元素添加至樹的過程中緩慢增長，而整體深度極少地增長，並導致所有葉子節點與根節點距離加1。

在存取節點資料所耗時間遠超過處理節點資料所耗時間的情況下，Ｂ樹在可選的實現中擁有很多優勢，因為存取節點的開銷被分攤到裡層節點的多次操作上。這通常出現在當節點儲存在二級記憶體如硬碟記憶體上。通過最大化內部裡層節點的子節點的數量，樹的高度減小，存取節點的開銷被縮減。另外，重新平衡樹的動作也更少出現。子節點的最大數量取決於，每個子節點必需儲存的資訊量，和完整磁碟塊的大小或者二次記憶體中類似的容量。雖然 2-3 樹更易於解釋，實際運用中，Ｂ樹使用二級記憶體，需要大量數目的子節點來提升效率。

變體

術語B樹可以指一個特定的方案，也可以指大體上一類方案。狹義上，一個Ｂ樹在它內部節點中儲存鍵值，但不需在葉子節點上儲存這些鍵值的記錄。大體上的一類包含一些變體，如B+樹和B*樹。

在B⁺樹，這些鍵值的拷貝被儲存在內部節點；鍵值和記錄儲存在葉子節點；另外，一個葉子節點可以包含一個指標，指向另一個葉子節點以加速順序存取。

B*樹分支出更多的內部鄰居節點以保持內部節點更密集地填充。此變體要求非根節點至少2/3填充，而不是1/2。為了維持這樣的結構，當一個節點填滿之後將不會再立即分割節點，而是將它的鍵值與下一個節點共享。當兩個節點都填滿之後，分割成3個節點。

計數B樹儲存，每一樹都帶有一個指標和其指向子樹的節點數目。這就允許了以鍵值為序快速尋找第N筆記錄，或是統計2筆記錄之間的記錄數目，還有其他很多相關的操作。

名字取義

魯道夫·拜爾（Rudolf Bayer）和 艾華·M·麥克雷（Ed M. McCreight）於1972年在波音研究實驗室（Boeing Research Labs）工作時發明了B 樹，但是他們沒有解釋B 代表什麼意義（如果有的話）。道格拉斯·科默爾（Douglas Comer）解釋說: 兩位作者從來都沒解釋過B樹的原始意義。正如我們所見，「balanced」， 「broad」 或 「bushy」 可能適合。其他人建議字母「B」代表 Boeing。源自於他的贊助，不過，看起來把B樹當作「Bayer」樹更合適些

高德納（Donald Knuth） 在他1980年5月發表的題為「CS144C classroom lecture about disk storage and B-trees」的論文中推測了B樹的名字取義，提出「B」可能意味Boeing 或者Bayer 的名字。

資料庫的問題

已排序檔案的尋找時間

通常，排序和尋找演算法會被通過大O符號，刻畫為比較級別的數值。對一個有N筆記錄的已排序表進行二元搜尋，打個比方說，可以在O（log₂N）比較級完成。如果表有1,000,000筆記錄,那麼定位其中一筆記錄，將在20個比較級內完成。 log₂(1,000,000) = 19.931...

巨量資料庫一直以來被儲存在磁碟。從磁碟上讀取一筆記錄，與之後的比較鍵值操作相比，在花費的執行時間上前者處於支配地位。從磁碟讀取記錄的時間涉及到一個 尋道時間 和 旋轉延遲。尋道時間可能是從0到20或者更多毫秒，旋轉延遲平均下來約是旋轉周期的一半。對於一個7,200轉每分鐘的磁碟，旋轉周期大約是8.33毫秒。像希捷ST3500320NS這樣的磁碟,磁軌至磁軌的尋道時間為 0.8毫秒，平均讀取尋道時間為8.5毫秒。為了簡化，假設從磁碟讀取花費10毫秒。

樂觀來說，如此，在一百萬中定位一筆記錄將對談花費20次磁碟讀取乘上10毫秒每次讀取時間，總共是0.2秒。

時間花費沒有那麼糟糕的原因是，獨立的記錄被成組地記錄在磁碟塊上。一個磁碟塊可能為16 千位元組。如果每筆記錄大小為160 位元組，那麼一個塊可以儲存100 筆記錄。上面假設的磁碟讀取時間確切地說是讀取一個完整塊的時間。一旦磁頭到達位置，一個或者更多的磁碟塊可以以較小的延遲來完成讀取。對於100筆記錄每塊，最後差不多6個比較級是不需要任何磁碟讀取的——都在上次讀取操作中完成了。

為進一步加速尋找，開始的13或14個比較級（每個需要一次磁碟訪問）必須要提速。

提升尋找的索引

較大程度上的提升是通過索引來做到的。在上面的例子中，初始磁碟讀取從2個因素限制了尋找範圍。這基本上可以通過建立一個輔助索引來改善，這個索引包含每塊磁碟塊上的首筆記錄（有時稱為稀疏索引）。這個輔助索引可能只有原始資料庫的1%大小，但是它可以更快速地被檢索。在輔助索引中尋找入口可以告訴我們在主資料庫中要讀取哪一塊;尋找輔助索引之後，我們只需要讀取主資料庫中的特定的某一個磁碟分塊——通過一次磁碟讀取開銷。索引可以提供10,000入口，所以，這樣最多需要14個比較級。就像主資料庫，輔助索引中最後6個左右的比較級可能在相同的磁碟分塊上。索引可以在大約8次磁碟讀取中完成尋找，目標記錄會在9次磁碟讀取後獲得。

建立輔助索引的竅門是可以重複地給輔助索引建立輔助索引。那樣可以實現一個只擁有100 入口，能填滿一整個磁碟塊的輔助-輔助索引。

要找到想要的記錄，我們只需要讀取3次磁碟分塊，而不是14次。讀取和尋找輔助-輔助索引中第一個（而且是唯一的）塊，標記了相應的輔助索引中的分塊。讀取和尋找輔助索引的分塊，標記了主資料庫中相應的分塊。我們只需要30毫秒，而不是150毫秒就能取得記錄。

輔助的索引，使得尋找問題從約為log2N 磁碟讀取開銷的二分尋找，變成logbN 磁碟讀取開銷的尋找，其中b為分塊因素（每分塊的入口數目：b = 100 入口每分塊;logb1,000,000 = 3 次讀取）。

在實際中，如果主資料庫被頻繁尋找，輔助-輔助索引和大部分的輔助索引可能會儲存在磁碟快取中，所以它們不會產生磁碟讀取。

插入和刪除帶來的麻煩

如果資料庫不會改變，那麼編制索引就很簡單，而且索引永遠不需要改變。如果他們會改變，那麼管理資料庫及其索引就變得非常麻煩。

從資料庫中刪除記錄不會引起太大問題。索引可以保持不變，記錄只需要標記為已刪除。資料庫仍然保持有序狀態。如果會有很多刪除，之後尋找和儲存就不再那麼高效了。

在一個有序檔案中進行插入將是個災難，因為需要給插入的記錄製造空間。在檔案中第一筆記錄後插入記錄需要把所有記錄向後偏移一個位置。如此的操作在實際中實在太過昂貴。

一種做法是預留一些空間給插入操作。磁碟塊有一些空閒空間允許後來的插入，而不是高密度地填充。這些記錄可以被標記為像是已刪除的記錄。

現在，只要塊中存在空間，插入和刪除都可以很快速。如果一個插入操作在一個塊上找不到合適的空間，就在臨近的塊中尋找，且要調整輔助索引。期望是臨近存在足夠的空間，以免重新調整大量的塊。作為可選方案，可以使用一些非排序的塊。

B樹運用的理念

B樹使用了以上所有的想法。特別是：

• 保持鍵值有序，以順序遍歷
• 使用層次化的索引來最小化磁碟讀取
• 使用不完全填充的塊來加速插入和刪除
• 通過優雅的遍歷演算法來保持索引平衡

另外，B樹通過保證內部節點至少半滿來最小化空間浪費。一棵B樹可以處理任意數目的插入和刪除。

B樹的弊端

• 除非完全重建資料庫，否則無法改變鍵值的最大長度。這使得許多資料庫系統將人名截斷到70字元之內。

（其他關聯陣列的實現，例如三元搜尋樹或者開雜湊雜湊表，可以動態適應任意長度的鍵值）。

術語和定義

術語

文獻中B樹的術語並不統一 (Folk & Zoellick 1992，第362頁)。

Bayer & McCreight (1972)，Comer (1979)等人將B樹的 階 定義為非根節點擁有鍵的最小數量。Folk & Zoellick (1992) 指出這一術語是模糊不清的。一個 3 階B樹鍵的最大數量可能為 6 或 7。 Knuth (1998，第483頁) 通過將 階 定義為最大數量的子節點（比最大數量的鍵大1）來避免這一問題。

術語 葉子 的定義也不一致。 Bayer & McCreight (1972) 認為葉子層是最下面一層的鍵，但是 Knuth 認為葉子層是最下面一層鍵之下的一層 (Folk & Zoellick 1992，第363頁)。可能的實現有許多。在一些設計中，葉子可能儲存了完整的資料記錄；在另一些設計中，葉子可能只儲存了指向資料記錄的指標。

為了簡化，許多作者假定一個節點能夠容納固定數量的鍵。基礎的假設是鍵和節點的大小都是固定的。事實上，可變長度的鍵可能會被使用 (Folk & Zoellick 1992，第379頁)。

定義

根據 Knuth 的定義，一個 m 階的B樹是一個有以下屬性的樹：

1. 每一個節點最多有 m 個子節點
2. 每一個非葉子節點（除根節點）最少有 ⌈m/2⌉ 個子節點
3. 如果根節點不是葉子節點，那麼它至少有兩個子節點
4. 有 k 個子節點的非葉子節點擁有 k − 1 個鍵
5. 所有的葉子節點都在同一層

每一個內部節點的鍵將節點的子樹分開。例如，如果一個內部節點有3個子節點（子樹），那麼它就必須有兩個鍵： a₁ 和 a₂ 。左邊子樹的所有值都必須小於 a₁ ，中間子樹的所有值都必須在 a₁ 和a₂ 之間，右邊子樹的所有值都必須大於 a₂ 。

內部節點

內部節點是除葉子節點和根節點之外的所有節點。它們通常被表示為一組有序的元素和指向子節點的指標。每一個內部節點擁有最多 U 個，最少 L 個子節點。元素的數量總是比子節點指標的數量少一（元素的數量在 L-1 和 U-1 之間）。U 必須等於 2L 或者 2L-1;因此，每一個內部節點都至少是半滿的。U 和 L 之間的關係意味著兩個半滿的節點可以合併成一個合法的節點，一個全滿的節點可以被分裂成兩個合法的節點（如果父節點有空間容納移來的一個元素）。這些特性使得在B樹中刪除或插入新的值時可以調整樹來保持B樹的性質。

根節點

根節點擁有的子節點數量的上限和內部節點相同，但是沒有下限。例如，當整個樹中的元素數量小於 L-1 時，根節點是唯一的節點並且沒有任何子節點。

葉子節點

葉子節點對元素的數量有相同的限制，但是沒有子節點，也沒有指向子節點的指標。

一個深度為n+1 的B樹可以容納的元素數量大約是深度為 n 的B樹的 U 倍，但是搜尋、插入和刪除操作的開銷也會增加。和其他的平衡樹一樣，這一開銷增加的速度遠遠慢於元素數量的增加。

一些平衡樹只在葉子節點中儲存值，而且葉子節點和內部節點使用不同的結構。B樹在每一個節點中都儲存值，所有的節點有著相同的結構。然而，因為葉子節點沒有子節點，所以可以通過使用專門的結構來提高B樹的效能。

非形式的描述

秩為5的B樹.

B樹的內部非葉節點的子節點的數量要保持在一定範圍。當在這個節點上插入或刪除值，它的子節點可以合併或者分裂，以便該節點的子節點的數量繼續保持在一定範圍內。從而， B樹不需要像其他二元搜尋樹那樣需要頻繁地再平衡操作，但可能會浪費一些空間，因為節點未必是滿的。非葉節點的子節點的數量一般實現時取固定值。例如，2-3樹的內部節點可以有2或3個子節點。

通常，內部節點的鍵值的數量在$d$到$2d$之間變化，其中$d$是鍵值的最少數量，$d+1$是樹的最小出度或分支因子。係數2保證了這個節點可以分割或合併。如果內部節點有$2d$個鍵值，那麼再增加一個鍵值需要把該節點分為2個包含$d$個鍵值的節點和1個增加到父節點的分隔鍵值。如果一個內部節點和它的相鄰兄弟節點都有$d$個鍵值，那麼從該節點刪除一個鍵值需要合併它與相鄰兄弟節點及父節點中的分隔鍵值，結果為一個具有$2d$個鍵值的滿節點，及父節點刪除一個鍵值操作。

一顆B樹有時被稱為$(d+1)$—$(2d+1)$（例如2-3樹）或者用最大分支秩$(2d+1)$。

B樹在插入操作後將分裂過滿的節點，以保持平衡，即對有$2d+1$個鍵值的節點分裂為2個$d$個鍵值的兄弟節點並向父節點插入一個分隔鍵值。僅當根節點分裂時，B樹的深度會增長，以保持平衡。類似地，B-樹刪除操作會對少於$d$個鍵值的非根節點執行和相鄰兄弟節點的合併或重分布操作，以保持平衡。合併節點將導致父節點減少一個分隔操作，這導致父節點的刪除操作。僅當根節點僅有2個子節點且各自包含 $d$個和$d-1$個鍵值，做合併操作時，B樹的深度將減去1。

當訪問節點資料的時間大大超過處理該資料所花費的時間時，B-樹比替代實現具有顯著的優勢，因為訪問節點的成本可以分攤到節點內的多個操作上。當節點資料位於輔助儲存（例如磁碟機）時，通常會發生這種情況。 通過最大化每個內部節點內的鍵數量，樹的高度會降低，並且昂貴的節點訪問次數也會減少。 此外，樹的重新平衡發生的頻率也較低。 子節點的最大數量取決於必須為每個子節點儲存的資訊以及完整磁碟塊的大小或輔助儲存中的類似大小。 雖然2-3樹更容易解釋，但實際用於輔助儲存的B樹需要大量子節點來提高效能。

變種

術語「B樹」可以指特定設計，也可以指一般類別的設計。 狹義上，B樹將鍵儲存在其內部節點中，但不需要將這些鍵儲存在葉節點的記錄中。 一般類包括諸如B+樹、B^*樹和B^*+樹之類的變體。

• 在B+樹中, 鍵值的副本儲存在內部節點中；鍵值和記錄儲存在葉節點中； 此外，葉節點可能包含指向下一個相鄰葉節點的指標以加速順序訪問。
• B^*樹平衡更多相鄰的內部節點，以保持內部節點更密集。B^*樹確保非根節點至少有2/3滿，而不是1/2。由於在B樹中插入節點的操作中成本最高的部分是分裂節點，因此建立了B^*樹儘可能推遲分裂操作。為了維持這一點，不是在節點滿時立即拆分節點，而是與下一個節點共享其鍵值。這種溢位操作的成本比拆分要低，因為它只需要在現有節點之間移動鍵值，而不需要為新節點分配主記憶體。
• B^*+樹將B+樹和B^*樹的主要特徵結合在一起。
• B樹可以變成順序統計樹，可以快速尋找關鍵順序的第N條記錄，或者統計任意兩條記錄之間的記錄數，以及其他各種相關操作。

演算法

搜尋

B樹的搜尋和二元搜尋樹類似。從根節點開始，從上到下遞迴的遍歷樹。在每一層上，搜尋的範圍被減小到包含了搜尋值的子樹中。子樹值的範圍被它的父節點的鍵確定。

插入

B樹插入的例子。 節點最多有3個孩子 (Knuth 階為 3).

所有的插入都從根節點開始。要插入一個新的元素，首先搜尋這棵樹找到新元素應該被添加到的對應節點。將新元素插入到這一節點中的步驟如下：

1. 如果節點擁有的元素數量小於最大值，那麼有空間容納新的元素。將新元素插入到這一節點，且保持節點中元素有序。
2. 否則的話這一節點已經滿了，將它平均地分裂成兩個節點：
   1. 從該節點的原有元素和新的元素中選擇出中位數
   2. 小於這一中位數的元素放入左邊節點，大於這一中位數的元素放入右邊節點，中位數作為分隔值。
   3. 分隔值被插入到父節點中，這可能會造成父節點分裂，分裂父節點時可能又會使它的父節點分裂，以此類推。如果沒有父節點（這一節點是根節點），就建立一個新的根節點（增加了樹的高度）。

如果分裂一直上升到根節點，那麼一個新的根節點會被建立，它有一個分隔值和兩個子節點。這就是根節點並不像內部節點一樣有最少子節點數量限制的原因。每個節點中元素的最大數量是 U-1。當一個節點分裂時，一個元素被移動到它的父節點，但是一個新的元素增加了進來。所以最大的元素數量 U-1 必須能夠被分成兩個合法的節點。如果 U-1 是奇數，那麼 U=2L ，總共有 2L-1 個元素，一個新的節點有 L-1 個元素，另外一個有 L 個元素，都是合法的節點。如果 U-1 是偶數，那麼 U=2L-1,總共有 2L-2 個元素。 一半是 L-1，正好是節點允許的最小元素數量。

刪除

有兩種常用的刪除策略

1. 定位並刪除元素，然後調整樹使它滿足約束條件； 或者
2. 從上到下處理這棵樹，在進入一個節點之前，調整樹使得之後一旦遇到了要刪除的鍵，它可以被直接刪除而不需要再進行調整

以下的演算法使用了前一種策略。

刪除一個元素時有以下兩種特殊情況

1. 這個元素用於分隔一個內部節點的子節點
2. 刪除元素會導致它所在的節點的元素或子節點數量小於最低值

下面分別是這些情況的處理過程

刪除葉子節點中的元素

1. 搜尋要刪除的元素
2. 如果它在葉子節點，將它從中刪除
3. 如果發生了下溢位，按照後面 「刪除後重新平衡」部分的描述重新調整樹

刪除內部節點中的元素

內部節點中的每一個元素都作為分隔兩顆子樹的分隔值，因此我們需要重新劃分。值得注意的是左子樹中最大的元素仍然小於分隔值。同樣的，右子樹中最小的元素仍然大於分隔值。這兩個元素都在葉子節點中，並且任何一個都可以作為兩顆子樹的新分隔值。演算法的描述如下：

1. 選擇一個新的分隔符（左子樹中最大的元素或右子樹中最小的元素），將它從葉子節點中移除，替換掉被刪除的元素作為新的分隔值。
2. 前一步刪除了一個葉子節點中的元素。如果這個葉子節點擁有的元素數量小於最低要求，那麼從這一葉子節點開始重新進行平衡。

刪除後的重新平衡

重新平衡從葉子節點開始向根節點進行，直到樹重新平衡。如果刪除節點中的一個元素使該節點的元素數量低於最小值，那麼一些元素必須被重新分配。通常，移動一個元素數量大於最小值的兄弟節點中的元素。如果兄弟節點都沒有多餘的元素，那麼缺少元素的節點就必須要和他的兄弟節點 合併。合併可能導致父節點失去了分隔值，所以父節點可能缺少元素並需要重新平衡。合併和重新平衡可能一直進行到根節點，根節點變成惟一缺少元素的節點。重新平衡樹的演算法如下：

• 如果缺少元素節點的右兄弟存在且擁有多餘的元素，那麼向左旋轉
  1. 將父節點的分隔值複製到缺少元素節點的最後（分隔值被移下來；缺少元素的節點現在有最小數量的元素）
  2. 將父節點的分隔值替換為右兄弟的第一個元素（右兄弟失去了一個節點但仍然擁有最小數量的元素）
  3. 樹又重新平衡
• 否則，如果缺少元素節點的左兄弟存在且擁有多餘的元素，那麼向右旋轉
  1. 將父節點的分隔值複製到缺少元素節點的第一個節點（分隔值被移下來；缺少元素的節點現在有最小數量的元素）
  2. 將父節點的分隔值替換為左兄弟的最後一個元素（左兄弟失去了一個節點但仍然擁有最小數量的元素）
  3. 樹又重新平衡
• 否則，如果它的兩個直接兄弟節點都只有最小數量的元素，那麼將它與一個直接兄弟節點以及父節點中它們的分隔值合併
  1. 將分隔值複製到左邊的節點（左邊的節點可以是缺少元素的節點或者擁有最小數量元素的兄弟節點）
  2. 將右邊節點中所有的元素移動到左邊節點（左邊節點現在擁有最大數量的元素，右邊節點為空）
  3. 將父節點中的分隔值和空的右子樹移除（父節點失去了一個元素）
     • 如果父節點是根節點並且沒有元素了，那麼釋放它並且讓合併之後的節點成為新的根節點（樹的深度減小）
     • 否則，如果父節點的元素數量小於最小值，重新平衡父節點

相關條目

B+樹