“B+ tree” is similar to a “B-tree” with an additional level at the bottom with connected leaves and each node containing only keys (not key–value pairs). A “B+ tree in data structure” is an m-ary tree with a variable number of children per node, but frequently a high number. A root, internal nodes, and leaves make up a B+ tree.
By the end of this article, you will have a better understanding of the technical fundamentals of B+ trees.
Properties of B+ Tree in Data Structure
- Every node in a B+ Tree contains at most “m” children.
- Every node in a B+ Tree, except the root node and the leaf node contain at least “m/2” children.
- Nodes can have a maximum of (m-1) keys.
- Nodes can have a minimum of ⌈m/2⌉-1 keys.
These are the properties associated with B+ tree in data structure. Next, you will explore various operations you can perform on B+ tree in data structure.
Operations on B+ Tree in Data Structure
You can execute two operations on a B+ tree in a data structure:
- Insertion operation
- Deletion operation
Let's discuss them in detail.
Insertion Operation on B+ Tree in Data Structure
We will start with the root node and then find the suitable leaf node to which the new key will be added using the Binary Search Tree rules. Now, we will check if the leaf node has an empty place and add a new key in the tree. If the leaf node is complete, we will split it and send the key to its parent node. We will do this until all elements are filled in the B+ tree.
Code:
//A function to insert keys in b+ trees
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 splitchild(bplustreenode *x, int i)
{
int j, mid;
bplustreenode *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->childptr[j - 3] = x->childptr[j];
np3->n++;
x->data[j] = 0;
x->n--;
}
for(j = 0; j < 6; j++)
{
x->childptr[j] = NULL;
}
np1->data[0] = mid;
np1->childptr[np1->n] = x;
np1->childptr[np1->n + 1] = np3;
np1->n++;
root = np1;
}
else
{
y = x->childptr[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->childptr[i + 1] = y;
x->childptr[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 = splitchild(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->childptr[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->childptr[i])->n == 5)
{
temp = splitchild(x, i);
x->data[x->n] = temp;
x->n++;
continue;
}
else
{
x = x->childptr[i];
}
}
}
}
x->data[x->n] = a;
sort(x->data, x->n);
x->n++; }
Deletion Operation on the B+ Tree in Data Structure
Deletion from a B+ tree in data structure is more complex than insertion because we can delete a key from any node, not only a leaf, and we must rearrange the node's children when we delete a key from an internal node.
Code:
|
//A C++ function to delete keys from b+ tree in data structure Node *bptree::findparent(Node *csr, Node *child) { Node *parent; if (csr->isleaf || (csr->ptr[0])->isleaf) { return NULL; } //a for loop to locate parent for (int j = 0; j < csr->size + 1; j++) { if (csr->ptr[j] == child) { parent = csr; return parent; } else { parent = findparent(csr->ptr[j], child); . if (parent != NULL) return parent; } } return parent; } void bptree::remove(int x) { if (root == NULL) { cout << "Tree is empty\n"; } else { Node *csr = root; Node *parent; int ltsibling, rtsibling; while (csr->isleaf == false) { for (int j = 0; j < csr->size; j++) { parent = csr; ltsibling =j- 1; rtsibling = j+ 1; if (x < csr->key[j]) { csr = csr->ptr[j]; break; } if (j == csr->size - 1) { ltsibling =j; rtsibling = j + 2; csr = csr->ptr[j + 1]; break; } } } bool found = false; int pos; for (pos = 0; pos < csr->size; pos++) { if (csr->key[pos] == x) { found = true; break; } } if (!found) { cout << "Not found\n"; return; } for (int j= pos; j< csr->size; j++) { csr->key[j] = csr->key[j + 1]; } csr->size--; if (csr == root) { for (int j = 0;j < MAX + 1; j++) { csr->ptr[j] = NULL; } if (csr->size == 0) { cout << "Tree is dead\n"; delete[] csr->key;// delete csr's key delete[] csr->ptr;//delete csr's pointer delete csr;// delete csr root = NULL; //root is set to NULL } return; } //shift csr's pointer value back by one csr->ptr[csr->size] = csr->ptr[csr->size + 1]; //delete previous csr'pointer location csr->ptr[csr->size + 1] = NULL; if (csr->size >= (MAX + 1) / 2) { return; } if (ltsibling >= 0) { Node *leftnode = parent->ptr[ltsibling]; if (leftnode->size >= (MAX + 1) / 2 + 1) { for (int j= csr->size; j > 0;j--) { csr->key[j] = csr->key[j - 1]; } csr->size++; csr->ptr[csr->size] = csr->ptr[csr->size - 1]; csr->ptr[csr->size - 1] = NULL; csr->key[0] = leftnode->key[leftnode->size - 1]; leftnode->size--; leftnode->ptr[leftnode->size] = csr; leftnode->ptr[leftnode->size + 1] = NULL; parent->key[ltsibling] = csr->key[0]; return; } } if (rtsibling <= parent->size) { Node *rightnode = parent->ptr[rtsibling]; if (rightnode->size >= (MAX + 1) / 2 + 1) { csr->size++; csr->ptr[csr->size] = csr->ptr[csr->size - 1]; csr->ptr[csr->size - 1] = NULL; csr->key[csr->size - 1] = rightnode->key[0]; rightnode->size--;// decrease size of right node rightnode->ptr[rightnode->size] = rightnode->ptr[rightnode->size + 1]; //shift rightnode pointer back by one rightnode->ptr[rightnode->size + 1] = NULL; for (int j = 0;j < rightnode->size;j++) { rightnode->key[j] = rightnode->key[j+ 1]; } parent->key[rtsibling - 1] = rightnode->key[0]; return; } } if (ltsibling >= 0) { Node *leftnode = parent->ptr[ltsibling]; for (int k= leftnode->size, j = 0; j < csr->size; k++, j++) { leftnode->key[k] = csr->key[j]; } //delete left node pointer located at index as its size leftnode->ptr[leftnode->size] = NULL; leftnode->size += csr->size;// increase leftnode pointer size by csr's leftnode->ptr[leftnode->size] = csr->ptr[csr->size]; csr(parent->key[ltsibling], parent, csr); delete[] csr->key; delete[] csr->ptr; delete csr; } else if (rtsibling <= parent->size) { Node *rightnode = parent->ptr[rtsibling]; for (int k = csr->size, j = 0; j < rightnode->size; k++, j++) { csr->key[k] = rightnode->key[j]; } //delete csr ptr csr->ptr[csr->size] = NULL; csr->size += rightnode->size; // increase size of csr by rightnode's csr->ptr[csr->size] = rightnode->ptr[rightnode->size]; // store right node pointer's size in csr cout << "Merging two leaf nodes\n"; csr(parent->key[rtsibling - 1], parent, rightnode); delete[] rightnode->key;//delete righnode's key delete[] rightnode->ptr;//delete rightnode's pointer delete rightnode;// delete right node } } } void bptree::csr(int x, Node *csr, Node *child) { if (csr == root) { if (csr->size == 1) { // check if csr's pointer points at a child if (csr->ptr[1] == child) { delete[] child->key;//delete child's key delete[] child->ptr;// delete child's pointer delete child; //delete child itself root = csr->ptr[0]; //store root at csr pointer index 1 delete[] csr->key;//delete csr key delete[] csr->ptr;//delete csr pointer delete csr;//delete csr cout << "Change root node"; } else if (csr->ptr[0] == child) { delete[] child->key;// delete child's key delete[] child->ptr;//delete child's pointer delete child;//delete child itself root = csr->ptr[1]; delete[] csr->key; delete[] csr->ptr; delete csr; cout << "Changed root node\n"; return; } } } int pos; for (pos = 0; pos < csr->size; pos++) { if (csr->key[pos] == x) { break; } } for (int i = pos; i < csr->size; i++) { csr->key[i] = csr->key[i + 1]; } for (pos = 0; pos < csr->size + 1; pos++) { if (csr->ptr[pos] == child) { break; } } for (int i = pos; i < csr->size + 1; i++) { csr->ptr[i] = csr->ptr[i + 1]; } csr->size--; if (csr->size >= (MAX + 1) / 2 - 1) { return; } if (csr == root) return; Node *parent = findparent(root, csr); int ltsibling, rtsibling; for (pos = 0; pos < parent->size + 1; pos++) { if (parent->ptr[pos] == csr) { ltsibling = pos - 1; rtsibling = pos + 1; break; } } if (ltsibling >= 0) { Node *leftnode = parent->ptr[ltsibling]; if (leftnode->size >= (MAX + 1) / 2) { for (int i = csr->size; i > 0; i--) { csr->key[i] = csr->key[i - 1]; } csr->key[0] = parent->key[ltsibling]; parent->key[ltsibling] = leftnode->key[leftnode->size - 1]; for (int i = csr->size + 1; i > 0; i--) { csr->ptr[i] = csr->ptr[i - 1]; } csr->ptr[0] = leftnode->ptr[leftnode->size]; csr->size++; leftnode->size--; return; } } if (rtsibling <= parent->size) { Node *rightnode = parent->ptr[rtsibling]; if (rightnode->size >= (MAX + 1) / 2) { csr->key[csr->size] = parent->key[pos]; parent->key[pos] = rightnode->key[0]; for (int j = 0; j < rightnode->size - 1; j++) { rightnode->key[j] = rightnode->key[j + 1]; } csr->ptr[csr->size + 1] = rightnode->ptr[0]; for (int j = 0; j < rightnode->size; ++j) { rightnode->ptr[j] = rightnode->ptr[j + 1]; } csr->size++; rightnode->size--; return; } } if (ltsibling >= 0) { Node *leftnode = parent->ptr[ltsibling]; leftnode->key[leftnode->size] = parent->key[ltsibling]; for (int k = leftnode->size + 1, j = 0; j < csr->size; j++) { leftnode->key[k] = csr->key[j]; } for (int k = leftnode->size + 1, j = 0; j < csr->size + 1; j++) { leftnode->ptr[k] = csr->ptr[j]; csr->ptr[j] = NULL; } leftnode->size += csr->size + 1; csr->size = 0; csr(parent->key[ltsibling], parent, csr); } else if (rtsibling <= parent->size) { Node *rightnode = parent->ptr[rtsibling]; csr->key[csr->size] = parent->key[rtsibling - 1]; for (int k = csr->size + 1, j = 0; j < rightnode->size; j++) { csr->key[k] = rightnode->key[j]; } for (int k = csr->size + 1, j = 0; j < rightnode->size + 1; j++) { csr->ptr[k] = rightnode->ptr[j]; rightnode->ptr[j] = NULL; } csr->size += rightnode->size + 1; rightnode->size = 0; csr(parent->key[rtsibling - 1], parent, rightnode); } } |
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!
Next Steps
Your next stop in understanding data structures would be Sorting Algorithms. Sorting Algorithms rearrange elements in an array or list based on a comparison operator. Sorting is crucial for improving the performance of other algorithms that need input data to be in sorted lists (such as search and merging algorithms).
You've come to the right place if you want to learn more about software development and how to make a living doing it. You may be interested in Simplilearn's software development courses, which are delivered in partnership with Caltech CTME and IIT-Kanpur. All you need to know about Data Structures and Algorithms will be covered in these classes, from the fundamentals to more advanced topics like Competitive Programming. Data structures such as trees, graphs, and queues will be covered in this course to help you become a software developer.
If you have any questions or need any clarifications regarding this "B+ tree in Data Structure" tutorial, do let us know by leaving them in the comments section at the bottom of this page. Our expert team will ensure that they are answered at the earliest.
