In order to delete elements from B-Tree we need to ensure that their properties(Refer : http://letslearncs.com/b-trees/ does not get violated.It should remain a binary search tree and number of pointers must be according to the order and keys should be one less than the order in each and every node.
Consider a B-tree of Fig 1.Say we want to delete 2,21,10,3 and 4 step by step from the tree.
- 2 is present in node b.Deletion of 2 do not violate any property of B-tree,so we delete 2 directly from node b.(Fig 2)
- Deletion of 21 cannot be done directly.It causes node e to underflow so elements are redistributed among c,g and e(Fig 3).
- 10 remains in c.
- 12 is stored in g and 13 is stored in e.
- Deletion of 10 again cannot be done directly.It causes node c to underflow which further causes parent node g to combine with f and a and tree shrinks by one level.3,7 and 9 are stored in a,1 in b,4 and 5 in d,8 in h ,12 and 13 in e (Fig 4).
- Deletion of 3 causes 4 to move in a (Fig 5).
- Deletion of 4 needs redistribution of the keys in the subtrees of 4; however, nodes b and d do not have enough keys to redistribute without causing an underflow. Thus, nodes b and d are combined together(Fig 6).