Insertion in B+ Tree
We will learn how to insert a node in the B+ tree and what are the different properties we are going to follow.
Except for the root node, every node should have a maximum of Children at least ceil(M/2) children.
The root node must contain at least two children and at least one search key.
Steps for insertion at root node:
- Every element must be inserted in the leaf node.
- If an overflow situation occurs in the leaf nodes, we must follow the following steps to overcome the overflow.
- Partition the leaf into two different nodes along with the other nodes.
- The starting node contains the ceiling value of (m-1)/2.
- The next node contains the remaining nodes from the above nodes.
- Insert the element in the left base node in the Right-biased tree.
Code for the insertion at B+ Tree
// C++ program for implementing B+ Tree
#include <climits>
#include <fstream>
#include <iostream>
#include <sstream>
using namespace std;
int MAX = 3;
// BP node
class Node {
bool IS_LEAF;
int *key, size;
Node** ptr;
friend class BPTree;
public:
Node();
};
// BP tree
class BPTree {
Node* root;
void insert internal(int,
Node*,
Node*);
Node* findParent(Node*, Node*);
public:
BPTree();
void search(int);
void insert(int);
void display(Node*);
Node* getRoot();
};
// Constructor of Node
Node::Node()
{
key = new int[MAX];
ptr = new Node*[MAX + 1];
}
// Initialise the BPTree Node
BPTree::BPTree()
{
root = NULL;
}
// Function to find any element
// in B+ Tree
void BPTree::search(int x)
{
// If the tree is empty
if (root == NULL) {
cout << "Tree is empty\n";
}
// Traverse to find the value
else {
Node* cursor = root;
while (cursor->IS_LEAF == false) {
for (int i = 0;
i < cursor->size; i++) {
if (x < cursor->key[i]) {
cursor = cursor->ptr[i];
break;
}
// If reaches the end of the
// cursor node
if (i == cursor->size - 1) {
cursor = cursor->ptr[i + 1];
break;
}
}
}
for (int i = 0;
i < cursor->size; i++) {
// If found then return
if (cursor->key[i] == x) {
cout << "Found\n";
return;
}
}
// Else element is not present
cout << "Not found\n";
}
}
// Function to implement the Insert
void BPTree::insert(int x)
{
if (root == NULL) {
root = new Node;
root->key[0] = x;
root->IS_LEAF = true;
root->size = 1;
}
// Traverse the B+ Tree
else {
Node* cursor = root;
Node* parent;
while (cursor->IS_LEAF
== false) {
parent = cursor;
for (int i = 0;
i < cursor->size;
i++) {
// If found the position
// where we have to insert
// node
if (x < cursor->key[i]) {
cursor
= cursor->ptr[i];
break;
}
// If reaches the end
if (i == cursor->size - 1) {
cursor
= cursor->ptr[i + 1];
break;
}
}
}
if (cursor->size < MAX) {
int i = 0;
while (x > cursor->key[i]
&& i < cursor->size) {
i++;
}
for (int j = cursor->size;
j > i; j--) {
cursor->key[j]
= cursor->key[j - 1];
}
cursor->key[i] = x;
cursor->size++;
cursor->ptr[cursor->size]
= cursor->ptr[cursor->size - 1];
cursor->ptr[cursor->size - 1] = NULL;
}
else {
// Create a newLeaf node
Node* newLeaf = new Node;
int virtualNode[MAX + 1];
// node created
for (int i = 0; i < MAX; i++) {
virtualNode[i]
= cursor->key[i];
}
int i = 0, j;
// Traverse to find where the new
while (x > virtualNode[i]
&& i < MAX) {
i++;
}
// Update the current virtual
// Node to its previous
for (int j = MAX + 1;
j > i; j--) {
virtualNode[j]
= virtualNode[j - 1];
}
virtualNode[i] = x;
newLeaf->IS_LEAF = true;
cursor->size = (MAX + 1) / 2;
newLeaf->size
= MAX + 1 - (MAX + 1) / 2;
cursor->ptr[cursor->size]
= newLeaf;
newLeaf->ptr[newLeaf->size]
= cursor->ptr[MAX];
cursor->ptr[MAX] = NULL;
// Update the current virtual
// Node's key to its previous
for (i = 0;
i < cursor->size; i++) {
cursor->key[i]
= virtualNode[i];
}
// Update the newLeaf key to
// virtual Node
for (i = 0, j = cursor->size;
i < newLeaf->size;
i++, j++) {
newLeaf->key[i]
= virtualNode[j];
}
// If the cursor is the root node
if (cursor == root) {
Node* newRoot = new Node;
// Update the rest field of
// B+ Tree Node
newRoot->key[0] = newLeaf->key[0];
newRoot->ptr[0] = cursor;
newRoot->ptr[1] = newLeaf;
newRoot->IS_LEAF = false;
newRoot->size = 1;
root = newRoot;
}
else {
// Recursive Call for
// insert in internal
insertInternal(newLeaf->key[0],
parent,
newLeaf);
}
}
}
}
// Function to implement the Insert
// Internal Operation in B+ Tree
void BPTree::insertInternal(int x,
Node* cursor,
Node* child)
{
// If we don’t have overflow
if (cursor->size < MAX) {
int i = 0;
// Traverse the child node
// for current cursor node
while (x > cursor->key[i]
&& i < cursor->size) {
i++;
}
for (int j = cursor->size;
j > i; j--) {
cursor->key[j]
= cursor->key[j - 1];
}
for (int j = cursor->size + 1;
j > i + 1; j--) {
cursor->ptr[j]
= cursor->ptr[j - 1];
}
cursor->key[i] = x;
cursor->size++;
cursor->ptr[i + 1] = child;
}
else {
Node* newInternal = new Node;
int virtualKey[MAX + 1];
Node* virtualPtr[MAX + 2];
for (int i = 0; i < MAX; i++) {
virtualKey[i] = cursor->key[i];
}
for (int i = 0; i < MAX + 1; i++) {
virtualPtr[i] = cursor->ptr[i];
}
int i = 0, j;
// Traverse to find where the new
while (x > virtualKey[i]
&& i < MAX) {
i++;
}
// Traverse the virtual node
// and update the current key
// to its previous node key
for (int j = MAX + 1;
j > i; j--) {
virtualKey[j]
= virtualKey[j - 1];
}
virtualKey[i] = x;
for (int j = MAX + 2;
j > i + 1; j--) {
virtualPtr[j]
= virtualPtr[j - 1];
}
virtualPtr[i + 1] = child;
newInternal->IS_LEAF = false;
cursor->size
= (MAX + 1) / 2;
newInternal->size
= MAX - (MAX + 1) / 2;
// Insert a new node as an
// internal node
for (i = 0, j = cursor->size + 1;
i < newInternal->size;
i++, j++) {
newInternal->key[i]
= virtualKey[j];
}
for (i = 0, j = cursor->size + 1;
i < newInternal->size + 1;
i++, j++) {
newInternal->ptr[i]
= virtualPtr[j];
}
// If the cursor is the root node
if (cursor == root) {
// Create a new root node
Node* newRoot = new Node;
// Update key value
newRoot->key[0]
= cursor->key[cursor->size];
// Update the rest field of
// B+ Tree Node
newRoot->ptr[0] = cursor;
newRoot->ptr[1] = newInternal;
newRoot->IS_LEAF = false;
newRoot->size = 1;
root = newRoot;
}
else {
// Recursive Call to insert
// the data
insertInternal(cursor->key[cursor->size],
findParent(root,
cursor),
newInternal);
}
}
}
// Function to find the parent node
Node* BPTree::findParent(Node* cursor,
Node* child)
{
Node* parent;
// If the cursor reaches the end of the Tree
if (cursor->IS_LEAF
|| (cursor->ptr[0])->IS_LEAF) {
return NULL;
}
// Traverse the current node with
// all its child
for (int i = 0;
i < cursor->size + 1; i++) {
// Update the parent for the
// child Node
if (cursor->ptr[i] == child) {
parent = cursor;
return parent;
}
// Else recursively traverse to
// find child node
else {
parent
= findParent(cursor->ptr[i],
child);
// If a parent is found, then
// return that parent node
if (parent != NULL)
return parent;
}
}
// Return parent node
return parent;
}
// Function to get the root Node
Node* BPTree::getRoot()
{
return root;
}
// Driver Code
int main()
{
BPTree node;
// Create B+ Tree
node.insert(20);
node.insert(109);
node.insert(76);
node.insert(82);
node.insert(55);
// Function Call to search node
// with value 76
node.search(76);
return 0;
}