B+ 树
B+ 树是 B 树的扩展，旨在提高插入、删除和查找操作的效率。
B+ 树的性质与 B 树相似，不同之处在于，B 树可以在所有内部节点和叶节点中存储键和记录，而 B+ 树在叶节点中存储记录，在内部节点中存储键。B+ 树的一个重要特性是，所有叶节点都以单链表格式相互连接，并且有一个数据指针指向磁盘文件中的数据。这有助于以相同的磁盘访问次数获取记录。
由于主内存的大小有限，B+ 树充当了无法存储在主内存中的记录的数据存储。为此，内部节点存储在主存储器中，叶节点存储在辅助存储器中。
B+ 树的属性
B+ 树中的每个节点（根节点除外）最多可容纳 m 个子节点和 (m-1) 个键，并且至少可容纳 $\mathrm{\left \lceil \frac{m}{2} ight ceil}$ 个子节点和 $\mathrm{\left \lceil \frac{m-1}{2} ight ceil}$ 个键，因为树的阶数为 m。
根节点必须具有不少于两个子节点和至少一个搜索键。
B 树中的所有路径必须以同一级别结束，即叶节点必须位于同一级别。
B+ 树始终维护排序后的数据。
B+ 树的基本操作
B+ 树支持的操作包括插入、删除和查找，每个操作的时间复杂度为 O(log n)。
它们与 B 树的操作几乎相似，因为在这两种数据结构中存储数据的基本思想是相同的。然而，与 B 树不同，B+ 树的数据仅存储在叶子节点中，因此存在差异。
插入操作
B+ 树的插入操作从叶子节点开始。
步骤 1 − 计算要添加到 B+ 树节点的最大和最小键数。
步骤 2 − 将元素逐个相应地插入到叶子节点中，直到超过最大键数。
步骤 3 −将节点一分为二，左子节点包含最少数量的键，其余键存储在右子节点中。
步骤 4 − 但如果内部节点也超过了最大键属性，则将节点一分为二，左子节点包含最少数量的键，其余键存储在右子节点中。但是，右子节点中键数最少的将作为父节点。
步骤 5 −如果叶节点和内部节点都包含最大键，则以类似的方式拆分它们，并将右侧子节点中最小的键添加到父节点。
示例
以下是此操作在各种编程语言中的实现 −
// Bplus 树的 C 程序
#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) {
//遍历树
printf("
");
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("
");
}
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("
B+ 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) { //遍历树
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<<"
B+ tree:";
traverse(r);
}
输出
Insertion Done B+ tree: 10 20 30 40 50
//Bplus代码的Java程序
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("
B+ 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
