B+树

Table of content

B+树的基本操作
插入操作

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

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

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

B+树的特性

B+树中除根节点外的每个节点最多包含m个子节点和(m-1)个键，最少包含$\mathrm{\left \lceil \frac{m}{2}\right \rceil}$个子节点和$\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 - 如果叶子节点和内部节点都具有最大数量的键，则以类似的方式将它们都分割，并将右子节点中最小的键添加到父节点中。

示例

以下是各种编程语言中此操作的实现：

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("Insertion Done");
   printf("\nB+ tree:");
   traverse(r);
   return 0;
}

输出

Insertion Done
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<<"Insertion Done";
   cout<<"\nB+ tree:";
   traverse(r);
}

输出

Insertion Done
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 
      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.print("Insertion Done");
      System.out.println("\nB+ tree:");
      traverse(r);
   }
}

输出

Insertion Done
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):
    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("Insertion Done")
print("B+ tree:")
traverse(r)

输出

Insertion Done
B+ tree:
  10  20  30  40  50

打印页面