Deletion: The Case for Transferring Items From Siblings

if the leaf page B where x appears has m items

if there is a neighbor B’ (left or right) with >m items
then transfer the first (or the last item) of B’ to B

and update the appropriate ancestors of B

2 5 7 8

13 14 15 18

18 24

27 28

35 38

40 42 45 46

13 18

35 40

27

Delete 22

* transfer the last element of the left neighbor or the first of the right neigbor

Previous slide

Next slide

Back to first slide

View graphic version