Insertion Algorithm: Splitting Nodes

if the leaf page has 2m+1 items after the insertion then



• create a new page with m items
• insert the pointer of the new page and the first item in the parent directory

2 5 7 8

13 14 15 18

22 24

32 35 38

40 42 45 46

13 22

29 32 40

26

Insert 30

26 27 28

29 30

26 27 28 29 30

26 27 28

29 30

32 40

Insert 29 and

pointer

Previous slide

Next slide

Back to first slide

View graphic version