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

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

  魯道夫·拜爾()和 艾華·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(logN)比較級完成。如果表有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樹的 "階" 定義為非根節點擁有鍵的最小數量。 指出這一術語是模糊不清的。一個 3 階B樹鍵的最大數量可能為 6 或 7。 通過將 "階" 定義為最大數量的子節點(比最大數量的鍵大1)來避免這一問題。  術語 "葉子" 的定義也不一致。 認為葉子層是最下面一層的鍵,但是 Knuth 認為葉子層是最下面一層鍵之下的一層 。可能的實現有許多。在一些設計中,葉子可能儲存了完整的資料記錄;在另一些設計中,葉子可能只儲存了指向資料記錄的指標。  為了簡化,許多作者假定一個節點能夠容納固定數量的鍵。基礎的假設是鍵和節點的大小都是固定的。事實上,可變長度的鍵可能會被使用 。

  根據 Knuth 的定義,一個 "m" 階的B樹是一個有以下屬性的樹:  每一個內部節點的鍵將節點的子樹分開。例如,如果一個內部節點有3個子節點(子樹),那麼它就必須有兩個鍵: "a" 和 "a" 。左邊子樹的所有值都必須小於 "a",中間子樹的所有值都必須在 "a" 和"a" 之間,右邊子樹的所有值都必須大於 "a" 。  一個深度為"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+樹
在電腦科學中,B樹(英語:B-tree)是一種自平衡的樹,能夠保持資料有序。這種資料結構能夠讓查詢資料、順序訪問、插入資料及刪除的動作,都在對數時間內完成。B樹,概括來說是一個一般化的二元搜尋樹(binary search tree)一個節點可以擁有2個以上的子節點。與自平衡二叉查詢樹不同,B樹適用於讀寫相對大的資料塊的儲存系統,例如磁碟。B樹減少定位記錄時所經歷的中間過程,從而加快存取速度。B樹這種資料結構可以用來描述外部儲存。這種資料結構常被應用在資料庫和檔案系統的實現上。