# Deletion In B-Trees

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.

Example

Consider a B-tree of Fig 1.Say we want to delete 2,21,10,3 and 4 step by step from the tree.

Delete 2

• 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)

Delete 21

• 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.

Delete 10

• 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).

Delete 3

• Deletion of 3 causes 4 to move in a (Fig 5).

Delete 4

• Deletion of 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).
Rate this post