B TREE in Data Structure: Search, Insert, Delete Operation Example

Details

What is a B Tree?

B Tree is a self-balancing data structure based on a specific set of rules for searching, inserting, and deleting the data in a faster and memory efficient way. In order to achieve this, the following rules are followed to create a B Tree.

A B-Tree is a special kind of tree in a data structure. In 1972, this method was first introduced by McCreight, and Bayer named it Height Balanced m-way Search Tree. It helps you to preserves data sorted and allowed various operations like Insertion, searching, and deletion in less time.

In this B-Tree tutorial, you will learn:

Rules for B-Tree

Here, are important rules for creating B_Tree

Why use B-Tree

Here, are reasons of using B-Tree

History of B Tree

Search Operation

The search operation is the simplest operation on B Tree.

The following algorithm is applied:

Insert Operation

Since B Tree is a self-balancing tree, you cannot force insert a key into just any node.

The following algorithm applies:

TIP

The following is not true about the insertion algorithm:

Since the node is full, therefore it will split, and then a new value will be inserted

In the above example:

In the above example:

In the above example:

Similarly, 13 and 2 can be inserted easily in the node as they fulfill less than max keys rule for the nodes.

In the above example:

Similarly, based on the above rules and cases, the rest of the values can be inserted easily in the B Tree.

Delete Operation

The delete operation has more rules than insert and search operations.

The following algorithm applies:

If the target key is in the leaf node

If the target key is in an internal node

If the target key is in a root node

Now, let's understand the delete operation with an example.

The above diagram displays different cases of delete operation in a B-Tree. This B-Tree is of order 5, which means that the minimum number of child nodes any node can have is 3, and the maximum number of child nodes any node can have is 5. Whereas the minimum and a maximum number of keys any node can have are 2 and 4, respectively.

In the above example:

In the above example:

Now, the following diagram explains how to delete this key:

The following example illustrates how to delete a key that needs a value from its in-order successor.

In the example below, the target node does not have any sibling that can give its key to the target node. Therefore, merging is required.

See the procedure of deleting such a key:

Delete Operation Pseudo Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

Output:

The biggest element is deleted from the B-Tree.

Summary:

 

YOU MIGHT LIKE: