Deletion of a key from a B-tree is similar to insertion, except that insertion leads to overflow, and deletion leads to underflow. The deletion of a key begins with the deletion of the key from its leaf node. There are several additional steps:
If the number of keys that remain in the node is less than the minimum (an underflow condition):
Move one or more keys from a sibling node so that both the original and the sibling node have at least the minimum number of keys.
If the sibling nodes also have the minimum number of nodes, merge the original node and node of its siblings into a single node.
If the largest key in any node has changed, replace the corresponding key in the parent node with the largest key in the child node.
If a node was deleted as a result of Step 1, delete the corresponding key in its parent node and repeat Steps 1–3 for that node.
If the root node has only one child, delete the root node and make its child become the root. Reduce the height of the tree by 1.
The figure on the right shows a B-tree and we will use it to demonstrate the deletions.
