B樹

B樹一個節點可以擁有2個以上的子節點。與自平衡二叉查詢樹不同，B樹適用於讀寫相對大的資料塊的儲存系統，例如磁碟。B樹減少定位記錄時所經歷的中間過程，從而加快存取速度。B樹這種資料結構可以用來描述外部儲存。這種資料結構常被應用在資料庫和檔案系統的實現上。概述.在B樹中，內部，每一個內部節點只能有2或3個子節點。B樹中每一個內部節點會包含一定數量的鍵，鍵將節點的子樹分開。例如，如果一個內部節點有3個子節點，那麼它就必須有兩個鍵： "a"1 和 "a"2 。左邊子樹的所有值都必須小於 "a"1 ，中間子樹的所有值都必須在 "a"1 和"a"2 之間，右邊子樹的所有值都必須大於 "a"2 。通常，鍵的數量被選定在 formula_1 和 formula_2 之間。其中 formula_1 是鍵的最小數量，formula_4 是樹最小的 度 或 分支因子 。在實際中，鍵值佔用了節點中大部分的空間。因數2將保證節點可以被拆分或組合。如果一個內部節點有 formula_2 個鍵，那麼要新增一個鍵值給此節點，只需要拆分這 formula_6 個鍵為2個 擁有 formula_1 個鍵的節點，並把中間值節點移動到父節點。每一個拆分的節點需要擁有足夠數目的鍵。相似地，如果一個內部節點和他的鄰居兩者都有 formula_1 個鍵，那麼將透過它與鄰居的合併來刪除一個鍵。刪除此鍵將導致此節點擁有 formula_9 個鍵;與鄰居的合併則加上 formula_1 個鍵，再加上從鄰居節點的父節點移來的一個鍵值。結果為完全填充的 formula_2 個鍵。一個節點的分支。一個B樹有時會被描述為 formula_12 或簡單地使用最高分支 formula_13 。一個Ｂ樹透過約束所有葉子節點在相同深度來保持平衡。深度在元素新增至樹的過程中緩慢增長，而整體深度極少地增長，並導致所有葉子節點與根節點距離加1。在存取節點資料所耗時間遠超過處理節點資料所耗時間的情況下，Ｂ樹在可選的實現中擁有很多優勢，因為存取節點的開銷被分攤到裡層節點的多次操作上。這通常出現在當節點儲存在二級儲存器如硬碟儲存器上。透過最大化內部裡層節點的子節點的數量，樹的高度減小，存取節點的開銷被縮減。另外，重新平衡樹的動作也更少出現。子節點的最大數量取決於，每個子節點必需儲存的資訊量，和完整磁碟塊的大小或者二次儲存器中類似的容量。雖然 2-3 樹更易於解釋，實際運用中，Ｂ樹使用二級儲存器，需要大量數目的子節點來提升效率。變體.術語B樹可以指一個特定的方案，也可以指大體上一類方案。狹義上，一個Ｂ樹在它內部節點中儲存鍵值，但不需在葉子節點上儲存這些鍵值的記錄。大體上的一類包含一些變體，如B+樹和B*樹。在B+樹，這些鍵值的複製被儲存在內部節點；鍵值和記錄儲存在葉子節點；另外，一個葉子節點可以包含一個指標，指向另一個葉子節點以加速順序存取。B*樹分支出更多的內部鄰居節點以保持內部節點更密集地填充。此變體要求非根節點至少2/3填充，而不是1/2。為了維持這樣的結構，當一個節點填滿之後將不會再立即分割節點，而是將它的鍵值與下一個節點共享。當兩個節點都填滿之後，分割成3個節點。計數B樹儲存，每一樹都帶有一個指標和其指向子樹的節點數目。這就允許了以鍵值為序快速查詢第N筆記錄，或是統計2筆記錄之間的記錄數目，還有其他很多相關的操作。名字取義.魯道夫·拜爾 在他1980年5月發表的題為“CS144C classroom lecture about disk storage and B-trees”的論文中推測了B樹的名字取義，提出“B”可能意味Boeing 或者Bayer 的名字。資料庫的問題.已排序檔案的查詢時間.通常，排序和查詢演算法會被透過大O符號，刻畫為比較級別的數值。對一個有N筆記錄的已排序表進行二叉查詢，打個比方說，可以在O比較級完成。如果表有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樹運用的理念.B樹使用了以上所有的想法。特別是：另外，B樹透過保證內部節點至少半滿來最小化空間浪費。一棵B樹可以處理任意數目的插入和刪除。B樹的弊端.。術語和定義.術語.B樹的術語並不統一 #重定向 。術語 "葉子" 的定義也不一致。 #重定向 認為葉子層是最下面一層的鍵，但是 Knuth 認為葉子層是最下面一層鍵之下的一層 #重定向 。可能的實現有許多。在一些設計中，葉子可能儲存了完整的資料記錄；在另一些設計中，葉子可能只儲存了指向資料記錄的指標。為了簡化，許多作者假定一個節點能夠容納固定數量的鍵。基礎的假設是鍵和節點的大小都是固定的。事實上，可變長度的鍵可能會被使用 #重定向 。定義.根據 Knuth 的定義，一個 "m" 階的B樹是一個有以下屬性的樹：每一個內部節點的鍵將節點的子樹分開。例如，如果一個內部節點有3個子節點，那麼它就必須有兩個鍵： "a"1 和 "a"2 。左邊子樹的所有值都必須小於 "a"1 ，中間子樹的所有值都必須在 "a"1 和"a"2 之間，右邊子樹的所有值都必須大於 "a"2 。內部節點是除葉子節點和根節點之外的所有節點。它們通常被表示為一組有序的元素和指向子節點的指標。每一個內部節點擁有最多 "U" 個，最少 "L" 個子節點。元素的數量總是比子節點指標的數量少一。這些特性使得在B樹中刪除或插入新的值時可以調整樹來保持B樹的性質。根節點擁有的子節點數量的上限和內部節點相同，但是沒有下限。例如，當整個樹中的元素數量小於 "L"-1 時，根節點是唯一的節點並且沒有任何子節點。葉子節點對元素的數量有相同的限制，但是沒有子節點，也沒有指向子節點的指標。一個深度為"n"+1 的B樹可以容納的元素數量大約是深度為 "n" 的B樹的 "U" 倍，但是搜尋、插入和刪除操作的開銷也會增加。和其他的平衡樹一樣，這一開銷增加的速度遠遠慢於元素數量的增加。一些平衡樹只在葉子節點中儲存值，而且葉子節點和內部節點使用不同的結構。B樹在每一個節點中都儲存值，所有的節點有著相同的結構。然而，因為葉子節點沒有子節點，所以可以透過使用專門的結構來提高B樹的效能。演算法.搜尋.B樹的搜尋和二叉搜尋樹類似。從根節點開始，從上到下遞迴的遍歷樹。在每一層上，搜尋的範圍被減小到包含了搜尋值的子樹中。子樹值的範圍被它的父節點的鍵確定。插入.所有的插入都從根節點開始。要插入一個新的元素，首先搜尋這棵樹找到新元素應該被新增到的對應節點。將新元素插入到這一節點中的步驟如下：如果分裂一直上升到根節點，那麼一個新的根節點會被建立，它有一個分隔值和兩個子節點。這就是根節點並不像內部節點一樣有最少子節點數量限制的原因。每個節點中元素的最大數量是 "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，正好是節點允許的最小元素數量。刪除.有兩種常用的刪除策略以下的演算法使用了前一種策略。刪除一個元素時有以下兩種特殊情況下面分別是這些情況的處理過程刪除內部節點中的元素.內部節點中的每一個元素都作為分隔兩顆子樹的分隔值，因此我們需要重新劃分。值得注意的是左子樹中最大的元素仍然小於分隔值。同樣的，右子樹中最小的元素仍然大於分隔值。這兩個元素都在葉子節點中，並且任何一個都可以作為兩顆子樹的新分隔值。演算法的描述如下：刪除後的重新平衡.重新平衡從葉子節點開始向根節點進行，直到樹重新平衡。如果刪除節點中的一個元素使該節點的元素數量低於最小值，那麼一些元素必須被重新分配。通常，移動一個元素數量大於最小值的兄弟節點中的元素。如果兄弟節點都沒有多餘的元素，那麼缺少元素的節點就必須要和他的兄弟節點 合併。合併可能導致父節點失去了分隔值，所以父節點可能缺少元素並需要重新平衡。合併和重新平衡可能一直進行到根節點，根節點變成惟一缺少元素的節點。重新平衡樹的演算法如下：相關條目.B+樹