B-樹

在計算機科學中，B樹（英語：B-tree）是一種自平衡的樹，能夠保持數據有序。這種數據結構能夠讓查找數據、順序訪問、插入數據及刪除的動作，都在對數時間內完成。B樹，概括來説是一個一般化的二叉查找樹（binary search tree），可以擁有多於2個子節點。與自平衡二叉查找樹不同，B樹為系統大塊數據的讀寫操作做了優化。B樹減少定位記錄時所經歷的中間過程，從而加快存取速度。B樹這種數據結構可以用來描述外部存儲。這種數據結構常被應用在數據庫和文件系統的實現上。 ^[1] 

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

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

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

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

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

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

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

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

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

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

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

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

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

為進一步加速查找，開始的13或14個比較級（每個需要一次磁盤訪問）必須要提速。 ^[1] 

較大程度上的提升是通過索引來做到的。在上面的例子中，初始磁盤讀取從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樹可以處理任意數目的插入和刪除。

（其他關聯數組的實現，例如三元搜索樹或者開散列哈希表，可以動態適應任意長度的鍵值）。 ^[1]