Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 21

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 22

The Best and Easiest Way to Understand an Algorithm

Lesson - 23

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 24

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 25

The Most Useful Guide to Learn Selection Sort Algorithm

Lesson - 26

Everything You Need to Know About Radix Sort Algorithm

Lesson - 27

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 28

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 29

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 30

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 31

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 32

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 33

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 34

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 35

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 36

Your One-Stop Solution for Graphs in Data Structures

Lesson - 37

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 38

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 39

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 40

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 41

The Holistic Look at Longest Common Subsequence Problem

Lesson - 42

The Best Article to Understand What Is Dynamic Programming

Lesson - 43

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 44

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 45

One Stop Solution to All the Dynamic Programming Problems

Lesson - 46

Understanding the Fundamentals of Binomial Distribution

Lesson - 47

Here’s All You Need to Know About Minimum Spanning Tree in Data Structures

Lesson - 48

Understanding the Difference Between Array and Linked List

Lesson - 49

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

Lesson - 50

A Comprehensive Look at Queue in Data Structure

Lesson - 51

Your One-Stop Solution to Understand Coin Change Problem

Lesson - 52

The Best Way to Understand the Matrix Chain Multiplication Problem

Lesson - 53

Your One-Stop Solution to Learn Floyd-Warshall Algorithm for Using Dynamic Programming

Lesson - 54
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 nomad 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.