Explain Insertion and deletion Operation on a B+ Tree | Data Structure Tutorial

In this article, you will understand the two operations on a B+ tree i.e insertion and deletion.

How to perform the Insertion Operation into a B+ Tree?

The events consisting to insert an element into a B+ tree are:

• Searching the particular Leaf.
• Inserting an element into a B+ tree.
• Balancing or splitting the tree

Insertion Operation

The properties needed to be kept in mind before inserting an element into a B+ tree:

• The root node has at least two children.
• Each node of the tree except the root node has a maximum of m children and at least [m/2] - 1 key.
• Each node of the tree can contain a maximum of m-1 keys and a minimum of [m/2]-1 keys.

To insert an element, these steps need to be followed:

1. Since each element is inserted into a leaf node, go to the particular leaf node.
2. Insert the key into that leaf node.

Case I

1. If the leaf node is not null, insert the key into the leaf node in increasing order.

Case II

1. If the leaf node is full, then insert the key into the leaf node in increasing order and then balance the value of the tree in the following way.
2. Break the node at the m/2th position. 
3. Insert the m/2th key at the position of the parent node.
4. If the parent node is complete, then again execute the 2 to 3 steps.

How to perform the Deletion Operation from a B+ Tree?

The events consist to delete an element from a B+ Tree:

• Search for the node where that key needs to be deleted.
• Deleting the key from the tree.
• Balance the tree if necessary

In the delete operation, the underflow condition can happen. Underflow is a situation when the tree is holding the least number of keys in a node than the minimum number of keys it should hold. 

Deletion Operation

The things you should know is B+ tree has a degree m:

• A node can have a maximum of m children.
• A node can have a maximum of m-1 keys.
• A node must have a minimum of [m/2] children.
• A node (apart from a root node) should have a minimum of [m/2]-1 keys.

Find out the key to be deleted in the following way:

CASE I: The key that needs to be deleted is always present only at the leaf node not on any of the internal nodes. There are two cases for it:

1. If there are more keys than the minimum number of keys in the node. Then simply delete the key.
2. If there is an exact minimum number of keys in the node. Delete the key and borrow a key from the corresponding. Add the median key of the sibling node to the particular parent.

CASE II: The deleted key needs to be present in the internal nodes as well. Now, we have to remove the key from the internal nodes as well. The following cases of this particular situation are:

1. If there are more keys than the minimum number of keys in the node, simply delete the key from the leaf node and delete the key from the internal node as well. Fill up the space in the internal node with the inorder successor.
2. If there is an exact minimum number of keys in the node, then delete the key from the tree and borrow a key from its corresponding sibling. Fill up the space created in the internal node with the borrowed key.