Trees on Disk

• In the 60s people considered using trees for disk files

• Trees can be grow in unbalanced patterns yielding slow access

• In 1963 AVL trees were developed
  balanced binary trees
  but even balanced binary trees are a little slow on disk

• Balanced trees with greater branching were needed

• In 1972 Bayer wrote about B-trees which solved the problem

• B+trees were developed to keep a linked list along with the B-tree