Do you think IIT Guwahati certified course can help you in your career?
Introduction📙
A B-tree Data Structure is a self-balancing tree data structure in computer science that keeps sorted data and supports logarithmic searches, sequential access, insertions, and deletions.
The B-tree is a variant of the binary search tree that allows nodes to have more than two children.
The B-tree is particularly suited for storage systems that read and write relatively large data blocks, such as discs. It's a common database and file system format.
Every insertion begins at a leaf node. To add a new element, search the tree for the leaf node where the new feature should be inserted, similar to how a binary search tree is searched for insertion.
Depending on whether the leaf node has space for the new element or not, follow these procedures to add the new element to that node:
🙇If the leaf node contains space for the new element, insert the new element into the node while maintaining the order of the node's constituents.
🙇Otherwise, if the node is complete, divide it evenly into two nodes as follows:
💥We chose a median element considering both the leaf elements node and the new element.
💥We create two new nodes, namely left and right, respectively. With median as a comparison/separation value, all the elements less than the median are put in the left node. Similarly, all the elements greater than the median are placed in the right node.
💥Then, the median is called upon to be inserted into the parent node, which further, depending on the values and conditions, may or may not split the parent node and so on until we encounter the root.
💥If the node does not contain any parent, i.e., the root node, and splitting takes place, we increase the tree's height by creating a new node.
Example📖
Suppose we have no tree initially and insert the following nodes into the B-Tree.
Insert: Node as 1, 2, 3, 4, 5, 6, 7, and suppose the order of the B-Tree is 3.
Approach👩💻
🧿Initially, we had no root node, so we created a root node and inserted 1. Simple and easy.
🧿Now we need to insert 2, and we have space for inserting an element and inserting it. Again, Simple and easy.
🧿Now we need to insert 3. As we can see, we have no space for the insertion of 3, and the nodes are in an overflow condition. We pick 2 as the median and create two child nodes, left and right. Element smaller than 2, i.e., 1, is put in the left node, and similarly, an element greater than 2, i.e., 3, is in the right node. 2 is now the root node.
🧿Now we need to insert 4. We have space for insertion of 4 in the node containing 3, so we insert it.
🧿Next, we have 5. We can see the node where 5 needs to be inserted is already full. Thus we need to split again the node containing elements 3 and 4. We chose 4 as the median and created 2 nodes with the left child as 3 and the right as 5. The median will now go up to the parent node, i.e., the node containing 2. Since we have space for insertion of 4, insertion takes place accordingly.
🧿Now we need to insert 6. We have space for 6, so we insert it.
🧿 Lastly, we have 7. We can see the node where 7 needs to be inserted is already full. Thus we need to split again the node containing elements 5 and 6. We chose 6 as the median and created 2 nodes with the left child as 5 and the right child as 7. The median will now go up to the parent node, i.e., the node containing 2 and 4.
Now for the parent node containing 2 and 4, insertion of the element is not possible, resulting in overflow. We need to split the parent node here. Chose 4 as median and accordingly created two nodes such that 2 goes to the left node and 6 goes to the right node. Now median element 4 is in the root itself and cannot be pushed to its parent, and we need to create a new parent node containing 4.
Congratulations, Insertion Completed💃.
Solution
📌C++
#include<stdio.h>
#include<conio.h>
#include<iostream>
using namespace std;
class Node {
int *keys;
int t;
Node **C;
int n;
bool leaf;
public:
Node(int t, bool leaf) {
this->t = t;
this->leaf = leaf;
keys = new int[2 * t - 1];
C = new Node *[2 * t];
n = 0;
}
/* Insert non full condition */
void insertNonFull(int k) {
int i = n - 1;
if (leaf == true) {
while (i >= 0 && keys[i] > k) {
keys[i + 1] = keys[i];
i--;
}
keys[i + 1] = k;
n = n + 1;
} else {
while (i >= 0 && keys[i] > k)
i--;
if (C[i + 1]->n == 2 * t - 1) {
splitChild(i + 1, C[i + 1]);
if (keys[i + 1] < k)
i++;
}
C[i + 1]->insertNonFull(k);
}
}
/* split the child */
void splitChild(int i, Node *y) {
Node *z = new Node(y->t, y->leaf);
z->n = t - 1;
for (int j = 0; j < t - 1; j++)
z->keys[j] = y->keys[j + t];
if (y->leaf == false) {
for (int j = 0; j < t; j++)
z->C[j] = y->C[j + t];
}
y->n = t - 1;
for (int j = n; j >= i + 1; j--)
C[j + 1] = C[j];
C[i + 1] = z;
for (int j = n - 1; j >= i; j--)
keys[j + 1] = keys[j];
keys[i] = y->keys[t - 1];
n = n + 1;
}
/* Traverse the nodes */
void traverse() {
int i;
for (i = 0; i < n; i++) {
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}
if (leaf == false)
C[i]->traverse();
}
friend class BTree;
};
class BTree {
Node *root;
int t;
public:
BTree(int t) {
root = NULL;
this->t = t;
}
void traverse() {
if (root != NULL)
root->traverse();
}
/* Insert the node */
void insert(int k) {
if (root == NULL) {
root = new Node(t, true);
root->keys[0] = k;
root->n = 1;
}
else {
if (root->n == 2 * t - 1) {
Node *s = new Node(t, false);
s->C[0] = root;
s->splitChild(0, root);
int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);
root = s;
}
else
root->insertNonFull(k);
}
}
};
int main() {
BTree t(3);
t.insert(1);
t.insert(2);
t.insert(3);
t.insert(4);
t.insert(5);
t.insert(6);
t.insert(7);
cout << "The B-tree is: ";
t.traverse();
}
You can also try this code with Online C++ Compiler
A B-tree data structure is a self-balancing tree data structure in computer science that keeps sorted data and supports logarithmic searches, sequential access, insertions, and deletions. The B-tree is a variant of the binary search tree that allows nodes to have more than two children.
What is the order of the B-Tree?
Order of B-Tree is the maximum number of children a node can have.
What is the B+Tree?
B+ Trees are balanced search trees used frequently in databases to index tables. They are an advanced and self-balancing version of the B-Tree that allows efficient and convenient insertion, deletion, and search.
What is the Depth of a tree?
The Depth of the tree refers to the levels of the records of the tree from the root to the leaves.
What are leaf nodes in a tree?
The leaf nodes, also known as leaves, are the nodes at the bottom of a tree that indicates the tree's end. The leaf nodes are all at equal heights.
Conclusion
In this article, we learned about Insertion Operation in B- trees. We have seen examples to understand the concept better and learn to implement our knowledge of Insertion Operation in B-trees.
19+ registered 
