数据结构和算法 - B+ 树

B+树是B树的扩展，旨在使插入、删除和搜索操作更加高效。

B+树的性质与B树的性质类似，不同之处在于B树可以在所有内部节点和叶节点中存储键和记录，而B+树在叶节点中存储记录，在内部节点中存储键。B+树的一个重要特性是所有叶节点都以单链表格式相互连接，并且可以使用数据指针来指向磁盘文件中存在的数据。这有助于在相同数量的磁盘访问中获取记录。

由于主存的大小有限，B+树充当主存中无法存储的记录的数据存储。为此，内部节点存储在主存储器中，叶节点存储在辅助存储器中。

B+树的属性

B+ 树中的每个节点（根除外）最多包含m个子节点和 (m-1) 个键，并且最少包含 $\mathrm{\left \lceil \frac{m}{2}\right \rceil} $children 和 $\mathrm{\left \lceil \frac{m-1}{2}\right \rceil}$ 键，因为树的顺序是m。
根节点必须有不少于两个子节点和至少一个搜索键。
B树中的所有路径必须在同一层结束，即叶节点必须在同一层。
B+ 树始终维护排序的数据。

B+树的基本操作

B+树支持的操作有插入、删除和搜索，每个操作的时间复杂度为O(log n) 。

它们与 B 树操作几乎相似，因为在两种数据结构中存储数据的基本思想是相同的。然而，与 B 树不同的是，由于数据仅存储在 B+ 树的叶节点中，因此会出现差异。

插入

向 B+ 树的插入从叶节点开始。

步骤 1 - 计算要添加到 B+ 树节点上的键的最大和最小数量。

步骤 2 - 将元素逐一插入到叶节点中，直到超过最大键数。

步骤 3 - 节点被分成两半，其中左子节点由最少数量的键组成，其余的键存储在右子节点中。

步骤 4 - 但如果内部节点也超过了最大键属性，则该节点将被分成两半，其中左子节点由最小键组成，剩余的键存储在右子节点中。然而，右孩子中最小的数字成为父母。

步骤 5 - 如果叶节点和内部节点都有最大键，则以类似的方式分割它们，并将右子节点中的最小键添加到父节点。

删除

B+树中的删除操作，需要考虑数据结构中的冗余。

情况 1 - 如果密钥存在于具有超过最小数量的密钥的叶节点中，而其副本不存在于内部节点中，则只需将其删除。

情况 2 - 如果密钥存在于具有最少数量密钥的叶节点中，并且内部节点中不存在其副本，则从其兄弟节点借用密钥并删除所需的密钥。

情况 3 - 如果叶节点中存在的密钥在内部节点中有其副本，则有多种可能的情况 -

叶节点和内部节点中都存在超过最小的键：只需删除该键并将中序后继仅添加到内部节点。

叶节点中存在的键的精确最小数量：删除该节点并从其直接兄弟借用一个节点，并替换其在内部节点中的值。

如果要删除的叶子节点的副本在其祖父节点中，则删除该节点并删除空闲空间。祖父节点由已删除节点的中序后继节点填充。

情况 4 - 如果要删除的键位于违反最小键属性的节点中，则其父级和兄弟级都具有最小数量的键，则删除该键并将其兄弟级与其父级合并。

例子

C C++ Java Python

// C program for Bplus tree
#include <stdio.h>
#include <stdlib.h>
struct BplusTree {
   int *d;
   struct BplusTree **child_ptr;
   int l;
   int n;
};
struct BplusTree *r = NULL, *np = NULL, *x = NULL;
struct BplusTree* init() {
    //to create nodes
   int i;
   np = (struct BplusTree*)malloc(sizeof(struct BplusTree));
   np->d = (int*)malloc(6 * sizeof(int)); // order 6
   np->child_ptr = (struct BplusTree**)malloc(7 * sizeof(struct BplusTree*));
   np->l = 1;
   np->n = 0;
   for (i = 0; i < 7; i++) {
      np->child_ptr[i] = NULL;
   }
   return np;
}
void traverse(struct BplusTree *p) {
    //traverse tree
   printf("\n");
   int i;
   for (i = 0; i < p->n; i++) {
      if (p->l == 0) {
         traverse(p->child_ptr[i]);
      }
      printf(" %d", p->d[i]);
   }
   if (p->l == 0) {
      traverse(p->child_ptr[i]);
   }
   printf("\n");
}

void sort(int *p, int n) {
   int i, j, t;
   for (i = 0; i < n; i++) {
      for (j = i; j <= n; j++) {
         if (p[i] > p[j]) {
            t = p[i];
            p[i] = p[j];
            p[j] = t;
         }
      }
   }
}

int split_child(struct BplusTree *x, int i) {
   int j, mid;
   struct BplusTree *np1, *np3, *y;
   np3 = init();
   np3->l = 1;
   if (i == -1) {
      mid = x->d[2];
      x->d[2] = 0;
      x->n--;
      np1 = init();
      np1->l = 0;
      x->l = 1;
      for (j = 3; j < 6; j++) {
         np3->d[j - 3] = x->d[j];
         np3->child_ptr[j - 3] = x->child_ptr[j];
         np3->n++;
         x->d[j] = 0;
         x->n--;
      }
      for (j = 0; j < 6; j++) {
         x->child_ptr[j] = NULL;
      }
      np1->d[0] = mid;
      np1->child_ptr[np1->n] = x;
      np1->child_ptr[np1->n + 1] = np3;
      np1->n++;
      r = np1;
   } else {
      y = x->child_ptr[i];
      mid = y->d[2];
      y->d[2] = 0;
      y->n--;
      for (j = 3; j < 6; j++) {
         np3->d[j - 3] = y->d[j];
         np3->n++;
         y->d[j] = 0;
         y->n--;
      }
      x->child_ptr[i + 1] = y;
      x->child_ptr[i + 1] = np3;
   }
   return mid;
}

void insert(int a) {
   int i, t;
   x = r;
   if (x == NULL) {
      r = init();
      x = r;
   } else {
      if (x->l == 1 && x->n == 6) {
         t = split_child(x, -1);
         x = r;
         for (i = 0; i < x->n; i++) {
            if (a > x->d[i] && a < x->d[i + 1]) {
               i++;
               break;
            } else if (a < x->d[0]) {
               break;
            } else {
               continue;
            }
         }
         x = x->child_ptr[i];
      } else {
         while (x->l == 0) {
            for (i = 0; i < x->n; i++) {
               if (a > x->d[i] && a < x->d[i + 1]) {
                  i++;
                  break;
               } else if (a < x->d[0]) {
                  break;
               } else {
                  continue;
               }
            }
            if (x->child_ptr[i]->n == 6) {
               t = split_child(x, i);
               x->d[x->n] = t;
               x->n++;
               continue;
            } else {
               x = x->child_ptr[i];
            }
         }
      }
   }
   x->d[x->n] = a;
   sort(x->d, x->n);
   x->n++;
}

int main() {
   int i, n, t;
   insert(10);
   insert(20);
   insert(30);
   insert(40);
   insert(50);
   printf("B+ tree:\n");
   traverse(r);
   return 0;
}

输出

B+ tree:
10  20  30  40  50

#include<iostream>
using namespace std;
struct BplusTree {
   int *d;
   BplusTree **child_ptr;
   bool l;
   int n;
}
*r = NULL, *np = NULL, *x = NULL;
BplusTree* init() { //to create nodes 
   int i;
   np = new BplusTree;
   np->d = new int[6];//order 6
   np->child_ptr = new BplusTree *[7];
   np->l = true;
   np->n = 0;
   for (i = 0; i < 7; i++) {
      np->child_ptr[i] = NULL;
   }
   return np;
}

void traverse(BplusTree *p) { //traverse tree 
   cout<<endl;
   int i;
   for (i = 0; i < p->n; i++) {
      if (p->l == false) {
         traverse(p->child_ptr[i]);
      }
      cout << " " << p->d[i];
   }
   if (p->l == false) {
      traverse(p->child_ptr[i]);
   }
   cout<<endl;
}

void sort(int *p, int n) { //sort the tree 
   int i, j, t;
   for (i = 0; i < n; i++) {
      for (j = i; j <= n; j++) {
         if (p[i] >p[j]) {
            t = p[i];
            p[i] = p[j];
            p[j] = t;
         }
      }
   }
}

int split_child(BplusTree *x, int i) {
   int j, mid;
   BplusTree *np1, *np3, *y;
   np3 = init();
   np3->l = true;
   if (i == -1) {
      mid = x->d[2];
      x->d[2] = 0;
      x->n--;
      np1 = init();
      np1->l = false;
      x->l = true;
      for (j = 3; j < 6; j++) {
         np3->d[j - 3] = x->d[j];
         np3->child_ptr[j - 3] = x->child_ptr[j];
         np3->n++;
         x->d[j] = 0;
         x->n--;
      }
      for (j = 0; j < 6; j++) {
         x->child_ptr[j] = NULL;
      }
      np1->d[0] = mid;
      np1->child_ptr[np1->n] = x;
      np1->child_ptr[np1->n + 1] = np3;
      np1->n++;
      r = np1;
   } else {
      y = x->child_ptr[i];
      mid = y->d[2];
      y->d[2] = 0;
      y->n--;
      for (j = 3; j <6 ; j++) {
         np3->d[j - 3] = y->d[j];
         np3->n++;
         y->d[j] = 0;
         y->n--;
      }
      x->child_ptr[i + 1] = y;
      x->child_ptr[i + 1] = np3;
   }
   return mid;
}

void insert(int a) {
   int i, t;
   x = r;
   if (x == NULL) {
      r = init();
      x = r;
   } else {
      if (x->l== true && x->n == 6) {
         t = split_child(x, -1);
         x = r;
         for (i = 0; i < (x->n); i++) {
            if ((a >x->d[i]) && (a < x->d[i + 1])) {
            i++;
            break;
         } else if (a < x->d[0]) {
            break;
         } else {
            continue;
         }
      }
      x = x->child_ptr[i];
   } else {
      while (x->l == false) {
         for (i = 0; i < (x->n); i++) {
            if ((a >x->d[i]) && (a < x->d[i + 1])) {
               i++;
               break;
            } else if (a < x->d[0]) {
               break;
            } else {
               continue;
            }
         }
         if ((x->child_ptr[i])->n == 6) {
            t = split_child(x, i);
            x->d[x->n] = t;
            x->n++;
            continue;
         } else {
            x = x->child_ptr[i];
         }
      }
   }
}
   x->d[x->n] = a;
   sort(x->d, x->n);
   x->n++;
}

int main() {
   int i, n, t;
   insert(10);
   insert(20);
   insert(30);
   insert(40);
   insert(50);
   cout<<"B+ tree:\n";
   traverse(r);
}

输出

B+ tree:
10 20 30 40 50

//Java program for Bplus code
import java.util.*;
class BplusTree {
   int[] d;
   BplusTree[] child_ptr;
   boolean l;
   int n;
}
public class Main {
   static BplusTree r = null, np = null, x = null;
   static BplusTree init() { // to create nodes 
      int i;
      np = new BplusTree();
      np.d = new int[6]; // order 6
      np.child_ptr = new BplusTree[7];
      np.l = true;
      np.n = 0;
      for (i = 0; i < 7; i++) {
         np.child_ptr[i] = null;
      }
      return np;
   }
   static void traverse(BplusTree p) { // traverse tree 
      System.out.println();
      int i;
      for (i = 0; i < p.n; i++) {
         if (p.l == false) {
            traverse(p.child_ptr[i]);
         }
         System.out.print(" " + p.d[i]);
      }
      if (p.l == false) {
         traverse(p.child_ptr[i]);
      }
      System.out.println();
   }
   static void sort(int[] p, int n) { // sort the tree 
      int i, j, t;
      for (i = 0; i < n; i++) {
         for (j = i; j <= n; j++) {
            if (p[i] > p[j]) {
               t = p[i];
               p[i] = p[j];
               p[j] = t;
            }
         }
      }
   }
   static int split_child(BplusTree x, int i) {
      int j, mid;
      BplusTree np1, np3, y;
      np3 = init();
      np3.l = true;
      if (i == -1) {
         mid = x.d[2];
         x.d[2] = 0;
         x.n--;
         np1 = init();
         np1.l = false;
         x.l = true;
         for (j = 3; j < 6; j++) {
            np3.d[j - 3] = x.d[j];
            np3.child_ptr[j - 3] = x.child_ptr[j];
            np3.n++;
            x.d[j] = 0;
            x.n--;
         }
         for (j = 0; j < 6; j++) {
            x.child_ptr[j] = null;
         }
         np1.d[0] = mid;
         np1.child_ptr[np1.n] = x;
         np1.child_ptr[np1.n + 1] = np3;
         np1.n++;
         r = np1;
      } else {
         y = x.child_ptr[i];
         mid = y.d[2];
         y.d[2] = 0;
         y.n--;
         for (j = 3; j < 6; j++) {
            np3.d[j - 3] = y.d[j];
            np3.n++;
            y.d[j] = 0;
            y.n--;
         }
         x.child_ptr[i + 1] = y;
         x.child_ptr[i + 1] = np3;
      }
      return mid;
   }
   static void insert(int a) {
      int i, t;
      x = r;
      if (x == null) {
         r = init();
         x = r;
      } else {
         if (x.l == true && x.n == 6) {
            t = split_child(x, -1);
            x = r;
            for (i = 0; i < x.n; i++) {
               if (a > x.d[i] && a < x.d[i + 1]) {
                  i++;
                  break;
               } else if (a < x.d[0]) {
                  break;
               } else {
                  continue;
               }
            }
            x = x.child_ptr[i];
         } else {
            while (x.l == false) {
               for (i = 0; i < x.n; i++) {
                  if (a > x.d[i] && a < x.d[i + 1]) {
                     i++;
                     break;
                  } else if (a < x.d[0]) {
                     break;
                  } else {
                     continue;
                  }
               }
               if (x.child_ptr[i].n == 6) {
                  t = split_child(x, i);
                  x.d[x.n] = t;
                  x.n++;
                  continue;
               } else {
                  x = x.child_ptr[i];
               }
            }
         }
      }
      x.d[x.n] = a;
      sort(x.d, x.n);
      x.n++;
   }
   public static void main(String[] args) {
      int i, n, t;
      insert(10);
      insert(20);
      insert(30);
      insert(40);
      insert(50);
      System.out.println("B+ tree:");
      traverse(r);
   }
}

输出

B+ tree:
10  20  30  40  50

#Python Program for Bplus tree
#to create nodes
class BplusTree:
    def __init__(self):
        self.d = [0] * 6  # order 6
        self.child_ptr = [None] * 7
        self.l = True  
        self.n = 0
def init():
    np = BplusTree()
    np.l = True
    np.n = 0
    return np
#traverse tree
def traverse(p):
    print()
    for i in range(p.n):
        if not p.l:
            traverse(p.child_ptr[i])
        print(" ", p.d[i], end="")
    if not p.l:
        traverse(p.child_ptr[p.n])
    print()
#sort the tree
def sort(p, n):
    for i in range(n):
        for j in range(i, n + 1):
            if p[i] > p[j]:
                p[i], p[j] = p[j], p[i]
def split_child(x, i):
    np3 = init()
    np3.l = True
    if i == -1:
        mid = x.d[2]
        x.d[2] = 0
        x.n -= 1
        np1 = init()
        np1.l = False
        x.l = True
        for j in range(3, 6):
            np3.d[j - 3] = x.d[j]
            np3.child_ptr[j - 3] = x.child_ptr[j]
            np3.n += 1
            x.d[j] = 0
            x.n -= 1
        for j in range(6):
            x.child_ptr[j] = None
        np1.d[0] = mid
        np1.child_ptr[np1.n] = x
        np1.child_ptr[np1.n + 1] = np3
        np1.n += 1
        r = np1
    else:
        y = x.child_ptr[i]
        mid = y.d[2]
        y.d[2] = 0
        y.n -= 1
        for j in range(3, 6):
            np3.d[j - 3] = y.d[j]
            np3.n += 1
            y.d[j] = 0
            y.n -= 1
        x.child_ptr[i + 1] = y
        x.child_ptr[i + 1] = np3
    return mid
def insert(a):
    global r, x
    x = r
    if x is None:
        r = init()
        x = r
    else:
        if x.l and x.n == 6:
            t = split_child(x, -1)
            x = r
            for i in range(x.n):
                if a > x.d[i] and a < x.d[i + 1]:
                    i += 1
                    break
                elif a < x.d[0]:
                    break
                else:
                    continue
            x = x.child_ptr[i]
        else:
            while not x.l:
                for i in range(x.n):
                    if a > x.d[i] and a < x.d[i + 1]:
                        i += 1
                        break
                    elif a < x.d[0]:
                        break
                    else:
                        continue
                if x.child_ptr[i].n == 6:
                    t = split_child(x, i)
                    x.d[x.n] = t
                    x.n += 1
                    continue
                else:
                    x = x.child_ptr[i]
    x.d[x.n] = a
    sort(x.d, x.n)
    x.n += 1
r = None
x = None
insert(10)
insert(20)
insert(30)
insert(40)
insert(50)
print("B+ tree:")
traverse(r)

输出

B+ tree:
10 20 30 40 50