B树

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

## 概述

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

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

通常，鍵的數量被選定在 $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（log2N）比較級完成。如果表有 1,000,000 筆記錄，那麼定位其中一筆記錄，將在 20 個比較級內完成。
log2(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，p.362）。

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

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

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

### 定義

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

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

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

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

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

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

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

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

## 演算法

### 搜尋

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

### 插入

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

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

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

### 刪除

有兩種常用的刪除策略

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

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

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

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

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

#### 刪除葉子節點中的元素

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

#### 刪除內部節點中的元素

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

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

#### 刪除後的重新平衡

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

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

## 相關條目

B + 樹