Explain Insertion and Deletion Operation in a B-Tree | Data Structure Tutorial

In this article, you will learn about the insertion and deletion operation in a B-Tree.

Insertion Operation

Elements can be inserted on a B-Tree in two ways:

• Searching for the particular node to add the element. 
• Splitting the node if necessary. 

Insertion can be done only in one way which is a bottom-up approach. 

Insertion Operation can be done in the following way:

1. If there is no element in the tree, allocate a root node and insert the key. 
2. Update the allowed number of keys in the node.
3. Search for a particular node for insertion. 
4. If the node is full, then follow the below steps
5. Insert the elements in increasing order.
6. Now, there are elements larger than their limit. So, split at the median. 
7. Push the median key upwards and the left child is considered as a left key and THE right child is considered as a right key. 
8. If the node is not complete, then follow the last step. 
9. Now, insert the node in increasing order.

Deletion Operation

The steps required to delete an element from a B-Tee are:

• Search for the node where the key has to be deleted.
• Delete the key
• Balance the tree if necessary.

While deleting a tree, a condition known as underflow may occur. Underflow condition occurs when a node has less than the minimum number of keys it should hold.

The terms that need to know before performing the deletion operation are:

1. Inorder Predecessor: The largest key on the left child of a node is known as the inorder predecessor.
2. Inorder Successor: The smallest key on the right child of a node is known as the inorder successor.

Deletion Operation

The steps required to delete the element are:

1. A node can have a maximum of m children.
2. A node can have a maximum of (m-1) keys.
3. A node should have a minimum of [m/2] children.
4. A node except the root node should have a minimum of [m-2] - 1 key.