I'm only commenting because of the "job interview" comment, but when someone compares hash tables to B-trees, I usually assume (fairly or not) that they don't really know what a B-tree is.
Ah, thanks for clarifying. I had to implement a B+-tree using only a 2D byte array as a sophomore, so I don't think I'll ever be able to forget how they work.
It's possible. There are parallels between main memory and disks. A disk seek gets you hundreds or thousands of bytes and requires (blocking for) millions of cpu cycles; a cache line fill gets you 64 (sometimes) bytes and requires (spinning for) hundreds of cpu cycles. You want to minimize both of those, but with memory, the difference is much less dramatic.
Well, you can walk spatial partitions with trees in ways that become clunky with hashes (taking a branch means all children are 'near' each other). Also, B-trees might work better in cached architectures -- this is certainly true with respect to disk accesses but I'm not sure if that carries over to L3/L2/L1 cache.
B-Trees actually have superior cache performance compared to other types of trees (such as T-Trees or BST Trees). In part, this is because B-Trees have a higher density of actual data to pointers.
There is a tradeoff of computation (doing binary search inside the node) and amount of storage (keeping less pointers). In environments where memory access is much more expensive than a CPU instruction, it is preferable to perform these computations than to have to read all the extra pointer data to jump to the right places.
In fact, a breed of cache-friendly data structures are precisely based on the B+Trees but with even less pointers, having the algorithm compute these pointers instead (CSS-, CSB-Trees)
It does carry over to L3/L2/L1 cache, but only if the tree is designed to benefit from that. See http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-obli... for one strategy to do that. (With that structure lookups become faster, but walking the tree in order becomes difficult.)
This is a really great article and I wish I could give you some more points to make this appear higher. I once used a cache-oblivious matrix transpose algorithm that was startlingly simple and effective but I didn't know the approach had been so widely applied. Thanks!
