文章出處

B 樹（B-Tree）是為磁盤等輔助存取設備設計的一種平衡查找樹，它實現了以 O(log n) 時間復雜度執行查找、順序讀取、插入和刪除操作。由于 B 樹和 B 樹的變種在降低磁盤 I/O 操作次數方面表現優異，所以經常用于設計文件系統和數據庫。

在 1972 年，在 Boeing Research Labs 工作的 Rudolf Bayer 和 Ed McCreight 發明了 B 樹。當時他們并沒有解釋 B 樹中的 "B" 代表什么涵義，所以猜測的多是 "Balanced", "Broad", "Bushy", "Boeing", "Bayer" 等，不過通常使用 "Balanced" 來描述樹是平衡的。Ed McCreight 在 CPM 2013 會議中回答 "B" 的起源問題時說："對 B 的涵義思考的越多，對 B 樹的理解則越深。"。

如下圖是一棵鍵值為英語字母的 B 樹，帶淺陰影的節點是查找字母 R 時要檢查的節點。

B 樹內的節點關系

B 樹中的節點分為內部節點（Internal Node）和葉節點（Leaf Node），內部節點也就是非葉節點（Non-Leaf Node）。

B 樹的內部節點可以包含 2 個以上的子節點，所以在設計時可以預先設定可包含子節點的數量范圍，也就是上界（Upper Bound）和下界（Lower Bound）。當向節點插入或刪除數據時，也就意味著子節點的數量發生變化。為了維持在預先設定的數量范圍，內部節點可能會被合并（Join）或拆分（Split）。因為子節點的數量有一定的范圍，所以 B 樹不需要頻繁地變化以保持平衡。但同時，由于節點可能沒有被完全填充，所以會浪費一些空間。

B 樹中每一個內部節點會包含一定數量的鍵值（Key）。這些鍵值同時也扮演著分割子節點的角色。例如，假設某內部節點包含 3 個子節點，則實際上必須有 2 個鍵值：a1 和 a2。其中，a1 的左子樹上的所有的值都要小于 a1，在 a1 和 a2 之間的子樹中的值都大于 a1 并小于 a2，a2 的右子樹上的所有的值都大于 a2。

通常，鍵值的數量被設定在 d 和 2d 之間，其中 d 是可包含鍵值的最小數量。可知，d + 1 是節點可擁有子節點的最小數量，也就是樹的最小的度（Degree）。因數 2 將確保節點可以被合并或拆分。

如果一個內部節點有 2d 個鍵值，那么添加一個鍵值給該節點將會導致 2d + 1 的數量大于范圍上界，則會拆分 2d + 1 數量的節點為 2 個 d 數量的節點，并有 1 個鍵值提升至父節點中。

類似地，如果一個內部節點和它的鄰居節點（Neighbor）都包含 d 個鍵值，那么刪除一個鍵值將導致此節點擁有 d - 1 個鍵值，小于范圍下界，則會導致與鄰居節點合并。合并后的節點包括 d – 1 的數量加上鄰居的 d 的數量和兩者的父節點中的 1 個鍵值，共為 d – 1 + d + 1 = 2d 數量的節點。

深度（Depth）描述樹中層（Level）的數量。B 樹通過要求所有葉節點保持在相同深度來保持樹的平衡。深度通常會隨著鍵值的不斷添加而緩慢地增長。

B 樹的定義

對于 B 樹定義中的一些術語常有混淆，比如對于階（Order）的定義。Knuth Donald 在 1998 年將階（Order）定義為節點包含子節點的最大數量。

使用階來定義 B 樹，一棵 m 階的 B 樹，需要滿足下列條件：

  1. 每個節點最多包含 m 個子節點。
  2. 除根節點外，每個非葉節點至少包含 m/2 個子節點。
  3. 如果根節點包含子節點，則至少包含 2 個子節點。
  4. 擁有 k 個子節點的非葉節點將包含 k - 1 個鍵值。
  5. 所有葉節點都在同一層中。

下面是一棵高度（Height）h = 3 的 B 樹。

B 樹上大部分操作所需的磁盤存取次數與 B 樹的高度成正比。

使用 h 代表 B 樹的高度；使用 n 代表整個樹中包含鍵值的數量 n > 0；m 為內部節點可包含子節點的最大數量，則當樹滿時 n = mh – 1；每個內部節點最多包含 m - 1 個鍵值；使用 d 代表內部節點可包含最少子節點的數量，即最小度數（Degree）有 d = ⌈m/2⌉。

B 樹的最優條件下的 h 為：

B 樹的最差條件下的 h 為：

合理的選取最小度數 d 的值，可以大大地降低樹的高度，則可降低查找任意鍵值時所需的磁盤存取次數。與自平衡二叉樹相比，高度都以 O(log n) 的速度增長，對 B 樹來說對數的底要大很多倍。對于大多數樹操作來說，B 樹要比自平衡二叉樹節省大約 lg d 因子的節點檢查次數。因為在樹中查找任意一個節點通常都需要一次磁盤存取，所以磁盤存取的次數大大地減少了。

B 樹的操作

查詢操作

在 B 樹中查詢鍵值與在二叉樹中的鍵值查詢方式是類似的。從根節點開始查詢，通過遞歸進行自頂向下的遍歷。在每一層上，將查詢鍵值與內部節點中的鍵值比較，以確定向哪個子樹中進行遍歷。

二叉樹相關的查詢可參考如下文章：

插入操作

當要插入一個新的鍵值時，首先在樹中找到該鍵值應當被插入的葉節點的位置：

  • 如果葉節點包含鍵值的數量在設定的范圍上界和下界內，則直接插入新鍵值，并保持鍵值在節點中順序。
  • 否則，節點已滿，將節點分割為 2 個節點：
    1. 選擇中間值（Median）作為分割點；
    2. 小于中間值的鍵值放入新的左節點中，大于中間值的鍵值放入新的右節點中；
    3. 將中間值插入到父節點中。此時可能導致父節點滿，采用同樣方式分割。如果父節點不存在，比如是根節點，則創建一個新的父節點，也就導致樹的高度增長。

刪除操作

在 B 樹中刪除鍵值可以通過不同的策略來實現，這里介紹常見的定位刪除策略：定位鍵值后刪除，然后重構整個樹至平衡。平衡指的是仍然保持 B 樹的性質。

  1. 搜索要被刪除鍵值的位置。
  2. 如果鍵值在葉節點中，則直接刪除。
  3. 如果鍵值在內部節點中，由于其正扮演分割子節點的角色，所以刪除后需要找一個替代鍵值繼續保持兩個子節點的分割。此時，可以選擇左子節點中最大的鍵值，或者右子節點中最小的鍵值。將選中的鍵值從子節點中刪除，然后插入到被替換的位置。
  4. 如果刪除鍵值后的節點已經不滿足對最少鍵值數量的要求，則需要重平衡整棵樹，平衡操作包括旋轉（Rotation）、組合（Join）等。

B 樹的變種

"B 樹" 這個術語在實際應用中還代表著多種 B 樹的變種，它們有著相似的結構，卻各有特點和優勢：

  • B 樹在其內部節點中存儲的鍵值不會再在葉節點中存儲，內部節點不僅存儲鍵值也會存儲鍵值關聯附屬數據，或者存儲指向關聯附屬數據的指針。同時，B 樹會保持內部節點的 1/2 填充。
  • B+ 樹是 B 樹的一個變種，在內部節點中存儲的鍵值同樣也會出現在葉節點中，但內部節點中不存儲關聯附屬數據或指針。在葉節點中的不僅存儲鍵值，還存儲關聯附屬數據或指針。此外，葉節點還增加了一個指向下一個順序關聯葉節點的指針，以改進順序讀取的速度。
  • B* 樹也是 B 樹的一個變種，要求除根節點外的內部節點要至少 2/3 填充，而不是 1/2 填充。為了維持這樣的結構，當一個節點填滿后不會立即分割節點，而是將它的鍵值與下一個節點共享，當兩個節點都填滿之后，再將 2 個節點分割成 3 個節點。

B+ 樹的優勢

B+ 樹是 B 樹的一個變種，在內部節點中存儲的鍵值同樣也會出現在葉節點中，但內部節點中不存儲關聯附屬數據或指針。在葉節點中的不僅存儲鍵值，還存儲關聯附屬數據或指針。這樣，所有的附屬數據都保存在了葉節點中，只將鍵值和子女指針保存在了內節點中，因此最大化了內節點的分支能力。

此外，葉節點還增加了一個指向下一個順序關聯葉節點的指針，以改進順序讀取的速度。

常見的文件系統和數據庫均使用 B+ 樹實現，例如：

  • 文件系統：NTFS, ReiserFS, NSS, XFS, JFS, ReFS, BFS, Ext4；
  • 關系型數據庫：DB2, Informix, SQL Server, Oracle, Sybase ASE, SQLite；
  • NoSQL 數據庫：CouchDB, Tokyo Cabinet；

B+ 樹的優勢在于：

  • 由于內部節點不存儲鍵值關聯的附屬數據，所以內部節點節省的空間可以存放更多的鍵值。也就意味著從磁盤存取一頁時可獲得更多的鍵值信息。
  • 葉節點形成了一個鏈，所以對樹的全掃描就是對所有葉節點的線性遍歷。

B+ 樹 C# 代碼實現

在 GitHub 上的項目 BPlusTreePractice 使用 C# 語言實現了簡單的 B+ 樹，功能包括插入鍵值對、搜索鍵、刪除鍵、存儲至磁盤塊文件等，但未實現節點鏈的雙向鏈表和掃描功能。

下面是測試代碼示例。

 1 using System;
 2 using System.IO;
 3 
 4 namespace BPlusTreePractice
 5 {
 6   class Program
 7   {
 8     static void Main(string[] args)
 9     {
10       // 指定磁盤文件位置
11       string treeFileName = 
12         @"E:\BPlusTree_" + DateTime.Now.ToString(@"yyyyMMddHHmmssffffff") + ".data";
13       Stream treeFileStream = 
14         new FileStream(treeFileName, FileMode.CreateNew, FileAccess.ReadWrite);
15 
16       // 初始化 B+ 樹，固定長度字符串為鍵，映射至長整形
17       int keyLength = 64;
18       int nodeCapacity = 2;
19       BPlusTree tree = 
20         BPlusTree.InitializeInStream(treeFileStream, 0L, keyLength, nodeCapacity);
21 
22       // 插入 0 到 7 共 8 個鍵值對
23       for (int i = 0; i < 8; i++)
24       {
25         tree.Set(i.ToString(), (long)(i * 1000)); // Key 是字符串，Value 是 long 類型
26       }
27 
28       // 將 B+ 樹輸出到命令行
29       Console.WriteLine(tree.ToText());
30 
31       // 獲取指定的鍵值對
32       Console.WriteLine();
33       Console.WriteLine(string.Format("Tree's first key is {0}.", tree.FirstKey()));
34       Console.WriteLine(string.Format("Check key {0} exists {1}.", 
35         "3", tree.ContainsKey("3")));
36       Console.WriteLine(string.Format("{0}'s next key is {1}.", "6", tree.NextKey("6")));
37       Console.WriteLine(string.Format("Get key {0} with value {1}.", "2", tree.Get("2")));
38       Console.WriteLine(string.Format("Index key {0} with value {1}.", "4", tree["4"]));
39       Console.WriteLine();
40 
41       // 刪除鍵值對
42       tree.RemoveKey("6");
43       Console.WriteLine(tree.ToText());
44 
45       Console.ReadKey();
46     }
47   }
48 }

本篇文章《B 樹和 B+ 樹》由 Dennis Gao 發表自博客園個人技術博客，未經作者本人同意禁止任何形式的轉載，任何自動或人為的爬蟲轉載或抄襲行為均為耍流氓。


文章列表


不含病毒。www.avast.com
全站熱搜
創作者介紹
創作者 大師兄 的頭像
大師兄

IT工程師數位筆記本

大師兄 發表在 痞客邦 留言(0) 人氣()

E-mail轉寄