B Trees
Fun fact: it's a mystery, but the B could stand for Boeing, Balanced, or Bayer (co-inventor).
In practice, B-Trees are widely used in databases.
Most modern filesystems use B-trees (or Variants).
In addition to its use in databases, the B-tree is also used in filesystems to allow quick random access to an arbitrary block in a particular file.
The basic problem is turning the file block i address into a disk block (or perhaps to a cylinder-head-sector) address.
Memory Hierarchy Models- MIT 6.851 (video)
- covers cache-oblivious B-Trees, very interesting data structures
- the first 37 minutes are very technical, may be skipped (B is block size, cache line size)