The Best Article Out There to Understand the B+ Tree in Data Structure

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

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

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

Btrees_in_ds-insertion-img1

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.

Btrees_in_ds-insertion-img2

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

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++;  }

Btrees_in_ds-insertion-img3.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

Deletion Operation on the B+ Tree in Data Structure

Btrees_in_ds-deletion-img1.

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. 

Btrees_in_ds-deletion-img2

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);

  }

}

Btrees_in_ds-deletion-img3

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.

About the Author

Nikita DuggalNikita Duggal

Nikita Duggal is a passionate digital marketer with a major in English language and literature, a word connoisseur who loves writing about raging technologies, digital marketing, and career conundrums.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.
  • *According to Simplilearn survey conducted and subject to terms & conditions with Ernst & Young LLP (EY) as Process Advisors