Slide 1.9: A short history of file structure design
Slide 1.11: B+ trees
Home

A Short History of File Structure Design (Cont.)

1960s (AVL Trees)
Again, trees can grow very unevenly as records are added and deleted, resulting in long searches requiring many disk accesses to find a record. An AVL tree was proposed to solve the problem. It is a self-adjusting binary tree structure and is defined as follows:
A balanced binary tree where the height of the two subtrees (children) of a node differs by at most one.

Clearly, the binary search tree becomes more efficient if the item insertion and removal algorithms are modified in such way that a certain amount of balancing is guaranteed. The colored nodes are those that do not obey to the AVL rule.  
AVL trees


Not AVL trees


1970s (B-Trees)
The problem was that even with a balanced binary tree, dozens of accesses were required to find a record in even moderate-sized files. A method was needed to keep a tree balanced when each node of the tree was not a single record, as in a binary tree, but a file block containing dozens, perhaps even hundreds, of records. A B-tree was proposed to meet the requirements and is defined as follows: