To understand the implementation of a B+ tree using C++
Objective
To understand the implementation of a B+ tree using C++
#include <bits/stdc++.h>
using namespace std;
struct BPTreeNode {
int *data;
BPTreeNode **child_ptr;
bool leaf;
int n;
}*root = NULL, *np = NULL, *x = NULL;
BPTreeNode* init() {
int i;
np = new BPTreeNode;
np->data = new int[5];
np->child_ptr = new BPTreeNode *[6];
np->leaf = true;
np->n = 0;
for (i = 0; i < 6; i++) {
np->child_ptr[i] = NULL;
}
return np;
}
void traverse(BPTreeNode *p) {
cout << endl;
int i;
for (i = 0; i < p->n; i++) {
if (p->leaf == false) {
traverse(p->child_ptr[i]);
}
cout << " " << p->data[i];
}
if (p->leaf == false) {
traverse(p->child_ptr[i]);
}
cout << endl;
}
void sort(int *p, int n) {
int i, j, temp;
for (i = 0; i < n; i++) {
for (j = i; j <= n; j++) {
if (p[i] > p[j]) {
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
}
}
}
int split_child(BPTreeNode *x, int i) {
int j, mid;
BPTreeNode *np1, *np3, *y;
np3 = init();
np3->leaf = true;
if (i == -1) {
mid = x->data[2];
x->data[2] = 0;
x->n--;
np1 = init();
np1->leaf = false;
x->leaf = true;
for (j = 3; j < 5; j++) {
np3->data[j - 3] = x->data[j];
np3->child_ptr[j - 3] = x->child_ptr[j];
np3->n++;
x->data[j] = 0;
x->n--;
}
for(j = 0; j < 6; j++) {
x->child_ptr[j] = NULL;
}
np1->data[0] = mid;
np1->child_ptr[np1->n] = x;
np1->child_ptr[np1->n + 1] = np3;
np1->n++;
root = np1;
} else {
y = x->child_ptr[i];
mid = y->data[2];
y->data[2] = 0;
y->n--;
for (j = 3; j < 5; j++) {
np3->data[j - 3] = y->data[j];
np3->n++;
y->data[j] = 0;
y->n--;
}
x->child_ptr[i] = y;
x->child_ptr[i + 1] = np3;
}
return mid;
}
void insert(int a) {
int i, temp;
x = root;
if (x == NULL) {
root = init();
x = root;
} else {
if (x->leaf == true && x->n == 5) {
temp = split_child(x, -1);
x = root;
for (i = 0; i < (x->n); i++) {
if ((a > x->data[i]) && (a < x->data[i + 1])) {
i++;
break;
} else if (a < x->data[0]) {
break;
} else {
continue;
}
}
x = x->child_ptr[i];
} else {
while (x->leaf == false) {
for (i = 0; i < (x->n); i++) {
if ((a > x->data[i]) && (a < x->data[i + 1])) {
i++;
break;
} else if (a < x->data[0]) {
break;
} else {
continue;
}
}
if ((x->child_ptr[i])->n == 5) {
temp = split_child(x, i);
x->data[x->n] = temp;
x->n++;
continue;
} else {
x = x->child_ptr[i];
}
}
}
}
x->data[x->n] = a;
sort(x->data, x->n);
x->n++;
}
int main() {
int i, n, t;
cout << "Enter the no of elements to be inserted ";
cin>>n;
for(i = 0; i < n; i++) {
cout << "Enter the element ";
cin>>t;
insert(t);
}
cout << "Traversal of constructed B+ tree is ";
traverse(root);
return 0;
}Discussion of Algorithm
- Start
-
Is the tree empty?
- Yes: create root node, insert key into root, go to End
- No: Proceed to the next step
-
Is the root full?
- Yes: split the root, create a new root, link the new root to the split parts, and proceed to Step 5
- No: Proceed to Step 5
- Find the appropriate child node to insert the key
- Is the child node full?
- Yes: split the child node, distribute the keys, repeat Step 5
- No: insert key into the child node
- End
Representations
Flow Diagram
+----------------------------------+
| |
| Start |
| | |
+----------------------------------+
|
V
+----------------------------------+
| |
| // Initialize root |
| *root = NULL |
| | |
+----------------------------------+
|
V
+----------------------------------+
| |
| Enter number of elements |
| to be inserted |
| cin>>n; |
| | |
+----------------------------------+
|
V
+----------------------------------+
| |
| for(i = 0; i < n; i++) { |
| cout << "Enter the element "; |
| cin>>t; |
| insert(t); |
| } |
| |
+----------------------------------+
|
V
+----------------------------------+
| |
| Print the traversal of the |
| constructed B+ tree through |
| traverse(root); |
| | |
+----------------------------------+
|
V
+----------------------------------+
| |
| Exit |
| | |
+----------------------------------+
Tabular Dry Run
| Action | Node Value | Operation | Output Tree |
|---|---|---|---|
| Insert | 10 | Tree is empty, insert 10 at root | 10 |
| Insert | 20 | Insert to the right of 10 | 10, 20 |
| Insert | 5 | 5 < 10, insert to the left of 10. Split root | 10 |
| Insert | 15 | 15 > 10 and 15 < 20, insert to the right of 10 | 10 |
| Insert | 30 | 30 > 20, insert to the right of 20 | 10 |
Output
Enter the no of elements to be inserted 5 Enter the element 10 20 5 15 30 Traversal of constructed B+ tree is 5 10 15 20 30