A B-tree is a data structure that maintains data sorted and supports logarithmic amortized searches, insertions, and deletions. It is optimized for systems that read and write big data blocks, unlike self-balancing binary search trees. It's most often found in database and file management systems.
By the end of this tutorial, you will understand the technical fundamentals of b-trees with all the necessary details and practical examples.
What Are the Properties of B-Trees?
- Each B-Tree node has a maximum of m children.
- Each node in a B tree includes at least m/2 children, except the root node and the leaf node.
- At least two root nodes are required.
- All nodes of the leaf must be on the same level.
These are the properties associated with B-trees in data structures. Next, you will explore various operations you can perform on B-trees in data structures.
What Are the Operations You Can Perform on B-Trees?
You can execute three operations on a b-tree in data structures:
- Insertion operation
- Search operation
- Deletion operation
Now, you will explore them in detail.
Insertion Operation on B-Trees in Data Structures
You must 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, you will check if the leaf node has an empty place and add a new key in the tree. If the leaf node is complete, you must split it and send the key to its parent node. You must do this until all elements are filled in the b-tree.
Code:
// A C++ program to perform insertion on btree
#include<bits/stdc++.h>
using namespace std;
// A class to create a node
class btreenode
{
int *key;
int t;
btreenode **c; // A child pointers array
int n;
bool leaf; // returns true if tree is empty
public:
btreenode(int _t, bool _leaf);// btreenode class constructor
// A function to insert a new key in the subtree rooted with non full node.
void insertnonfull(int k);
// A function to split the child y of this node.
void splitchild(int i, btreenode *y);
void traverse();// A function to traverse the b-tree
// A function to search the key in the b-tree
btreenode *search(int k); // if k not found the returns NULL
//we will make btree friend of btreenode class so that we can access private members of this class
friend class btree;
};
// class btree
class btree
{
btreenode *root; //root node pointer
int t;
public:
// btree class Constructor initialized as empty
btree(int _t)
{
root = NULL;
t = _t;
}
// function to traverse the tree
void traverse()
{ if (root != NULL)
root->traverse();
}
// A function to insert the key in the node
void insert(int k);
};
//btreenode class constructor
btreenode::btreenode(int t1, bool leaf1)
{
t = t1;
leaf = leaf1;
// Allocate memory for max possible keys
// and the child pointers
key = new int[2*t-1];
c = new btreenode *[2*t];
n = 0;
}
// A function to traverse the tree
void btreenode::traverse()
{
int i;
for (i = 0; i < n; i++)
{
if (leaf == false)
c[i]->traverse();
cout << " " << key[i];
}
if (leaf == false)
c[i]->traverse();
}
// A Function to insert a key in B-Tree
void btree::insert(int k)
{
//check if tree is empty
if (root == NULL)
{
root = new btreenode(t, true);
root->key[0] = k;
root->n = 1;
}
else
{
// If root is full, then tree's height increases
if (root->n == 2*t-1)
{
btreenode *s = new btreenode(t, false);
// Change old root as new root's child
s->c[0] = root;
s->splitchild(0, root);
int i = 0;
if (s->key[0] < k)
i++;
s->c[i]->insertnonfull(k);
root = s;
}
else // If root is empty,then we will call insertnonfull
root->insertnonfull(k);
}
}
void btreenode::insertnonfull(int k)
{
// Initialize index as rightmost element's index
int i = n-1;
if (leaf == true)
{
// The following loop will find the location of key
//and move all bigger keys one place further
while (i >= 0 && key[i] > k)
{
key[i+1] = key[i];
i--;
}
key[i+1] = k;
n = n+1;
}
else // If this node is not the leaf
{
while (i >= 0 && key[i] > k)
i--;
if (c[i+1]->n == 2*t-1)
{
splitchild(i+1, c[i+1]);
if (key[i+1] < k)
i++;
}
c[i+1]->insertnonfull(k);
}
}
void btreenode::splitchild(int i, btreenode *y)
{
//
btreenode *z = new btreenode(y->t, y->leaf);
z->n = t - 1;
for (int j = 0; j < t-1; j++)
z->key[j] = y->key[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--)
key[j+1] = key[j];
key[i] = y->key[t-1];
//we will increment count of keys
n = n + 1;
}
int main()
{
btree p(3); // A B-Tree with minium degree 3
p.insert(15);
p.insert(2);
p.insert(25);
p.insert(16);
p.insert(32);
p.insert(30);
p.insert(6);
p.insert(7);
cout << "Traversal of the constructed tree is ";
p.traverse();
return 0;
}
Search Operation on B-Trees in Data Structures
You must start from the leftmost node and compare it with the key. If it doesn't match, you will move to the next node to find the key or traverse the complete tree.
Code:
// C++ program for B-Tree search
#include<iostream>
using namespace std;
// A class to create a b-tree node
class btreenode
{
int *key;
int t;
btreenode **c; // A child pointers Array
int n;
bool leaf; // return true if leaf is empty
public:
btreenode(int _t, bool _leaf); // A btreenode class constructor
// A function to insert a new key in the subtree rooted with
// this non full node.
void insertnonfull(int k);
// A function to split the child y of this node.
void splitchild(int i, btreenode *y);
void traverse();// A function to traverse the b-tree
// A function to search the key in the b-tree
btreenode *search(int k); // if k not found the returns NULL
//we will make btree friend of btreenode class
//so that we can access private members of this class
friend class btree;
};
class btree
{
btreenode *root; // A root pointer
int t; // Minimum degree
public:
// btree constructor intialized empty
btree(int _t)
{ root = NULL; t = _t; }
// function definition of traverse function
void traverse()
{ if (root != NULL) root->traverse(); }
// function definition of search function
btreenode* search(int k)
{ return (root == NULL)? NULL : root->search(k); }
// A function to insert key in the node
void insert(int k);
};
//btreenode class constructor
btreenode::btreenode(int t1, bool leaf1)
{
t = t1;
leaf = leaf1;
key = new int[2*t-1];
c = new btreenode *[2*t];
n = 0;
}
void btreenode::traverse()
{
int i;
for (i = 0; i < n; i++)
{
// If not leaf, then we will traverse the subtree rooted with child c[i].
if (leaf == false)
c[i]->traverse();
cout << " " << key[i];
}
// Print the subtree rooted with last child
if (leaf == false)
c[i]->traverse();
}
btreenode *btreenode::search(int k)
{
//we will search the key which is greater than
int i = 0;
while (i < n && k > key[i])
i++;
// If the key is found to be equal to k
if (key[i] == k)
return this;
if (leaf == true)
return NULL;
return c[i]->search(k);
}
// The Function that inserts a key in this B-Tree
void btree::insert(int k)
{
// If the tree is empty
if (root == NULL)
{
// Allocate memory for root
root = new btreenode(t, true);
root->key[0] = k;
root->n = 1;
}
else
{
// If root is full, then increase height of the tree
if (root->n == 2*t-1)
{
btreenode *s = new btreenode(t, false);
// change old root as new root's child
s->c[0] = root;
s->splitchild(0, root);
int i = 0;
if (s->key[0] < k)
i++;
s->c[i]->insertnonfull(k);
root = s;
}
// If root is not full, call insertnonfull function for root
else
root->insertnonfull(k);
}
}
void btreenode::insertnonfull(int k)
{
int i = n-1;
if (leaf == true)
{
// The following loop will find the location of key
//and move all bigger keys one place further
while (i >= 0 && key[i] > k)
{
key[i+1] = key[i];
i--;
}
// Insert the new key at found location
key[i+1] = k;
n = n+1;
}
else
{
// we will search the child which will have key
while (i >= 0 && key[i] > k)
i--;
//check if the child is full,
if((c[i+1]->n) == 2*t-1)
{
//then we will split this child
splitchild(i+1, c[i+1]);
if (key[i+1] < k)
i++;
}
c[i+1]->insertnonfull(k);
}
}
void btreenode::splitchild(int i, btreenode *y)
{
//we will create a new node z
btreenode *z = new btreenode(y->t, y->leaf);
// we will store t-1 keys in z
z->n = t - 1;
// we will copy the last (t-1) keys of y to z
for (int j = 0; j < t-1; j++)
z->key[j] = y->key[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 k = n; k >= i+1; k--)
c[k+1] = c[k];
c[i+1] = z;
for (int k = n-1; k >= i; k--)
key[k+1] = key[k];
key[i] = y->key[t-1];
n = n + 1;
}
int main()
{
btree t(3);
t.insert(13);
t.insert(8);
t.insert(5);
t.insert(6);
t.insert(11);
t.insert(3);
t.insert(7);
t.insert(27);
cout << "Traversal of the constucted tree is ";
t.traverse();
int k = 6;
if(t.search(k) != NULL)
cout << "\nPresent";
else
cout << "\nNot Present";
k = 15;
if(t.search(k) != NULL)
cout << "\nPresent";
else
cout << "\nNot Present";
return 0;
}
Deletion Operation on the B-Trees in Data Structures
Deletion from a B-tree is more complex than insertion because you can delete a key from any node, not only a leaf, and you must rearrange the node's children when you delete a key from an internal node.
Code:
//A C++ programme to delete keys from btree
#include<bits/stdc++.h>
using namespace std;
// A class to create btree node
class btreenode
{
int *key;
int t;
btreenode **c; // A child pointer's Array
int n;
bool leaf; // returns true, if node is leaf
public:
btreenode(int _t, bool _leaf); //A btreenode class constructor
// A function to traverse btree
void traverse();
btreenode *search(int k); // if k is not present return false
int findkey(int k);// a function to find a key in the btree
// A function to split the child y of this node.
void splitchild(int i, btreenode *y);
void remove(int k);
//A function to delete a key at idx index which is leaf
void removefromleaf(int idx);
// A function to delete a key at idx index which is leaf non-leaf
void removefromnonleaf(int idx);
int getpred(int idx);
int getsucc(int idx);
// A function for filling the child node in the idx index.
void fill(int idx);
void borrowfromprev(int idx);
void borrowfromnext(int idx);
// A function to merge idx child of the node next node
void merge(int idx);
// we will make BTree friend of btreenode
friend class btree;
};
class btree
{
btreenode *root; //root node's pointer
int t;
public:
//btree class Constructor
btree(int _t)
{
root = NULL;
t = _t;
}
void traverse()
{
if (root != NULL)
root->traverse();
}
//A function to search a key in this tree
btreenode* search(int k)
{
if(root == NULL)
return NULL;
else
root->search(k);
}
// A function that removes a new key in the BTree
void remove(int k);
};
btreenode::btreenode(int t1, bool l1)
{
t = t1;
leaf = l1;
// Allocate memory for max possible keys and child pointers
key = new int[2*t-1];
c = new btreenode *[2*t];
n = 0;
}
int btreenode::findkey(int k)
{
int idx=0;
while (idx<n && key[idx] < k)
++idx;
return idx;
}
// A function to remove the key k
void btreenode::remove(int k)
{
int idx = findkey(k);
// check if the key to be removed is present in this node
if (idx < n && key[idx] == k)
{
if (leaf)
removefromleaf(idx);
else
removefromnonleaf(idx);
}
else
{
if (leaf)
{
cout << "The key "<< k <<" is not found in the tree\n";
return;
}
bool flag = ( (idx==n)? true : false );
//If there are less than t keys in the child where the key is expected to exist
if (c[idx]->n < t)
fill(idx);
//We recurse on the (idx-1)th child if the last child has been merged,
//as it must have merged with the preceding child.
//If not, we go back to the (idx)th child, which now contains at least t keys.
if (flag && idx > n)
c[idx-1]->remove(k);
else
c[idx]->remove(k);
}
return;
}
void btreenode::removefromleaf (int idx)
{
// a loop to shift key back
for (int j=idx+1; j<n; ++j)
key[j-1] = key[j];
n--;
return;
}
void btreenode::removefromnonleaf(int idx)
{
int k = key[idx];
//In the subtree rooted at c[idx], look for k's predecessor 'pred'.
//if the child preceding k (C[idx]) contains at least t keys.
//Pred should be substituted for k.
//Delete pred in C[idx] in a recursive manner.
if (c[idx]->n >= t)
{
int pred = getpred(idx);
key[idx] = pred;
c[idx]->remove(pred);
}
//Examine c[idx+1] if the child C[idx] contains less than t keys.
//Find the k's successor 'succ' in the subtree rooted at C[idx+1]
//and replace k with succ if C[idx+1] has at least t keys.
//Delete succ in C[idx+1] in a recursive manner.
else if (c[idx+1]->n >= t)
{
// this getsucc function returns the successor at idx
int succ = getsucc(idx);
key[idx] = succ;
c[idx+1]->remove(succ);
}
//we will merge k and all of c[idx+1] into c[idx]
//if both c[idx] and c[idx+1] have fewer than t keys.
//2t-1 keys now reside in c[idx].
//Remove k from c[idx] by freeing c[idx+1].
else
{
merge(idx);
c[idx]->remove(k);
}
return;
}
// A function to get predecessor of key[idx]
int btreenode::getpred(int idx)
{
// Move to the rightmost node until we get to a leaf.
btreenode *cur=c[idx];
while (!cur->leaf)
cur = cur->c[cur->n];
return cur->key[cur->n-1];
}
int btreenode::getsucc(int idx)
{
btreenode *cur = c[idx+1];
while (!cur->leaf)
cur = cur->c[0];
// Return the first key of the leaf
return cur->key[0];
}
void btreenode::fill(int idx)
{
if (idx!=0 && c[idx-1]->n>=t)
// a function to borrow key from previous node
borrowfromprev(idx);
else if (idx!=n && c[idx+1]->n>=t)
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];
//The parent receives the final key from C[idx-1], and key[idx-1] from
//parent is placed as the first key in C[idx]. As a result, the sibling
//loses one key, and the child receives one.
for (int i=child->n-1; i>=0; --i)
child->key[i+1] = child->key[i];
//All keys in C[idx] are moved one step forward.
//If c[idx] isn't a leaf, advance all of its child pointers one step.
if (!child->leaf)
{
for(int i=child->n; i>=0; --i)
child->c[i+1] = child->c[i];
}
child->key[0] = key[idx-1];
if(!child->leaf)
child->c[0] = sibling->c[sibling->n];
//Shifting the key from a sibling to a parent.
//The number of keys in the sibling is reduced as a result.
key[idx-1] = sibling->key[sibling->n-1];
child->n += 1;
sibling->n -= 1;
return;
}
//A function that takes a key from C[idx+1] and stores it in C[idx].
void btreenode::borrowfromnext(int idx)
{
btreenode *child=c[idx];
btreenode *sibling=c[idx+1];
child->key[(child->n)] = key[idx];
//check if child node has a leaf node
if (!(child->leaf))
child->c[(child->n)+1] = sibling->c[0];
key[idx] = sibling->key[0];
for (int j=1; j<sibling->n; ++j)
sibling->key[j-1] = sibling->key[j];
if (!sibling->leaf)
{
for(int j=1; j<=sibling->n; ++j)
sibling->c[j-1] = sibling->c[j];
}
child->n ++;
sibling->n--;
return;
}
//C[idx] and C[idx+1] are merged with this function.
//After merging, C[idx+1] is freed.
void btreenode::merge(int idx)
{
btreenode *child = c[idx];
btreenode *sibling = c[idx+1];
child->key[t-1] = key[idx];
for (int j=0; j<sibling->n; ++j)
child->key[j+t] = sibling->key[j];
// Copying the child pointers from C[idx+1] to C[idx]
if (!child->leaf)
{
for(int j=0; j<=sibling->n; ++j)
child->c[j+t] = sibling->c[j];
}
//To fill the gap created by shifting keys[idx] to C[idx],
//move all keys following idx in the current node one step before.
for (int i=idx+1; i<n; ++i)
key[i-1] = key[i];
//Moving the child pointers one step
//before (idx+1) in the current node
for (int j=idx+2; j<=n; ++j)
c[j-1] = c[j];
//Updating the current node's key count
//and the child's key count
child->n += sibling->n+1;
n--;
delete(sibling);
return;
}
//A function to separate this node's child y
void btreenode::splitchild(int i, btreenode *y)
{
//Create a new node that will store the keys
`btreenode *z = new btreenode(y->t, y->leaf);
z->n = t - 1;
for (int j = 0; j < t-1; j++)
z->key[j] = y->key[j+t];
if (y->leaf == false)
{
for (int j = 0; j < t; j++)
z->c[j] = y->c[j+t];
}
y->n = t - 1;
//Create a new child space for this node
//since it will have a new child.
for (int j = n; j >= i+1; j--)
c[j+1] = c[j];
c[i+1] = z;
//This node will be moved with a key of y.
//Locate the new key and
//move all larger keys one place forward.
for (int j = n-1; j >= i; j--)
key[j+1] = key[j];
//To this node, copy y's middle key.
key[i] = y->key[t-1];
n++;
}
// A Function to traverse all nodes
void btreenode::traverse()
{
int i;
for (i = 0; i < n; i++)
{
//If this is not a leaf, traverse the subtree rooted
//with child C[i] before printing key[i].
if (leaf == false)
c[i]->traverse();
cout << " " << key[i];
}
// Print the subtree rooted with last child
if (leaf == false)
c[i]->traverse();
}
//A function to search key k in btree
btreenode *btreenode::search(int k)
{
//Find the first key with a value higher or equal to k.
int i = 0;
while (i < n && k > key[i])
i++;
//Return this node if the detected key is equal to k.
if (key[i] == k)
return this;
//If the key isn't found here and the node is a leaf,
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;
}
// A function Call to remove function
root->remove(k);
// Make the first child of the root node the new root
//if the root node has no keys.
//If it has a child, set root to NULL otherwise.
if (root->n==0)
{
btreenode *tmp = root;
//check if root has leaf
if (root->leaf)
root = NULL;
else
root = root->c[0];
delete tmp;
}
return;
}
int main()
{
btree p(3); // A B-Tree with minimum degree 3
p.insert(1);
p.insert(13);
p.insert(7);
p.insert(10);
p.insert(11);
p.insert(6);
p.insert(14);
p.insert(15);
cout << "Traversal of tree constructed is\n";
p.traverse();
cout << endl;
p.remove(6);
cout << "Traversal of tree after deleting 6\n";
p.traverse();
cout << endl;
p.remove(13);
cout << "Traversal of tree after deleting 13\n";
p.traverse();
cout << endl;
return 0;
}
Next Steps
Your next stop in understanding data structures would be "B+ Trees in data structure". A b+ tree is a unique m-way tree data structure. A b+ Tree of order m can have at most m-1 keys and m children. A b+ tree can be used as a b-tree with only keys to each node and with linked leaves to which an additional level is added at the bottom.
Maybe you are looking for more comprehensive learning of software development which can help you forge a strong career in software development. If that is the case, explore Simplilearn's Postgraduate Program in Full Stack Web Development in collaboration with Caltech CTME, the behemoth university in technology education. This coding boot camp program offers the learning, practice, and certifications that you need not just to get work-ready but stand a chance to compete for top software development jobs anywhere in the world.
If you have any questions or need any clarifications regarding this "B-trees in data structures" tutorial, do let us know by leaving them in the comments section you can find at the bottom of this page. Our expert team will review and ensure that they are answered at the earliest.
