The B-Tree Variant: B+-Tree Remains the Winner

• Avoid storing the same item at multiple levels

  • saves space (but who cares?)
  • non-leaf and leaf nodes contain different numbers of nodes
  • deletion more complicated
  • [Korth&Silberschatz] claims faster lookup for B-Trees because the height of the tree is smaller (because items are stored more compactly). Why this is false ?

2 5 7 8

13 14 15 18

22 24

26 27 28

32 35 38

40 42 45 46

12 21

30 39

25

Previous slide

Next slide

Back to first slide

View graphic version