Logo
×

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 
Present

Deletion 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;
}

Related Topics

Conversion of ER Diagram into Relational Model

After designing the Entity-Relationship diagram, you need to convert it into tables in the relational model. Because the relational model can be easily implemented by the Relational DBMS like Oracle, MySQL, etc....

2 minutes read.

Redundancy in Database Management System

Redundancy in a database management system (DBMS) refers to the duplication of data within the database. This duplication can occur in multiple ways, such as having multiple copies of the...

13 minutes read.

Red-Black Tree Deletion in DBMS

Introduction To Red Black Tree Each node's extra bit in a red-black tree, a type of self-balancing binary search tree, is frequently understood as the color (red or black). The balance...

3 minutes read.

DBMS Generalization, Specialization, and Aggregation

DBMS Generalization Generalization is a bottom-up approach in which the common attributes of two or more lower-level entities combines to form a new higher-level entity. In generalization, the generalized entity of higher level can also...

3 minutes read.

B-Tree Insertion in DBMS

A B-tree is a special type of m-way tree, commonly used for disk access. A B-tree of order m can have at most m-1 keys and m descendants. B-trees are...

4 minutes read.

What is RDBMS?

To discuss the Relational Database Management System, there are some terms and concepts you need to know. Database Any collection of related information is called a database. The phone book is...

5 minutes read.

Inference Rules

Armstrong’s axioms are the complete set of basic inference rules used to infer all the functional dependencies on the relational database. An inference rule is a type of assertion that a user can...

2 minutes read.

Advantages of DBMS

A Database Management System (DBMS) is a collection of programs which lets the end-users to manage and control the database. Database systems use query language for accessing, storing, and maintaining the...

3 minutes read.

What is Non-Relational Database

Databases can be sorted as either relational or non-relational. Non-relational data sets are now and again alluded to as "NoSQL," which represents Not Only SQL. The principal difference between these...

4 minutes read.

B+ (Plus) Tree in DBMS

What is a B+ tree? The B+ tree is known as a balanced binary search tree. in this tree, we can store the data in the form of nodes. B+ tree...

9 minutes read.

Advantages of Threaded Binary Tree in DBMS

We know that every node in a binary tree contains both its data value and the address pointers for its left and right children. A null pointer is used to...

3 minutes read.

How to draw ER-Diagram in DBMS?

Entity Relationship Diagrams, or ERDs, are diagrams that assist you in visualizing your database design. An ERD, also called anER diagram or ER model,describes data and how parts of the data interact. ERDs are crucial in database architecture and projects that call for...

9 minutes read.

Constraints in Database Management System

In a database management system, certain constraints are applied while performing any operation on the database to ensure that the integrity and quality of the data are maintained throughout the...

4 minutes read.

Relational Algebra in DBMS

Relational Algebra is a widely used procedural query language, which takes instances of one or more relation as an input and generates a new relation as an output. It uses a different...

6 minutes read.

DBMS Examples

Introduction to DBMS A database management system (DBMS) is a software application that is designed to manage and organize data stored in a database. It is responsible for storing, retrieving, and...

4 minutes read.

ER Diagram of Company Database in DBMS

Entity Relationship Diagram Entity Relationship Diagrams, or ER Diagrams for short, are diagrams that show the relationships among entity sets that are stored in databases. Alternatively said, ER diagrams assist in...

3 minutes read.

Query optimization in DBMS

Choosing an effective execution strategy to execute a query is a process known as query optimization. After the decision-making process of query parsing, which determines how many distinct ways a given...

5 minutes read.

Advantages of RDBMS

The relational database management system collects related data stored in tabular format. The data is stored in rows and columns, where rows usually represent the individual entity of the collected...

6 minutes read.

Redundancy in DBMS

Data redundancy is a situation that is created in the database in which the same amount of data is stored in two different places. The different places are found in a...

3 minutes read.

Types of DBMS

Database Management System A software that is programmed to enable the user to create and maintain a database. Using DBMS, we can implement create, read, update and delete operations on the...

4 minutes read.