B+ 樹

引入

B+ 樹是 B 樹 的一個升級，它比 B 樹更適合實際應用中操作系統的文件索引和數據庫索引。目前現代關係型數據庫最廣泛的支持索引結構就是 B+ 樹。

B+ 樹是一種多叉排序樹，即每個節點通常有多個孩子。一棵 B+ 樹包含根節點、內部節點和葉子節點。根節點可能是一個葉子節點，也可能是一個包含兩個或兩個以上孩子節點的節點。

B+ 樹的特點是能夠保持數據穩定有序，其插入與修改擁有較穩定的對數時間複雜度。B+ 樹元素自底向上插入，這與二叉樹恰好相反。

首先介紹一棵 \(m\) 階 B+ 樹的特性。\(m\) 表示這個樹的每一個節點最多可以擁有的子節點個數。一棵 \(m\) 階的 B+ 樹和 B 樹的差異在於：

1. 有 \(n\) 棵子樹的節點中含有 \(n-1\) 個關鍵字（即將區間分為 \(n\) 個子區間，每個子區間對應一棵子樹）。
2. 所有葉子節點中包含了全部關鍵字的信息，及指向含這些關鍵字記錄的指針，且葉子節點本身依關鍵字的大小自小而大順序鏈接。
3. 所有的非葉子節點可以看成是索引部分，節點中僅含有其子樹（根節點）中的最大（或最小）關鍵字。
4. 除根節點外，其他所有節點中所含關鍵字的個數最少有 \(\lceil \dfrac{m}{2} \rceil\)（注意：B 樹中除根以外的所有非葉子節點至少有 \(\lceil \dfrac{m}{2} \rceil\) 棵子樹）。

同時，B+ 樹為了方便範圍查詢，葉子節點之間還用指針串聯起來。

以下是一棵 B+ 樹的典型結構：

B+ 樹相比於 B 樹的優勢

由於索引節點上只有索引而沒有數據，所以索引節點上能存儲比 B 樹更多的索引，這樣樹的高度就會更矮。樹的高度越矮，磁盤尋道的次數就會越少。

因為數據都集中在葉子節點，而所有葉子節點的高度相同，那麼可以在葉子節點中增加前後指針，指向同一個父節點的相鄰兄弟節點，這樣可以更好地支持查詢一個值的前驅或後繼，使連續訪問更容易實現。

比如這樣的 SQL 語句：select * from tbl where t > 10，如果使用 B+ 樹存儲數據的話，可以首先定位到數據為 10 的節點，再沿着它的 next 指針一路找到所有在該葉子節點右邊的葉子節點，返回這些節點包含的數據。

而如果使用 B 樹結構，由於數據既可以存儲在內部節點也可以存儲在葉子節點，連續訪問的實現會更加繁瑣（需要在樹的內部結構中進行移動）。

過程

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

查找

B+ 樹的查找過程和 B 樹類似。假設需要查找的鍵值是 \(k\)，那麼從根節點開始，從上到下遞歸地遍歷樹。在每一層上，搜索的範圍被減小到包含搜索值的子樹中。

一個實例：在如下這棵 B+ 樹上查找 45。

先和根節點比較

因為根節點的鍵值比 45 要小，所以去往根節點的右子樹查找

因為 45 比 35 大，所以要與右邊的索引相比

右側的索引也為 45，所以要去往該節點的右子樹繼續查找

然後就可以找到 45

需要注意的是，在查找時，若非葉子節點上的關鍵字等於給定值，並不終止，而是繼續向下直到葉子節點。因此，在 B+ 樹中，不管查找成功與否，每次查找都是走了一條從根到葉子節點的路徑。其餘同 B 樹的查找類似。

查找一個鍵的代碼如下：

實現

T find(V key) {
  int i = 0;
  while (i < this.number) {
    if (key.compareTo((V)this.keys[i]) <= 0) break;
    i++;
  }
  if (this.number == i) return null;
  return this.childs[i].find(key);
}

遍歷

B+ 樹只在葉子節點的層級上就可以實現整棵樹的遍歷。從根節點出發一路搜索到最左端的葉子節點之後即可根據指針遍歷。

插入

B+ 樹的插入算法與 B 樹的相近：

1. 若為空樹，創建一個葉子節點，然後將記錄插入其中，此時這個葉子節點也是根節點，插入操作結束。
2. 針對葉子類型節點：根據關鍵字找到葉子節點，向這個葉子節點插入記錄。插入後，若當前節點關鍵字的個數小於 \(m\)，則插入結束。否則將這個葉子節點分裂成左右兩個葉子節點，左葉子節點包含前 \(m/2\) 個記錄，右節點包含剩下的記錄，將第 \(m/2+1\) 個記錄的關鍵字進位到父節點中（父節點一定是索引類型節點），進位到父節點的關鍵字左孩子指針向左節點，右孩子指針向右節點。將當前節點的指針指向父節點，然後執行第 3 步。
3. 針對索引類型節點（內部節點）：若當前節點關鍵字的個數小於等於 \(m-1\)，則插入結束。否則，將這個索引類型節點分裂成兩個索引節點，左索引節點包含前 \((m-1)/2\) 個 key，右節點包含 \(m-(m-1)/2\) 個 key，將第 \(m/2\) 個關鍵字進位到父節點中，進位到父節點的關鍵字左孩子指向左節點，進位到父節點的關鍵字右孩子指向右節點。將當前節點的指針指向父節點，然後重複這一步。

比如在下圖的 B+ 樹中，插入新的數據 10：

由於插入節點 \([7,11]\) 在插入之後並沒有溢出，所以可以直接變成 \([7,10,11]\)。

而如下圖的 B+ 樹中，插入數據 4：

由於所在節點 \([2,3,5]\) 在插入之後數據溢出，因此需要分裂為兩個新的節點，同時調整父節點的索引數據：

\([2,3,4,5]\) 分裂成了 \([2,3]\) 和 \([4,5]\)，因此需要在這兩個節點之間新增一個索引值，這個值應該滿足：

1. 大於左子樹的最大值；
2. 小於等於右子樹的最小值。

綜上，需要在父節點中新增索引 4 和兩個指向新節點的指針。

更多的例子可以參考演示網站 BPlustree

插入一個鍵的代碼如下：

實現

void BPTree::insert(int x) {
  if (root == NULL) {
    root = new Node;
    root->key[0] = x;
    root->IS_LEAF = true;
    root->size = 1;
    root->parent = NULL;
  } else {
    Node* cursor = root;
    Node* parent;

    while (cursor->IS_LEAF == false) {
      parent = cursor;
      for (int i = 0; i < cursor->size; i++) {
        if (x < cursor->key[i]) {
          cursor = cursor->ptr[i];
          break;
        }

        if (i == cursor->size - 1) {
          cursor = cursor->ptr[i + 1];
          break;
        }
      }
    }
    if (cursor->size < MAX) {
      insertVal(x, cursor);
      cursor->parent = parent;
      cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];
      cursor->ptr[cursor->size - 1] = NULL;
    } else
      split(x, parent, cursor);
  }
}

void BPTree::split(int x, Node* parent, Node* cursor) {
  Node* LLeaf = new Node;
  Node* RLeaf = new Node;
  insertVal(x, cursor);
  LLeaf->IS_LEAF = RLeaf->IS_LEAF = true;
  LLeaf->size = (MAX + 1) / 2;
  RLeaf->size = (MAX + 1) - (MAX + 1) / 2;
  for (int i = 0; i < MAX + 1; i++) LLeaf->ptr[i] = cursor->ptr[i];
  LLeaf->ptr[LLeaf->size] = RLeaf;
  RLeaf->ptr[RLeaf->size] = LLeaf->ptr[MAX];
  LLeaf->ptr[MAX] = NULL;
  for (int i = 0; i < LLeaf->size; i++) {
    LLeaf->key[i] = cursor->key[i];
  }
  for (int i = 0, j = LLeaf->size; i < RLeaf->size; i++, j++) {
    RLeaf->key[i] = cursor->key[j];
  }
  if (cursor == root) {
    Node* newRoot = new Node;
    newRoot->key[0] = RLeaf->key[0];
    newRoot->ptr[0] = LLeaf;
    newRoot->ptr[1] = RLeaf;
    newRoot->IS_LEAF = false;
    newRoot->size = 1;
    root = newRoot;
    LLeaf->parent = RLeaf->parent = newRoot;
  } else {
    insertInternal(RLeaf->key[0], parent, LLeaf, RLeaf);
  }
}

void BPTree::insertInternal(int x, Node* cursor, Node* LLeaf, Node* RRLeaf) {
  if (cursor->size < MAX) {
    auto i = insertVal(x, cursor);
    for (int j = cursor->size; j > i + 1; j--) {
      cursor->ptr[j] = cursor->ptr[j - 1];
    }
    cursor->ptr[i] = LLeaf;
    cursor->ptr[i + 1] = RRLeaf;
  }

  else {
    Node* newLchild = new Node;
    Node* newRchild = new Node;
    Node* virtualPtr[MAX + 2];
    for (int i = 0; i < MAX + 1; i++) {
      virtualPtr[i] = cursor->ptr[i];
    }
    int i = insertVal(x, cursor);
    for (int j = MAX + 2; j > i + 1; j--) {
      virtualPtr[j] = virtualPtr[j - 1];
    }
    virtualPtr[i] = LLeaf;
    virtualPtr[i + 1] = RRLeaf;
    newLchild->IS_LEAF = newRchild->IS_LEAF = false;
    // 這裏和葉子節點有區別
    newLchild->size = (MAX + 1) / 2;
    newRchild->size = MAX - (MAX + 1) / 2;
    for (int i = 0; i < newLchild->size; i++) {
      newLchild->key[i] = cursor->key[i];
    }
    for (int i = 0, j = newLchild->size + 1; i < newRchild->size; i++, j++) {
      newRchild->key[i] = cursor->key[j];
    }
    for (int i = 0; i < LLeaf->size + 1; i++) {
      newLchild->ptr[i] = virtualPtr[i];
    }
    for (int i = 0, j = LLeaf->size + 1; i < RRLeaf->size + 1; i++, j++) {
      newRchild->ptr[i] = virtualPtr[j];
    }
    if (cursor == root) {
      Node* newRoot = new Node;
      newRoot->key[0] = cursor->key[newLchild->size];
      newRoot->ptr[0] = newLchild;
      newRoot->ptr[1] = newRchild;
      newRoot->IS_LEAF = false;
      newRoot->size = 1;
      root = newRoot;
      newLchild->parent = newRchild->parent = newRoot;
    } else {
      insertInternal(cursor->key[newLchild->size], cursor->parent, newLchild,
                     newRchild);
    }
  }
}

刪除

B+ 樹的刪除也僅在葉子節點中進行，當葉子節點中的最大關鍵字被刪除時，其在非葉子節點中的值可以作為一個分界關鍵字存在。若因刪除而使節點中關鍵字的個數少於 \(\lceil \dfrac{m}{2} \rceil\) 時，其和兄弟節點的合併過程亦和 B 樹類似。

具體步驟如下：

1. 首先查詢到鍵值所在的葉子節點，刪除該葉子節點的數據。
2. 如果刪除葉子節點之後的數據數量，滿足 B+ 樹的平衡條件，則直接返回。
3. 否則，就需要做平衡操作：如果該葉子節點的左右兄弟節點的數據量可以借用，就借用過來滿足平衡條件。否則，就與相鄰的兄弟節點合併成一個新的子節點了。

在上面平衡操作中，如果是進行了合併操作，就需要向上修正父節點的指針：刪除被合併節點的鍵值以及指針。

由於做了刪除操作，可能父節點也會不平衡，那麼就按照前面的步驟也對父節點進行重新平衡操作，這樣一直到某個節點平衡為止。

可以參考 B 樹 中的刪除章節。

實現

// Deletion operation on a B+ tree in C++
#include <climits>
#include <fstream>
#include <iostream>
#include <sstream>
using namespace std;
int MAX = 3;

class BPTree;

class Node {
  bool IS_LEAF;
  int *key, size;
  Node **ptr;
  friend class BPTree;

 public:
  Node();
};

class BPTree {
  Node *root;
  void insertInternal(int, Node *, Node *);
  void removeInternal(int, Node *, Node *);
  Node *findParent(Node *, Node *);

 public:
  BPTree();
  void search(int);
  void insert(int);
  void remove(int);
  void display(Node *);
  Node *getRoot();
};

Node::Node() {
  key = new int[MAX];
  ptr = new Node *[MAX + 1];
}

BPTree::BPTree() { root = NULL; }

void BPTree::insert(int x) {
  if (root == NULL) {
    root = new Node;
    root->key[0] = x;
    root->IS_LEAF = true;
    root->size = 1;
  } else {
    Node *cursor = root;
    Node *parent;
    while (cursor->IS_LEAF == false) {
      parent = cursor;
      for (int i = 0; i < cursor->size; i++) {
        if (x < cursor->key[i]) {
          cursor = cursor->ptr[i];
          break;
        }
        if (i == cursor->size - 1) {
          cursor = cursor->ptr[i + 1];
          break;
        }
      }
    }
    if (cursor->size < MAX) {
      int i = 0;
      while (x > cursor->key[i] && i < cursor->size) i++;
      for (int j = cursor->size; j > i; j--) {
        cursor->key[j] = cursor->key[j - 1];
      }
      cursor->key[i] = x;
      cursor->size++;
      cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];
      cursor->ptr[cursor->size - 1] = NULL;
    } else {
      Node *newLeaf = new Node;
      int virtualNode[MAX + 1];
      for (int i = 0; i < MAX; i++) {
        virtualNode[i] = cursor->key[i];
      }
      int i = 0, j;
      while (x > virtualNode[i] && i < MAX) i++;
      for (int j = MAX + 1; j > i; j--) {
        virtualNode[j] = virtualNode[j - 1];
      }
      virtualNode[i] = x;
      newLeaf->IS_LEAF = true;
      cursor->size = (MAX + 1) / 2;
      newLeaf->size = MAX + 1 - (MAX + 1) / 2;
      cursor->ptr[cursor->size] = newLeaf;
      newLeaf->ptr[newLeaf->size] = cursor->ptr[MAX];
      cursor->ptr[MAX] = NULL;
      for (i = 0; i < cursor->size; i++) {
        cursor->key[i] = virtualNode[i];
      }
      for (i = 0, j = cursor->size; i < newLeaf->size; i++, j++) {
        newLeaf->key[i] = virtualNode[j];
      }
      if (cursor == root) {
        Node *newRoot = new Node;
        newRoot->key[0] = newLeaf->key[0];
        newRoot->ptr[0] = cursor;
        newRoot->ptr[1] = newLeaf;
        newRoot->IS_LEAF = false;
        newRoot->size = 1;
        root = newRoot;
      } else {
        insertInternal(newLeaf->key[0], parent, newLeaf);
      }
    }
  }
}

void BPTree::insertInternal(int x, Node *cursor, Node *child) {
  if (cursor->size < MAX) {
    int i = 0;
    while (x > cursor->key[i] && i < cursor->size) i++;
    for (int j = cursor->size; j > i; j--) {
      cursor->key[j] = cursor->key[j - 1];
    }
    for (int j = cursor->size + 1; j > i + 1; j--) {
      cursor->ptr[j] = cursor->ptr[j - 1];
    }
    cursor->key[i] = x;
    cursor->size++;
    cursor->ptr[i + 1] = child;
  } else {
    Node *newInternal = new Node;
    int virtualKey[MAX + 1];
    Node *virtualPtr[MAX + 2];
    for (int i = 0; i < MAX; i++) {
      virtualKey[i] = cursor->key[i];
    }
    for (int i = 0; i < MAX + 1; i++) {
      virtualPtr[i] = cursor->ptr[i];
    }
    int i = 0, j;
    while (x > virtualKey[i] && i < MAX) i++;
    for (int j = MAX + 1; j > i; j--) {
      virtualKey[j] = virtualKey[j - 1];
    }
    virtualKey[i] = x;
    for (int j = MAX + 2; j > i + 1; j--) {
      virtualPtr[j] = virtualPtr[j - 1];
    }
    virtualPtr[i + 1] = child;
    newInternal->IS_LEAF = false;
    cursor->size = (MAX + 1) / 2;
    newInternal->size = MAX - (MAX + 1) / 2;
    for (i = 0, j = cursor->size + 1; i < newInternal->size; i++, j++) {
      newInternal->key[i] = virtualKey[j];
    }
    for (i = 0, j = cursor->size + 1; i < newInternal->size + 1; i++, j++) {
      newInternal->ptr[i] = virtualPtr[j];
    }
    if (cursor == root) {
      Node *newRoot = new Node;
      newRoot->key[0] = cursor->key[cursor->size];
      newRoot->ptr[0] = cursor;
      newRoot->ptr[1] = newInternal;
      newRoot->IS_LEAF = false;
      newRoot->size = 1;
      root = newRoot;
    } else {
      insertInternal(cursor->key[cursor->size], findParent(root, cursor),
                     newInternal);
    }
  }
}

Node *BPTree::findParent(Node *cursor, Node *child) {
  Node *parent;
  if (cursor->IS_LEAF || (cursor->ptr[0])->IS_LEAF) {
    return NULL;
  }
  for (int i = 0; i < cursor->size + 1; i++) {
    if (cursor->ptr[i] == child) {
      parent = cursor;
      return parent;
    } else {
      parent = findParent(cursor->ptr[i], child);
      if (parent != NULL) return parent;
    }
  }
  return parent;
}

void BPTree::remove(int x) {
  if (root == NULL) {
    cout << "Tree empty\n";
  } else {
    Node *cursor = root;
    Node *parent;
    int leftSibling, rightSibling;
    while (cursor->IS_LEAF == false) {
      for (int i = 0; i < cursor->size; i++) {
        parent = cursor;
        leftSibling = i - 1;
        rightSibling = i + 1;
        if (x < cursor->key[i]) {
          cursor = cursor->ptr[i];
          break;
        }
        if (i == cursor->size - 1) {
          leftSibling = i;
          rightSibling = i + 2;
          cursor = cursor->ptr[i + 1];
          break;
        }
      }
    }
    bool found = false;
    int pos;
    for (pos = 0; pos < cursor->size; pos++) {
      if (cursor->key[pos] == x) {
        found = true;
        break;
      }
    }
    if (!found) {
      cout << "Not found\n";
      return;
    }
    for (int i = pos; i < cursor->size; i++) {
      cursor->key[i] = cursor->key[i + 1];
    }
    cursor->size--;
    if (cursor == root) {
      for (int i = 0; i < MAX + 1; i++) {
        cursor->ptr[i] = NULL;
      }
      if (cursor->size == 0) {
        cout << "Tree died\n";
        delete[] cursor->key;
        delete[] cursor->ptr;
        delete cursor;
        root = NULL;
      }
      return;
    }
    cursor->ptr[cursor->size] = cursor->ptr[cursor->size + 1];
    cursor->ptr[cursor->size + 1] = NULL;
    if (cursor->size >= (MAX + 1) / 2) {
      return;
    }
    if (leftSibling >= 0) {
      Node *leftNode = parent->ptr[leftSibling];
      if (leftNode->size >= (MAX + 1) / 2 + 1) {
        for (int i = cursor->size; i > 0; i--) {
          cursor->key[i] = cursor->key[i - 1];
        }
        cursor->size++;
        cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];
        cursor->ptr[cursor->size - 1] = NULL;
        cursor->key[0] = leftNode->key[leftNode->size - 1];
        leftNode->size--;
        leftNode->ptr[leftNode->size] = cursor;
        leftNode->ptr[leftNode->size + 1] = NULL;
        parent->key[leftSibling] = cursor->key[0];
        return;
      }
    }
    if (rightSibling <= parent->size) {
      Node *rightNode = parent->ptr[rightSibling];
      if (rightNode->size >= (MAX + 1) / 2 + 1) {
        cursor->size++;
        cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];
        cursor->ptr[cursor->size - 1] = NULL;
        cursor->key[cursor->size - 1] = rightNode->key[0];
        rightNode->size--;
        rightNode->ptr[rightNode->size] = rightNode->ptr[rightNode->size + 1];
        rightNode->ptr[rightNode->size + 1] = NULL;
        for (int i = 0; i < rightNode->size; i++) {
          rightNode->key[i] = rightNode->key[i + 1];
        }
        parent->key[rightSibling - 1] = rightNode->key[0];
        return;
      }
    }
    if (leftSibling >= 0) {
      Node *leftNode = parent->ptr[leftSibling];
      for (int i = leftNode->size, j = 0; j < cursor->size; i++, j++) {
        leftNode->key[i] = cursor->key[j];
      }
      leftNode->ptr[leftNode->size] = NULL;
      leftNode->size += cursor->size;
      leftNode->ptr[leftNode->size] = cursor->ptr[cursor->size];
      removeInternal(parent->key[leftSibling], parent, cursor);
      delete[] cursor->key;
      delete[] cursor->ptr;
      delete cursor;
    } else if (rightSibling <= parent->size) {
      Node *rightNode = parent->ptr[rightSibling];
      for (int i = cursor->size, j = 0; j < rightNode->size; i++, j++) {
        cursor->key[i] = rightNode->key[j];
      }
      cursor->ptr[cursor->size] = NULL;
      cursor->size += rightNode->size;
      cursor->ptr[cursor->size] = rightNode->ptr[rightNode->size];
      cout << "Merging two leaf nodes\n";
      removeInternal(parent->key[rightSibling - 1], parent, rightNode);
      delete[] rightNode->key;
      delete[] rightNode->ptr;
      delete rightNode;
    }
  }
}

void BPTree::removeInternal(int x, Node *cursor, Node *child) {
  if (cursor == root) {
    if (cursor->size == 1) {
      if (cursor->ptr[1] == child) {
        delete[] child->key;
        delete[] child->ptr;
        delete child;
        root = cursor->ptr[0];
        delete[] cursor->key;
        delete[] cursor->ptr;
        delete cursor;
        cout << "Changed root node\n";
        return;
      } else if (cursor->ptr[0] == child) {
        delete[] child->key;
        delete[] child->ptr;
        delete child;
        root = cursor->ptr[1];
        delete[] cursor->key;
        delete[] cursor->ptr;
        delete cursor;
        cout << "Changed root node\n";
        return;
      }
    }
  }
  int pos;
  for (pos = 0; pos < cursor->size; pos++) {
    if (cursor->key[pos] == x) {
      break;
    }
  }
  for (int i = pos; i < cursor->size; i++) {
    cursor->key[i] = cursor->key[i + 1];
  }
  for (pos = 0; pos < cursor->size + 1; pos++) {
    if (cursor->ptr[pos] == child) {
      break;
    }
  }
  for (int i = pos; i < cursor->size + 1; i++) {
    cursor->ptr[i] = cursor->ptr[i + 1];
  }
  cursor->size--;
  if (cursor->size >= (MAX + 1) / 2 - 1) {
    return;
  }
  if (cursor == root) return;
  Node *parent = findParent(root, cursor);
  int leftSibling, rightSibling;
  for (pos = 0; pos < parent->size + 1; pos++) {
    if (parent->ptr[pos] == cursor) {
      leftSibling = pos - 1;
      rightSibling = pos + 1;
      break;
    }
  }
  if (leftSibling >= 0) {
    Node *leftNode = parent->ptr[leftSibling];
    if (leftNode->size >= (MAX + 1) / 2) {
      for (int i = cursor->size; i > 0; i--) {
        cursor->key[i] = cursor->key[i - 1];
      }
      cursor->key[0] = parent->key[leftSibling];
      parent->key[leftSibling] = leftNode->key[leftNode->size - 1];
      for (int i = cursor->size + 1; i > 0; i--) {
        cursor->ptr[i] = cursor->ptr[i - 1];
      }
      cursor->ptr[0] = leftNode->ptr[leftNode->size];
      cursor->size++;
      leftNode->size--;
      return;
    }
  }
  if (rightSibling <= parent->size) {
    Node *rightNode = parent->ptr[rightSibling];
    if (rightNode->size >= (MAX + 1) / 2) {
      cursor->key[cursor->size] = parent->key[pos];
      parent->key[pos] = rightNode->key[0];
      for (int i = 0; i < rightNode->size - 1; i++) {
        rightNode->key[i] = rightNode->key[i + 1];
      }
      cursor->ptr[cursor->size + 1] = rightNode->ptr[0];
      for (int i = 0; i < rightNode->size; ++i) {
        rightNode->ptr[i] = rightNode->ptr[i + 1];
      }
      cursor->size++;
      rightNode->size--;
      return;
    }
  }
  if (leftSibling >= 0) {
    Node *leftNode = parent->ptr[leftSibling];
    leftNode->key[leftNode->size] = parent->key[leftSibling];
    for (int i = leftNode->size + 1, j = 0; j < cursor->size; j++) {
      leftNode->key[i] = cursor->key[j];
    }
    for (int i = leftNode->size + 1, j = 0; j < cursor->size + 1; j++) {
      leftNode->ptr[i] = cursor->ptr[j];
      cursor->ptr[j] = NULL;
    }
    leftNode->size += cursor->size + 1;
    cursor->size = 0;
    removeInternal(parent->key[leftSibling], parent, cursor);
  } else if (rightSibling <= parent->size) {
    Node *rightNode = parent->ptr[rightSibling];
    cursor->key[cursor->size] = parent->key[rightSibling - 1];
    for (int i = cursor->size + 1, j = 0; j < rightNode->size; j++) {
      cursor->key[i] = rightNode->key[j];
    }
    for (int i = cursor->size + 1, j = 0; j < rightNode->size + 1; j++) {
      cursor->ptr[i] = rightNode->ptr[j];
      rightNode->ptr[j] = NULL;
    }
    cursor->size += rightNode->size + 1;
    rightNode->size = 0;
    removeInternal(parent->key[rightSibling - 1], parent, rightNode);
  }
}

void BPTree::display(Node *cursor) {
  if (cursor != NULL) {
    for (int i = 0; i < cursor->size; i++) {
      cout << cursor->key[i] << " ";
    }
    cout << "\n";
    if (cursor->IS_LEAF != true) {
      for (int i = 0; i < cursor->size + 1; i++) {
        display(cursor->ptr[i]);
      }
    }
  }
}

Node *BPTree::getRoot() { return root; }

int main() {
  BPTree node;
  node.insert(5);
  node.insert(15);
  node.insert(25);
  node.insert(35);
  node.insert(45);

  node.display(node.getRoot());

  node.remove(15);

  node.display(node.getRoot());
}

參考資料

• B+ tree wikipedia
• B 樹、B+ 樹索引算法原理（下）
• B+ 樹詳解 + 代碼實現（插入篇）
• Deletion from a B+ Tree

---

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