跳转至

B 樹

引入

在計算機科學中，B 樹（B-tree）是一種自平衡的樹，能夠保持數據有序。這種數據結構能夠讓查找數據、順序訪問、插入數據及刪除的動作，都在對數時間內完成。

在 B 樹中，有兩種節點：

  1. 內部節點（internal node）：存儲了數據以及指向其子節點的指針。
  2. 葉子節點（leaf node）：與內部節點不同的是，葉子節點只存儲數據，並沒有子節點。

樹是一種數據結構。樹用多個節點儲存元素。某些節點存在一定的關係，用連線表示。二叉樹是一種特殊的樹，每個節點最多有兩個子樹。二叉樹常用於實現二叉搜索樹和二叉堆。 而 AVL 樹 是特殊的二叉樹，是最早被髮明的自平衡二叉查找樹。B 樹保留了自平衡的特點，但 B 樹的每個節點可以擁有兩個以上的子節點，因此 B 樹是一種多路搜索樹。

性質

首先介紹一下一棵 \(m\) 階的 B 樹的特性。\(m\) 表示這個樹的每一個節點最多可以擁有的子節點個數。一棵 \(m\) 階的 B 樹滿足的性質如下：

  1. 每個節點最多有 \(m\) 個子節點。
  2. 每一個非葉子節點（除根節點）最少有 \(\lceil \dfrac{m}{2} \rceil\) 個子節點。
  3. 如果根節點不是葉子節點，那麼它至少有兩個子節點。
  4. 有 \(k\) 個子節點的非葉子節點擁有 \(k−1\) 個鍵，且升序排列，滿足 \(k[i] < k[i+1]\)。
  5. 每個節點至多包含 \(2k-1\) 個鍵。
  6. 所有的葉子節點都在同一層。

一個簡單的圖例如下：

過程

與 二叉搜索樹 類似，B 樹的基本操作有查找，遍歷，插入，刪除。

查找

B 樹中的節點包含有多個鍵。假設需要查找的是 \(k\)，那麼從根節點開始，從上到下遞歸的遍歷樹。在每一層上，搜索的範圍被減小到包含了搜索值的子樹中。 子樹值的範圍被它的父節點的鍵確定。因為是從根節點開始的二分法查找，所以查找一個鍵的代碼如下：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
BTreeNode *BTreeNode::search(int k) {
  // 找到第一個大於等於待查找鍵 k 的鍵
  int i = 0;
  while (i < n && k > keys[i]) i++;

  // 如果找到的第一個鍵等於 k , 返回節點指針
  if (keys[i] == k) return this;

  // 如果沒有找到鍵 k 且當前節點為葉子節點則返回NULL
  if (leaf == true) return NULL;

  // 遞歸
  return C[i]->search(k);
}

遍歷

B 樹的中序遍歷與二叉搜索樹的中序遍歷也很相似，從最左邊的孩子節點開始，遞歸地打印最左邊的孩子節點，然後對剩餘的孩子和鍵重複相同的過程。 最後，遞歸打印最右邊的孩子節點。

遍歷的代碼如下：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void BTreeNode::traverse() {
  // 有 n 個鍵和 n+1 個孩子
  // 遍歷 n 個鍵和前 n 個孩子
  int i;
  for (i = 0; i < n; i++) {
    // 如果當前節點不是葉子節點, 在打印 key[i] 之前,
    // 先遍歷以 C[i] 為根的子樹.
    if (leaf == false) C[i]->traverse();
    cout << " " << keys[i];
  }

  // 打印以最後一個孩子為根的子樹
  if (leaf == false) C[i]->traverse();
}

插入

為了方便表述，插入設定為在以 \(o\) 為根節點的 B 樹中插入一個值為 \(v\) 的新節點。

一個新插入的 \(v\) 總是被插入到葉子節點。與二叉搜索樹的插入操作類似，從根節點開始，向下遍歷直到葉子節點，將值為 \(v\) 的新節點插入到相應的葉子節點。 與二叉搜索樹不同的是，通過最小度定義了一個節點可以包含鍵的個數的一個取值範圍，所以在插入一個新節點時，就需要確認插入這個葉子節點之後，它的父節點是否超出該節點本身最大可容納的節點個數。

針對一棵高度為 \(h\) 的 \(m\) 階 B 樹，插入一個元素時，首先要驗證該元素在 B 樹中是否存在，如果不存在，那麼就要在葉子節點中插入該新的元素，此時分 3 種情況：

  1. 如果葉子節點空間足夠，即該節點的關鍵字數小於 \(m-1\)，則直接插入在葉子節點的左邊或右邊；
  2. 如果空間滿了以至於沒有足夠的空間去添加新的元素，即該節點的關鍵字數已經有了 \(m\) 個，則需要將該節點進行「分裂」，將一半數量的關鍵字元素分裂到新的其相鄰右節點中，中間關鍵字元素上移到父節點中，而且當節點中關鍵元素向右移動了，相關的指針也需要向右移。
    1. 從該節點的原有元素和新的元素中選擇出中位數
    2. 小於這一中位數的元素放入左邊節點，大於這一中位數的元素放入右邊節點，中位數作為分隔值。
    3. 分隔值被插入到父節點中，這可能會造成父節點分裂，分裂父節點時可能又會使它的父節點分裂，以此類推。如果沒有父節點（這一節點是根節點），就創建一個新的根節點（增加了樹的高度）。

如果一直分裂到根節點，那麼就需要創建一個新的根節點。它有一個分隔值和兩個子節點。

這就是根節點並不像內部節點一樣有最少子節點數量限制的原因。每個節點中元素的最大數量是 \(U-1\)。當一個節點分裂時，一個元素被移動到它的父節點，但是一個新的元素增加了進來。所以最大的元素數量 \(U-1\) 必須能夠被分成兩個合法的節點。 如果 \(U-1\) 是奇數，那麼 \(U=2L\)，總共有 \(2L-1\) 個元素，一個新的節點有 \(L-1\) 個元素，另外一個有 \(L\) 個元素，都是合法的節點。如果 \(U-1\) 是偶數，那麼 \(U=2L-1\), 總共有 \(2L-2\) 個元素。一半是 \(L-1\)，正好是節點允許的最小元素數量。

插入的代碼如下：

實現 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
void BTree::insert(int k) {
  // 如果樹為空樹
  if (root == NULL) {
    // 為根節點分配空間
    root = new BTreeNode(t, true);
    root->keys[0] = k;  // 插入節點 k
    root->n = 1;        // 更新根節點的關鍵字的個數為 1
  } else {
    // 當根節點已滿，則對B-樹進行生長操作
    if (root->n == 2 * t - 1) {
      // 為新的根節點分配空間
      BTreeNode *s = new BTreeNode(t, false);

      // 將舊的根節點作為新的根節點的孩子
      s->C[0] = root;

      // 將舊的根節點分裂為兩個，並將一個關鍵字上移到新的根節點
      s->splitChild(0, root);

      // 新的根節點有兩個孩子節點
      // 確定哪一個孩子將擁有新插入的關鍵字
      int i = 0;
      if (s->keys[0] < k) i++;
      s->C[i]->insertNonFull(k);

      // 新的根節點更新為 s
      root = s;
    } else  // 根節點未滿，調用 insertNonFull() 函數進行插入
      root->insertNonFull(k);
  }
}

// 將關鍵字 k 插入到一個未滿的節點中
void BTreeNode::insertNonFull(int k) {
  // 初始化 i 為節點中的最後一個關鍵字的位置
  int i = n - 1;

  // 如果當前節點是葉子節點
  if (leaf == true) {
    // 下面的循環做兩件事：
    // a) 找到新插入的關鍵字位置並插入
    // b) 移動所有大於關鍵字 k 的向後移動一個位置
    while (i >= 0 && keys[i] > k) {
      keys[i + 1] = keys[i];
      i--;
    }

    // 插入新的關鍵字，節點包含的關鍵字個數加 1
    keys[i + 1] = k;
    n = n + 1;
  } else {
    // 找到第一個大於關鍵字 k 的關鍵字 keys[i] 的孩子節點
    while (i >= 0 && keys[i] > k) i--;

    // 檢查孩子節點是否已滿
    if (C[i + 1]->n == 2 * t - 1) {
      // 如果已滿，則進行分裂操作
      splitChild(i + 1, C[i + 1]);

      // 分裂後，C[i] 中間的關鍵字上移到父節點，
      // C[i] 分裂稱為兩個孩子節點
      // 找到新插入關鍵字應該插入的節點位置
      if (keys[i + 1] < k) i++;
    }
    C[i + 1]->insertNonFull(k);
  }
}

// 節點 y 已滿，則分裂節點 y
void BTreeNode::splitChild(int i, BTreeNode *y) {
  // 創建一個新的節點存儲 t - 1 個關鍵字
  BTreeNode *z = new BTreeNode(y->t, y->leaf);
  z->n = t - 1;

  // 將節點 y 的後 t -1 個關鍵字拷貝到 z 中
  for (int j = 0; j < t - 1; j++) z->keys[j] = y->keys[j + t];

  // 如果 y 不是葉子節點，拷貝 y 的後 t 個孩子節點到 z中
  if (y->leaf == false) {
    for (int j = 0; j < t; j++) z->C[j] = y->C[j + t];
  }

  // 將 y 所包含的關鍵字的個數設置為 t -1
  // 因為已滿則為2t -1 ，節點 z 中包含 t - 1 個
  // 一個關鍵字需要上移
  // 所以 y 中包含的關鍵字變為 2t-1 - (t-1) -1
  y->n = t - 1;

  // 給當前節點的指針分配新的空間，
  // 因為有新的關鍵字加入，父節點將多一個孩子。
  for (int j = n; j >= i + 1; j--) C[j + 1] = C[j];

  // 當前節點的下一個孩子設置為z
  C[i + 1] = z;

  // 將所有父節點中比上移的關鍵字大的關鍵字後移
  // 找到上移節點的關鍵字的位置
  for (int j = n - 1; j >= i; j--) keys[j + 1] = keys[j];

  // 拷貝 y 的中間關鍵字到其父節點中
  keys[i] = y->keys[t - 1];

  // 當前節點包含的關鍵字個數加 1
  n = n + 1;
}

刪除

B 樹的刪除操作相比於插入操作更為複雜，因為刪除之後經常需要重新排列節點。

與 B 樹的插入操作類似，必須確保刪除操作不違背 B 樹的特性。正如插入操作中每一個節點所包含的鍵的個數不能超過 \(2k-1\) 一樣，刪除操作要保證每一個節點包含的鍵的個數不少於 \(k-1\) 個（除根節點允許包含比 \(k-1\) 少的關鍵字的個數）。

有兩種常用的刪除策略：

  1. 定位並刪除元素，然後調整樹使它滿足約束條件。
  2. 從上到下處理這棵樹，在進入一個節點之前，調整樹使得之後一旦遇到了要刪除的鍵，它可以被直接刪除而不需要再進行調整。

下面介紹使用第一種策略的刪除。

首先，查找 B 樹中需刪除的元素，如果該元素在 B 樹中存在，則將該元素在其節點中進行刪除；刪除該元素後，首先判斷該元素是否有左右孩子節點， 如果有，則上移孩子節點中的某相近元素（「左孩子最右邊的節點」或「右孩子最左邊的節點」）到父節點中，然後是移動之後的情況；如果沒有，直接刪除。

  1. 某節點中元素數目小於 \(m/2-1\)，\(m/2\) 向上取整，則需要看其某相鄰兄弟節點是否豐滿。
  2. 如果豐滿（節點中元素個數大於 \(m/2-1\)），則向父節點借一個元素來滿足條件。
  3. 如果其相鄰兄弟都不豐滿，即其節點數目等於 \(m/2-1\)，則該節點與其相鄰的某一兄弟節點進行「合併」成一個節點。

接下來用一個 5 階 B 樹為例，詳細講解刪除的操作。

如圖所示，接下來要依次刪除 8，20，18，5。 首先要刪除元素 8。先查找到元素 8 在葉子節點中，刪除 8 後葉子節點的元素個數為 2，符合 B 樹的規則。然後需要把元素 11 和 12 都向前移動一位。完成後如圖所示。

下一步，刪除 20，因為 20 沒有在葉子節點中，而是在中間節點中找到，可以發現 20 的繼承者是 23（字母升序的下個元素），然後需要將 23 上移到 20 的位置，之後將孩子節點中的 23 進行刪除。 刪除後檢查一下，該孩子節點中元素個數大於 2，無需進行合併操作。

所以這一步之後，B 樹如下圖所示。

下一步刪除 18，18 在葉子節點中，但是該節點中元素數目為 2，刪除導致只有 1 個元素，已經小於最小元素數目 2。 而由前面已經知道：如果其某個相鄰兄弟節點中比較豐滿（元素個數大於 \(\lceil \dfrac{5}{2} \rceil\)），則可以向父節點借一個元素，然後將最豐滿的相鄰兄弟節點中上移最後或最前一個元素到父節點中。 在這個實例中，右相鄰兄弟節點中比較豐滿（3 個元素大於 2），所以先向父節點借一個元素 23 下移到該葉子節點中，代替原來 19 的位置。19 前移。 然後 24 在相鄰右兄弟節點中，需要上移到父節點中。最後在相鄰右兄弟節點中刪除 24，後面的元素前移。

這一步之後，B 樹如下圖所示。

最後一步需要刪除元素 5，但是刪除後會導致很多問題。因為 5 所在的節點數目剛好達標也就是剛好滿足最小元素個數 2。 而相鄰的兄弟節點也是同樣的情況，刪除一個元素都不能滿足條件，所以需要該節點與某相鄰兄弟節點進行合併操作；首先移動父節點中的元素（該元素在兩個需要合併的兩個節點元素之間）下移到其子節點中。 然後將這兩個節點進行合併成一個節點。所以在該實例中，首先將父節點中的元素 4 下移到已經刪除 5 而只有 6 的節點中，然後將含有 4 和 6 的節點和含有 1，3 的相鄰兄弟節點進行合併成一個節點。

這一步之後，B 樹如下圖所示。

但是這裏觀察到父節點只包含了一個元素 7，這就沒有達標（因為非根節點包括葉子節點的元素數量 \(K\) 必須滿足於 \(2<=K<=4\)，而此處的 \(K=1\)）。 如果這個問題節點的相鄰兄弟比較豐滿，則可以向父節點借一個元素。而此時兄弟節點元素剛好為 2，剛剛滿足，只能進行合併，而根節點中的唯一元素 13 下移到子節點。 這樣，樹的高度減少一層。

所以最終的效果如下圖。

刪除的偽代碼如下：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
B-Tree-Delete-Key(x, k) 
if not leaf[x] then 
    y ← Preceding-Child(x) 
    z ← Successor-Child(x) 
    if n[[y] > t − 1 then 
        k' ← Find-Predecessor-Key(k, x)]() 
        Move-Key(k', y, x) 
        Move-Key(k, x, z) 
        B-Tree-Delete-Key(k, z) 
    else if n[z] > t − 1 then 
        k' ← Find-Successor-Key(k, x) 
        Move-Key(k', z, x) 
        Move-Key(k, x, y) 
        B-Tree-Delete-Key(k, y) 
    else 
        Move-Key(k, x, y) 
        Merge-Nodes(y, z) 
        B-Tree-Delete-Key(k, y) 
    else (leaf node) 
    y ← Preceding-Child(x) 
    z ← Successor-Child(x) 
    w ← root(x) 
    v ← RootKey(x) 
        if n[x] > t − 1 then Remove-Key(k, x) 
        else if n[y] > t − 1 then 
            k' ← Find-Predecessor-Key(w, v) 
            Move-Key(k', y,w) 
            k' ← Find-Successor-Key(w, v) 
            Move-Key(k',w, x) 
            B-Tree-Delete-Key(k, x) 
        else if n[w] > t − 1 then 
            k' ← Find-Successor-Key(w, v) 
            Move-Key(k', z,w) 
            k' ← Find-Predecessor-Key(w, v) 
            Move-Key(k',w, x) 
            B-Tree-Delete-Key(k, x) 
        else 
            s ← Find-Sibling(w) 
            w' ← root(w) 
                if n[w'] = t − 1 then 
                    Merge-Nodes(w',w) 
                    Merge-Nodes(w, s) 
                    B-Tree-Delete-Key(k, x)
                else
                    Move-Key(v,w, x)
                    B-Tree-Delete-Key(k, x)

B 樹優勢

之前已經介紹過二叉查找樹。但是這類型數據結構的問題在於，由於每個節點只能容納一個數據，導致樹的高度很高，邏輯上挨着的節點數據可能離得很遠。

考慮在磁盤中存儲數據的情況，與內存相比，讀寫磁盤有以下不同點：

  1. 讀寫磁盤的速度相比內存讀寫慢很多。
  2. 每次讀寫磁盤的單位要比讀寫內存的最小單位大很多。

由於讀寫磁盤的這個特點，因此對應的數據結構應該儘量的滿足「局部性原理」：「當一個數據被用到時，其附近的數據也通常會馬上被使用」，為了滿足局部性原理， 所以應該將邏輯上相鄰的數據在物理上也儘量存儲在一起。這樣才能減少讀寫磁盤的數量。

所以，對比起一個節點只能存儲一個數據的 BST 類數據結構來，要求這種數據結構在形狀上更「胖」、更加「扁平」，即：每個節點能容納更多的數據， 這樣就能降低樹的高度，同時讓邏輯上相鄰的數據都能儘量存儲在物理上也相鄰的硬盤空間上，減少磁盤讀寫。

參考資料

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Persdre
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用