Introduction to B+ Tree in DBMS
B+ tree in DBMS, i.e., database management systems are primarily used in place of B tree in multilevel dynamic indexing. The most useful feature of the B+ tree is that only the nodes of the tree store the data pointers to the file system, while that in B- trees, the data pointers are present at each of the nodes along with the key value of the node. This greatly increases the efficiency in accessing the values inside the search tree and makes them work faster. Also, the use of a B+ tree decreases the number of levels the tree requires to store the data compared to levels required to store the B-tree. In this article, we will study the working of the B+ tree and its structure and learn about its implementation with the help of an example.
Structure of B+ Tree in DBMS
The B+ tree is actually considered the balanced binary search tree, which can be used for multilevel indexing. It is made sure that all the leaf nodes of the B+ tree are kept at the same height. The leaf node denotes the actual data pointer. All the leaf nodes are linked to each other by using the link list. The distance between the root node and the leaf nodes is exactly the same for all the nodes at the leaf. Each B+ tree has the order n, which is a fixed number. The nodes are segregated into two parts, one for the internal nodes and the other for the root nodes.
1. Internal Node: It can contain at least n/2 data pointers that do not include the root node. An internal node will contain at maximum n pointers in the B+ tree.
2. Leaf node: The leaf node can have a minimum of n/2 data pointers and a maximum of n key values and data pointers. Each leaf node has a pointer of one block type, and it points to the next leaf node of the B+ tree. The following diagram represents a structure of the B+ tree –
Working of B+ Tree in DBMS
In the B+ tree, while searching for a particular record, an intermediary node is retrieved first, which will help reach out to the leaf node, which will contain the record. While doing so, at first, the branch is selected between the two nodes where the node might be present. Then ultimately, the last thing to do will be to redirect it to the leaf node, where a sequential search will be followed to search that particular node.
Example
// C++ program for implementing the search in BPlus tree
#include<iostream>
using namespace std;
struct B_Plus_Tree{
int *d;
B_Plus_Tree **childPointer;
bool l;
int n;
}*r = NULL, *nodePointer = NULL, *x = NULL;
B_Plus_Tree* init() {//Creation of nodes in b+ tree
int i;
nodePointer = new B_Plus_Tree;
nodePointer->d = new int[6];//tree order should be 6
nodePointer->childPointer = new B_Plus_Tree*[7];
nodePointer->l = true;
nodePointer->n = 0;
for (i = 0; i < 7; i++) {
nodePointer->childPointer[i] = NULL;
}
return nodePointer;
}
void traverse(B_Plus_Tree*p){
cout<<endl;
int i;
for (i = 0; i < p->n; i++) {
if (p->l == false) {
traverse(p->childPointer[i]);
}
cout << " " << p->d[i];
}
if (p->l == false) {
traverse(p->childPointer[i]);
}
cout<<endl;
}
void sort(int *p, int n){//sorting of all the nodes present in 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 splittingTheChildren(B_Plus_Tree*x, int i) {
int j, mid;
B_Plus_Tree*nodePointer1, *nodePointer3, *y;
nodePointer3 = init();
nodePointer3->l = true;
if (i == -1) {
mid = x->d[2];
x->d[2] = 0;
x->n--;
nodePointer1 = init();
nodePointer1->l = false;
x->l = true;
for (j = 3; j < 6; j++) {
nodePointer3->d[j - 3] = x->d[j];
nodePointer3->childPointer[j - 3] = x->childPointer[j];
nodePointer3->n++;
x->d[j] = 0;
x->n--;
}
for (j = 0; j < 6; j++) {
x->childPointer[j] = NULL;
}
nodePointer1->d[0] = mid;
nodePointer1->childPointer[nodePointer1->n] = x;
nodePointer1->childPointer[nodePointer1->n + 1] = nodePointer3;
nodePointer1->n++;
r = nodePointer1;
} else {
y = x->childPointer[i];
mid = y->d[2];
y->d[2] = 0;
y->n--;
for (j = 3; j <6 ; j++) {
nodePointer3->d[j - 3] = y->d[j];
nodePointer3->n++;
y->d[j] = 0;
y->n--;
}
x->childPointer[i + 1] = y;
x->childPointer[i + 1] = nodePointer3;
}
return mid;
}
void insertingNode(int a) {
int i, t;
x = r;
if (x == NULL) {
r = init();
x = r;
} else {
if (x->l== true && x->n == 6) {
t = splittingTheChildren(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->childPointer[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->childPointer[i])->n == 6) {
t = splittingTheChildren(x, i);
x->d[x->n] = t;
x->n++;
continue;
} else {
x = x->childPointer[i];
}
}
}
}
x->d[x->n] = a;
sort(x->d, x->n);
x->n++;
}
int main() {
insertingNode(18);
insertingNode(20);
insertingNode(36);
insertingNode(95);
insertingNode(75);
insertingNode(52);
cout<<"B+ tree nodes resulted after traversing\n";
traverse(r);
}
The output of the execution of the above C++ program used to traverse the B+ tree created after inserting the nodes is as shown below. We can observe that the retrieved nodes are all in the sorted format arranged in ascending order.
Conclusion
B+ tree is similar to a balanced binary search tree but which has two orders, one for the internal nodes and the other for the leaf nodes. This makes it very efficient and fasts while performing the search, and that is why it is mostly used in the case of multilevel indexing.
Recommended Articles
This is a guide to B+ Tree in DBMS. Here we discuss the working of the B+ tree in DBMS and its structure and learn about its implementation with the help of an example. You may also have a look at the following articles to learn more –
