B树

概述

在B樹中，內部（非葉子）節點可以擁有可變數量的子節點（數量範圍預先定義好）。當數據被插入或從一個節點中移除，它的子節點數量發生變化。為了維持在預先設定的數量範圍內，內部節點可能會被合併或者分離。因為子節點數量有一定的允許範圍，所以B樹不需要像其他自平衡查找樹那樣頻繁地重新保持平衡，但是由於節點沒有被完全填充，可能浪費了一些空間。子節點數量的上界和下界依特定的實現而設置。例如，在一個2-3 B樹（通常簡稱2-3樹），每一個內部節點只能有2或3個子節點。
B樹中每一個內部節點會包含一定數量的鍵，鍵將節點的子樹分開。例如，如果一個內部節點有3個子節點（子樹），那麼它就必須有兩個鍵： a₁ 和 a₂ 。左邊子樹的所有值都必須小於 a₁ ，中間子樹的所有值都必須在 a₁ 和a₂ 之間，右邊子樹的所有值都必須大於 a₂ 。
通常，鍵的數量被選定在  和  之間。其中  是鍵的最小數量， 是樹最小的 度 或 分支因子 。在實際中，鍵值占用了節點中大部分的空間。因數2將保證節點可以被拆分或組合。如果一個內部節點有  個鍵，那麼要添加一個鍵值給此節點，只需要拆分這  個鍵為2個 擁有  個鍵的節點，並把中間值節點移動到父節點。每一個拆分的節點需要擁有足夠數目的鍵。相似地，如果一個內部節點和他的鄰居兩者都有  個鍵，那麼將通過它與鄰居的合併來刪除一個鍵。刪除此鍵將導致此節點擁有  個鍵;與鄰居的合併則加上  個鍵，再加上從鄰居節點的父節點移來的一個鍵值。結果為完全填充的  個鍵。
一個節點的分支（或子節點）的數量會比存儲在節點內部鍵值的數量大1。在 2-3 B樹中，內部節點將會存儲1個鍵值（帶有2個子節點）或2個鍵值（帶有3個子節點）。一個B樹有時會被描述為  或簡單地使用最高分支  。
一個Ｂ樹通過約束所有葉子節點在相同深度來保持平衡。深度在元素添加至樹的過程中緩慢增長，而整體深度極少地增長，並導致所有葉子節點與根節點距離加1。
在存取節點數據所耗時間遠超過處理節點數據所耗時間的情況下，Ｂ樹在可選的實現中擁有很多優勢，因為存取節點的開銷被分攤到裡層節點的多次操作上。這通常出現在當節點存儲在二級存儲器如硬碟存儲器上。通過最大化內部裡層節點的子節點的數量，樹的高度減小，存取節點的開銷被縮減。另外，重新平衡樹的動作也更少出現。子節點的最大數量取決於，每個子節點必需存儲的信息量，和完整磁碟塊的大小或者二次存儲器中類似的容量。雖然 2-3 樹更易於解釋，實際運用中，Ｂ樹使用二級存儲器，需要大量數目的子節點來提升效率。

變體

術語B樹可以指一個特定的方案，也可以指大體上一類方案。狹義上，一個Ｂ樹在它內部節點中存儲鍵值，但不需在葉子節點上存儲這些鍵值的記錄。大體上的一類包含一些變體，如B+樹和B*樹。
在B⁺樹，這些鍵值的拷貝被存儲在內部節點；鍵值和記錄存儲在葉子節點；另外，一個葉子節點可以包含一個指針，指向另一個葉子節點以加速順序存取。
B*樹分支出更多的內部鄰居節點以保持內部節點更密集地填充。此變體要求非根節點至少2/3填充，而不是1/2。為了維持這樣的結構，當一個節點填滿之後將不會再立即分割節點，而是將它的鍵值與下一個節點共享。當兩個節點都填滿之後，分割成3個節點。
計數B樹存儲，每一樹都帶有一個指針和其指向子樹的節點數目。這就允許了以鍵值為序快速查找第N筆記錄，或是統計2筆記錄之間的記錄數目，還有其他很多相關的操作。

名字取義

Rudolf Bayer 和 Ed 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樹的術語並不統一 （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）。

搜索

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