You are technically correct. My words were imprecise -- indexing into a B-tree does not require accessing the harddrive. But it is a rather large possibility,

You are technically correct. My words were imprecise -- indexing into a B-tree does not require accessing the harddrive. But it is a rather large possibility, and it's something to be aware of. From Wikipedia ( http://en.wikipedia.org/wiki/B-tree http://en.wikipedia.org/wiki/B-tree ): "B-trees have substantial advantages over alternative implementations when node access times far exceed access times within nodes. This usually occurs when most nodes are in secondary storage such as hard drives. By maximizing the number of child nodes within each internal node, the height of the tree decreases, balancing occurs less often, and efficiency increases. Usually this value is set such that each node takes up a full disk block or an analogous size in secondary storage. While 2-3 B-trees might be useful in main memory, and are certainly easier to explain, if the node sizes are tuned to the size of a disk block, the result might be a 257-513 B-tree (where the sizes are related to larger powers of 2)." So yes, "there's no reason that a b-tree must be stored on a hard drive". There's also no reason why a car couldn't also have a built-in toaster. :) As far as in-memory data structures go, there are better choices than B-trees. Why use a suboptimal data structure?