主題
Search

B 樹


B-樹由 Bayer (1972) 和 McCreight 引入。它們是一種特殊的 m 階平衡樹,因其結構允許記錄的插入、刪除和檢索,並保證最壞情況下的效能,而被廣泛應用於資料庫中。一個有 n 個節點的 B-樹的高度為 O(lgn),其中 lg 是以 2 為底的 對數。Apple® Macintosh® (Apple, Inc., Cupertino, CA) HFS 檔案系統使用 B-樹來儲存磁碟目錄 (Benedict 1995)。一個 B-樹滿足以下屬性:

1. 節點要麼是一個葉節點,要麼至少有兩個子節點

2. 每個節點(除了節點和葉節點)擁有介於 [m/2]m 之間的子節點,其中 [x]向上取整函式

3. 從節點到葉節點的每條路徑長度相同。

每個 2-3 都是一個 3 階 B-樹。具有 B-樹的 3 階,葉節點數為 n=1, 2, ... 的 B 樹的數量分別是 1, 1, 1, 1, 2, 2, 3, 4, 5, 8, 14, 23, 32, 43, 63, ... (Ruskey, OEIS A014535)。葉節點數為 n=1, 2, ... 的 4 階 B-樹的數量分別是 1, 1, 1, 2, 2, 4, 5, 9, 15, 28, 45, ... (OEIS A037026)。


參見

紅黑樹,

使用 探索

參考文獻

Aho, A. V.; Hopcroft, J. E.; 和 Ullmann, J. D. 資料結構與演算法。 Reading, MA: Addison-Wesley, pp. 369-374, 1987.Bayer, R. 和 McCreight, E. "大型有序索引的組織與維護。" Acta Informatica 1, 173-189, 1972.Benedict, B. Macintosh 版 Norton Utilities 使用指南。 Indianapolis, IN: Que, pp. B-17-B-33, 1995.Beyer, R. "對稱二叉 B-樹:資料結構與維護演算法。" Acta Informat. 1, 290-306, 1972.Knuth, D. E. "B 樹。" 計算機程式設計藝術,第 3 卷:排序與查詢,第 2 版。 Reading, MA: Addison-Wesley, pp. 482-485 和 490-491, 1998.Ruskey, F. "關於 B 樹的資訊。" http://www.theory.csc.uvic.ca/~cos/inf/tree/BTrees.html.Skiena, S. S. 演算法設計手冊。 New York: Springer-Verlag, p. 178, 1997.Sloane, N. J. A. 序列 A014535A037026 在 "整數序列線上百科全書" 中。

在 中引用

B 樹

請引用本文獻為

Weisstein, Eric W. "B 樹。" 來自 Web 資源。 https://mathworld.tw/B-Tree.html

主題分類