B+-tree

Idea:
  • like B-tree but all values are stored in leaves
  • internal nodes store copies of keys and are used for navigation but don't store any data
Advantages:
  • since internal nodes store no data, we can pack more keys in the same space ⇒ higher branching factor ⇒ smaller depth ⇒ faster search
  • since all values are in leaves, iterating them is much easier and faster than the tree traversal in B-trees
Disadvantages:
  • extra copies of keys take more space — this is more suitable when keys are small and easy to copy

References

  • R. Bayer and E.M. McCreight. Organization and maintenance of large ordered indexes. Acta informatica, 1(3):173-189, 1972. [bib] [pdf]
  • D. Comer. Ubiquitous B-tree. ACM Computing Surveys (CSUR), 11(2):121-137, 1979. [bib]