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

ER Diagram for University Database in DBMS

What is an ER diagram? ER diagram, short for Entity Relationship Diagram, also known as ERD, is a diagram that shows the relationships of a set of entities stored in a...

9 minutes read.

Three Schema Architecture of DBMS

The three schema architecture describes how the data is represented or viewed by the user in the database. This architecture is also known as three-level architecture and is sometimes called...

3 minutes read.

Cardinality in DBMS

Cardinality in DBMS Cardinality is the relationship between two or more entities (table). It shows how all the entities are connected. In DBMS, all the entities and tables are interconnected with...

2 minutes read.

Applications of DBMS

There are various fields where a database management system is used. Following are some applications which make use of the database management system: 1. Railway Reservation System: In the railway reservation...

7 minutes read.

Data Abstraction in DBMS

Introduction Data abstraction is a fundamental concept in database management systems (DBMS). It refers to the process of hiding the details of how data is stored and retrieved from the user,...

3 minutes read.

Data Models in DBMS

Data Models in DBMS Data models are the models explaining the logical structure of the database systems. They describe the entities, attributes, and the relationship among the data elements of the...

8 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.

States of Transaction in DBMS

Transaction States A transaction passes through many different states in its life cycle. These states are known as transaction states. A transaction can be in one of the following states in the database: Active statePartially...

3 minutes read.

Difference between Dropbox and Amazon Drive

What is Dropbox? It is a file organising company that is owned by the American Company Dropbox Inc. Itsheadquarters is situated in San Francisco, California, U.S. Dropbox offers personal cloud, client...

3 minutes read.

ER Diagram for Company Database in DBMS

What is ER Diagram? An ER diagram (short for Entity Relationship Diagram), also known as an ERD, is a diagram that shows the relationships of a set of entities stored in...

7 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.

Advantages of Database Management System in DBMS

A database management system (DBMS) is a software tool that provides an interface for managing data stored in a database. Some advantages of using a DBMS include: data integration, data...

3 minutes read.

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 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.

Components of DBMS

The database management system (DBMS) represents an essential tool for processing data within effectively structured structures. The database management system consists of important components that work together to maintain the...

6 minutes read.

Red-Black Tree Properties in DBMS

What is a Red-Black Tree? A red-black tree is a kind of self-balancing binary search tree. The extra bit that each node keeps denoting "color"-either "red" or "black"-is needed to keep...

3 minutes read.

Fundamentals Of Distributed DBMS

Fundamentals of DDBMS Here we are going to talk about the Fundamentals of DDBMS. But first, we need to know about Distributed databases to understand the Distributed Database Management System. Distributed Database: It is...

4 minutes read.

DBMS Schedule

A schedule is a process of combining the multiple transactions into one and executing the operations of these transactions in a predefined order. A schedule can have multiple transactions in it, each transaction...

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.