PPT Slide

Deletion: The Case for Combining Pages

if the leaf page B where x appears has m items

if there is a neighbor B’ (left or right) with >m items
then … (see previous page)

else combine B with a neigbor B’
delete from parent of B the first item of
the rightmost of B and B’

2 5 7 8

13 14 15

18 24

27 35 38

40 42 45 46

13 18

35 40

27

Delete 28

* the deletion from parent may ripple recursively

Delete 35 from

inner node

Previous slide

Next slide

Back to first slide

View graphic version