“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.

#### Here's How to Land a Top Software Developer Job

Full Stack Development-MEAN ## 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. #### Learn the Ins & Outs of Software Development

Caltech Coding Bootcamp 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;

x->data = 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 = mid;

np1->childptr[np1->n] = x;

np1->childptr[np1->n + 1] = np3;

np1->n++;

root = np1;

}

else

{

y = x->childptr[i];

mid = y->data;

y->data = 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)

{

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)

{

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++;  } #### Here's How to Land a Top Software Developer Job

Full Stack Development-MEAN ## 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)->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 = leftnode->key[leftnode->size - 1];         leftnode->size--;         leftnode->ptr[leftnode->size] = csr;         leftnode->ptr[leftnode->size + 1] = NULL;         parent->key[ltsibling] = csr->key;         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;        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;         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 == child) {         delete[] child->key;//delete child's key         delete[] child->ptr;// delete child's pointer         delete child; //delete child itself         root = csr->ptr; //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 == child) {         delete[] child->key;// delete child's key         delete[] child->ptr;//delete child's pointer         delete child;//delete child itself         root = csr->ptr;         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 = 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 = 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;       for (int j = 0; j < rightnode->size - 1; j++) {         rightnode->key[j] = rightnode->key[j + 1];       }       csr->ptr[csr->size + 1] = rightnode->ptr;       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. Nikita Duggal