B Tree in DBMS
How to perform Insertion operation in B Tree
A new value is inserted at the leaf node. Same like in a binary search tree we traverse from starting root node to till the leaf node and we insert a new key value at the leaf node.
Properties of the insertion:
- First, initialize a as the root.
- If a is not the root node, then follow the following conditions:
- Find the child or sub-node that is going to be traversed next. Let the child be b.
- If b is not full, change a to point to b.
- Divide it and change a to point to one of the two parts which are divided by b if the b is full.
- If k is smaller than the mid key in b, then set the a as the first part of b. Then the second part of b. When we divide b, we move a key from b to its parent a.
- The loop in step 2 stops when a is the leaf. Should have space for 1 extra key value as we have been dividing all nodes in before. So simply insert k to a.
Implementation of Insertion:
#include<iostream>
using namespace std;
// A BTree node
class BTreeNode
{
int *keys; // An array of keys
int t;
BTreeNode **C;
int n; // Current number of keys
bool leaf;
public:
BTreeNode(int _t, bool _leaf); // Constructor
void insertNonFull(int k);
void splitChild(int i, BTreeNode *y);
void traverse();
BTreeNode *search(int k);
// class in BTree functions
friend class BTree;
};
// A BTree
class BTree
{
BTreeNode *root;
int t; // Minimum degree
public:
BTree(int _t)
{ root = NULL; t = _t; }
void traverse()
{ if (root != NULL) root->traverse(); }
BTreeNode* search(int k)
{ return (root == NULL)? NULL : root->search(k); }
void insert(int k);
};
BTreeNode::BTreeNode(int t1, bool leaf1)
{
t = t1;
leaf = leaf1;
// and child pointers
keys = new int[2*t-1];
C = new BTreeNode *[2*t];
n = 0;
}
void BTreeNode::traverse()
{
// and first n children
int I;
for (i = 0; i < n; i++)
{
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}
// Print the subtree rooted with the last child
if (leaf == false)
C[i]->traverse();
}
BTreeNode *BTreeNode::search(int k)
{
while (i < n && k > keys[i])
i++;
if (keys[i] == k)
return this;
if (leaf == true)
return NULL;
return C[i]->search(k);
}
void BTree::insert(int k)
{
// If the tree is empty
if (root == NULL)
{
root = new BTreeNode(t, true);
root->keys[0] = k; // Insert key
root->n = 1; // Update number of keys in root
}
else // If the tree is not empty
{
// If the root is full, then the tree grows in height
if (root->n == 2*t-1)
{
BTreeNode *s = new BTreeNode(t, false);
// Make old root as a child of new root
s->C[0] = root;
s->splitChild(0, root);
int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);
// Change root
root = s;
}
else
root->insertNonFull(k);
}
}
void BTreeNode::insertNonFull(int k)
{
// Initialize index as index of rightmost element
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--;
// See if the found child is full
if (C[i+1]->n == 2*t-1)
{
// If the child is full, then split it
splitChild(i+1, C[i+1]);
// After the split, the middle key of C[i] goes up and
// is going to have the new key
if (keys[i+1] < k)
i++;
}
C[i+1]->insertNonFull(k);
}
}
void BTreeNode::splitChild(int i, BTreeNode *y)
{
// of y
BTreeNode *z = new BTreeNode(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;
// Since this node is going to have a new child,
// create space for a new child
for (int j = n; j >= i+1; j--)
C[j+1] = C[j];
// Link the new child to this node
C[i+1] = z;
for (int j = n-1; j >= i; j--)
keys[j+1] = keys[j];
keys[i] = y->keys[t-1];
// Increment count of keys in this node
n = n + 1;
}
// Driver program to test the above functions
int main()
{
BTree t(70); // A B-Tree with minimum degree 3
t.insert(14);
t.insert(26);
t.insert(56);
t.insert(69);
t.insert(92);
t.insert(34);
t.insert(70);
t.insert(17);
cout << "Traversal of the constructed tree is ";
t.traverse();
int k = 69;
(t.search(k) != NULL)? cout << "\nPresent" : cout << "\nNot Present";
k = 56;
(t.search(k) != NULL)? cout << "\nPresent" : cout << "\nNot Present";
return 0;
}Output:
Traversal of the tree is 70 14 26 56 69 92 34 70 17
Present
PresentDeletion operation in B Tree:
Compared to insertion the process of deletion is more complex because when we are deleting the node from leaf we have to rearrange the structure of the tree.
Properties of the deletion:
- If the key value is node and node is leaf node then directly delete the node
- If the key value is node and node is not a leaf node then follow the following conditions:
- If the key value is greater than the root node then traverse the right side. If the required key node is present then delete the node otherwise
- If the key value is less than the root node then traverse to left side. Delete the required key node from tree.
Implementation B Tree in C++:
#include<iostream>
using namespace std;
class BTreeNode
{
int *ky;
int temp;
BTreeNode **C;
int n;
bool leaf;
public:
BTreeNode(int _t, bool _leaf);
void traverse();
BTreeNode *search(int k);
int findKey(int k);
void insertNonFull(int k);
void splitChild(int i, BTreeNode *y);
void remove(int k);
void removeFromLeaf(int idx);
void removeFromNonLeaf(int idx);
int getPred(int idx);
int getSucc(int idx);
void fill(int idx);
void borrowFromPrev(int idx);
void borrowFromNext(int idx);
void merge(int idx);
};
class BTree
{
BTreeNode *root; // Pointer to root node
int temp; // Minimum degree
public:
BTree(int _t)
{
root = NULL;
t = _t;
}
void traverse()
{
if (root != NULL) root->traverse();
}
// function to search a key in this tree
BTreeNode* search(int k)
{
return (root == NULL)? NULL : root->search(k);
}
void insert(int k);
void remove(int k);
};
BTreeNode::BTreeNode(int t1, bool leaf1)
{
temp = t1;
leaf = leaf1;
// and child pointers
ky = new int[2*t-1];
C = new BTreeNode *[2*t];
// Initialize the number of keys as 0
n = 0;
}
int BTreeNode::findKey(int k)
{
int idx=0;
while (idx<n && ky[idx] < k)
++idx;
return idx;
}
void BTreeNode::remove(int k)
{
int idx = findKey(k);
// The key to be removed is present in this node
if (idx < n && ky[idx] == k)
{
// If the node is a leaf node - removeFromLeaf is called
if (leaf)
removeFromLeaf(idx);
else
removeFromNonLeaf(idx);
}
else
{
if (leaf)
{
cout<<"The key "<<k<<" is does not exist in the tree\n";
return;
}
bool flag = ( (idx==n)? true : false );
if (C[idx]->n < temp)
fill(idx);
if (flag && idx > n)
C[idx-1]->remove(k);
else
C[idx]->remove(k);
}
return;
}
void BTreeNode::removeFromLeaf (int idx)
{
for (int i=idx+1; i<n; ++i)
ky[i-1] = ky[i];
// Reduce the count of ky
n--;
return;
}
void BTreeNode::removeFromNonLeaf(int idx)
{
int k = ky[idx];
if (C[idx]->n >= temp)
{
int pred = getPred(idx);
ky[idx] = pred;
C[idx]->remove(pred);
}
else if (C[idx+1]->n >= temp)
{
int succ = getSucc(idx);
ky[idx] = succ;
C[idx+1]->remove(succ);
}
else
{
merge(idx);
C[idx]->remove(k);
}
return;
}
// A function to get predecessor of keys[idx]
int BTreeNode::getPred(int idx)
{
BTreeNode *cur=C[idx];
while (!cur->leaf)
cur = cur->C[cur->n];
// Return the last key of the leaf
return cur->ky[cur->n-1];
}
int BTreeNode::getSucc(int idx)
{
// Keep moving the left most node starting from C[idx+1] until we reach a leaf
BTreeNode *cur = C[idx+1];
while (!cur->leaf)
cur = cur->C[0];
// Return the first key of the leaf
return cur->ky[0];
}
// A function to fill child C[idx] which has less than t-1 keys
void BTreeNode::fill(int idx)
{
// If the previous child(C[idx-1]) has more than t-1 keys, borrow a key
// from that child
if (idx!=0 && C[idx-1]->n>=t)
borrowFromPrev(idx);
else if (idx!=n && C[idx+1]->n>=temp)
borrowFromNext(idx);
else
{
if (idx != n)
merge(idx);
else
merge(idx-1);
}
return;
}
void BTreeNode::borrowFromPrev(int idx)
{
BTreeNode *child=C[idx];
BTreeNode *sibling=C[idx-1];
for (int i=child->n-1; i>=0; --i)
child->keys[i+1] = child->keys[i];
if (!child->leaf)
{
for(int i=child->n; i>=0; --i)
child->C[i+1] = child->C[i];
}
child->ky[0] = ky[idx-1];
if(!child->leaf)
child->C[0] = sibling->C[sibling->n];
ky[idx-1] = sibling->ky[sibling->n-1];
child->n += 1;
sibling->n -= 1;
return;
}
void BTreeNode::borrowFromNext(int idx)
{
BTreeNode *child=C[idx];
BTreeNode *sibling=C[idx+1];
if (!(child->leaf))
child->C[(child->n)+1] = sibling->C[0];
ky[idx] = sibling->ky[0];
for (int i=1; i<sibling->n; ++i)
sibling->ky[i-1] = sibling->ky[i];
if (!sibling->leaf)
{
for(int i=1; i<=sibling->n; ++i)
sibling->C[i-1] = sibling->C[i];
}
C[idx] and C[idx+1]
// respectively
child->n += 1;
sibling->n -= 1;
return;
}
void BTreeNode::merge(int idx)
{
BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx+1];
child->ky[t-1] = ky[idx];
for (int i=0; i<sibling->n; ++i)
child->ky[i+t] = sibling->ky[i];
if (!child->leaf)
{
for(int i=0; i<=sibling->n; ++i)
child->C[i+t] = sibling->C[i];
}
for (int i=idx+1; i<n; ++i)
ky[i-1] = ky[i];
for (int i=idx+2; i<=n; ++i)
C[i-1] = C[i];
child->n += sibling->n+1;
n--;
return;
}
void BTree::insert(int k)
{
// If tree is empty
if (root == NULL)
{
// Allocate memory for root
root = new BTreeNode(t, true);
root->keys[0] = k; // Insert key
root->n = 1; // Update number of keys in root
}
else
{
if (root->n == 2*t-1)
{
BTreeNode *s = new BTreeNode(t, false);
s->C[0] = root;
s->splitChild(0, root)
int i = 0;
if (s->ky[0] < k)
i++;
s->C[i]->insertNonFull(k);
// Change root
root = s;
}
else
root->insertNonFull(k);
}
}
void BTreeNode::insertNonFull(int k)
{
int i = n-1;
if (leaf == true)
{
while (i >= 0 && ky[i] > k)
{
ky[i+1] = ky[i];
i--;
}
// Insert the new key at found location
ky[i+1] = k;
n = n+1;
}
else // If this node is not leaf
{
// Find the child which is going to have the new key
while (i >= 0 && ky[i] > k)
i--;
// See if the found child is full
if (C[i+1]->n == 2*t-1)
{
// If the child is full, then split it
splitChild(i+1, C[i+1]);
// C[i] is splitted into two. See which of the two
// is going to have the new key
if (ky[i+1] < k)
i++;
}
C[i+1]->insertNonFull(k);
}
}
void BTreeNode::splitChild(int i, BTreeNode *y)
{
// of y
BTreeNode *z = new BTreeNode(y->temp, y->leaf);
z->n = temp - 1;
// Copy the last (temp-1) ky of y to z
for (int j = 0; j < temp-1; j++)
z->ky[j] = y->ky[j+temp];
// Copy the last t children of y to z
if (y->leaf == false)
{
for (int j = 0; j < temp; j++)
z->C[j] = y->C[j+temp];
}
y->n = temp - 1;
// Since this node is going to have a new child,
// create space of new child
for (int j = n; j >= i+1; j--)
C[j+1] = C[j];
// Link the new child to this node
C[i+1] = z;
for (int j = n-1; j >= i; j--)
ky[j+1] = ky[j];
n = n + 1;
}
void BTreeNode::traverse()
{
int i;
for (i = 0; i < n; i++)
{
if (leaf == false)
C[i]->traverse();
cout << " " << ky[i];
}
// Print the subtree rooted with last child
if (leaf == false)
C[i]->traverse();
}
BTreeNode *BTreeNode::search(int k)
{
int i = 0;
while (i < n && k > ky[i])
i++;
// If the found key is equal to k, return this node
if (ky[i] == k)
return this;
// If key is not found here and this is a leaf node
if (leaf == true)
return NULL;
// Go to the appropriate child
return C[i]->search(k);
}
void BTree::remove(int k)
{
if (!root)
{
cout << "The tree is empty\n";
return;
}
// Call the remove function for root
root->remove(k);
if (root->n==0)
{
BTreeNode *tmp = root;
if (root->leaf)
root = NULL;
else
root = root->C[0];
// Free the old root
delete tmp;
}
return;
}
// Driver program to test above functions
int main()
{
BTree t(3); // A B-Tree with minimum degree 3
t.insert(19);
t.insert(38);
t.insert(77);
t.insert(1);
t.insert(16);
t.insert(78);
t.insert(4);
t.insert(5);
t.insert(58);
t.insert(60);
t.insert(15);
t.insert(94);
t.insert(50);
t.insert(16);
t.insert(11);
t.insert(41);
t.insert(54);
t.insert(2);
t.insert(82);
t.insert(20);
t.insert(77);
t.insert(23);
t.insert(60);
cout << "Traversal of tree constructed is\n";
t.traverse();
cout << endl;
t.remove(60);
cout << "Traversal of tree after removing 60\n";
t.traverse();
cout << endl;
t.remove(82);
cout << "Traversal of tree after removing 82\n";
t.traverse();
cout << endl;
t.remove(77);
cout << "Traversal of tree after removing 77\n";
t.traverse();
cout << endl;
t.remove(4);
cout << "Traversal of tree after removing 4\n";
t.traverse();
cout << endl;
t.remove(26);
cout << "Traversal of tree after removing 26\n";
t.traverse();
cout << endl;
t.remove(16);
cout << "Traversal of tree after removing 16\n";
t.traverse();
cout << endl;
return 0;
}