Cây B+ (B+ tree) là sự khái quát hóa của cây tìm kiếm nhị phân ở chỗ một nút có thể có hơn hai nút con. về cơ bản là một cấu trúc dữ liệu cây tự cân bằng (self-balancing) duy trì dữ liệu đã sắp xếp và cho phép truy cập tuần tự, tìm kiếm, chèn và xóa trong thời gian logarit.
Nó có thể được xem như một B-tree trong đó mỗi nút chỉ chứa khóa (keys) và một cấp độ bổ sung được thêm vào ở dưới cùng với các lá được liên kết.
Thuật toán
Bắt đầu
Hàm insert() để chèn nút vào cây:
Khởi tạo x là root.
Nếu x là lá và có chỗ cho thêm info thì chèn a vào x.
Ngược lại nếu x không phải lá, làm:
Tìm nút con của x sẽ được duyệt tiếp.
Nếu nút con không đầy, thay đổi x trỏ đến nút con đó.
Nếu nút con đầy, tách nó và thay đổi x trỏ đến một trong hai phần của nút con. Nếu a nhỏ hơn
khóa giữa trong nút con, đặt x là phần đầu của nút con. Ngược lại là phần thứ hai.
Kết thúc
Mã ví dụ
#include <iostream>
using namespace std;
struct BplusTree {
int *d;
BplusTree **child_ptr;
bool l;
int n;
}*r = NULL, *np = NULL, *x = NULL;
BplusTree* init() {
int i;
np = new BplusTree;
np->d = new int[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) {
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;
cout << "Nhập số phần tử cần chèn:\n";
cin >> n;
for(i = 0; i < n; i++) {
cout << "Nhập phần tử:\n";
cin >> t;
insert(t);
}
cout << "Duyệt cây B+ đã xây dựng:\n";
traverse(r);
return 0;
}
Kết quả đầu ra
Nhập số phần tử cần chèn: 10 Nhập phần tử: 10 Nhập phần tử: 20 Nhập phần tử: 30 Nhập phần tử: 40 Nhập phần tử: 50 Nhập phần tử: 60 Nhập phần tử: 70 Nhập phần tử: 80 Nhập phần tử: 90 Nhập phần tử: 100 Duyệt cây B+ đã xây dựng: 10 20 30 40 50 60 70 80 90 100