Deletion from a B-Tree
Deleting is all about rebalancing.
Reference
Contributors to Wikimedia projects
Deleting from a Leaf Node
Right Rotation
If a node becomes deficient after you delete an item in it, pull a key-value pair from its parent and move the last element of the left node to the vacancy in the parent node. This operation is called right rotation. Note that it is only possible if the left sibling has more items than the minimum number of items per node. There is a counter-clockwise version of it, called left rotation.
Merge
If both of the siblings have no more than the minimum number of items per node, we cannot conduct a rotation. In such a case, we merge leaves. Move all the elements in the leaf (or right) node and the key-value pair in the parent to the left sibling. Then, shift items in the parent node. Note that after a merge, the parent has fewer items. So, you might have to compensate for it. Actually, you can perform the same kind of operations for parent nodes. Repeat the compensation process up to the root node.
Deleting from an Inner Node
If you find the key to delete in the middle of the B-Tree, follow the pointers down to find the immediate smaller key. There is always such a key due to B-Tree's construction. Replace the deleting key and its value with that of the immediate smaller key and its value.
The node that used to hold the immediate smaller key now has fewer items. If it is deficient, perform compensating operations described in the previous section.
