Depth first or breadth first ordering in binary search trees?
Think about what happens when you move from one layer in the tree to the next. When you start getting to layers with progressively more nodes, you'll eventually get to a spot where the layers are so big that they can't fit into memory caches. When that happens, if you've laid out the memory in a BFS order, then going from one layer to the next will almost always cause a cache miss because the memory fetched for the first layer won't include the node from the next layer in it. In other words, every link followed will cause a cache miss. On the other hand, if you use DFS order, then the memory for the nodes will have the nodes broken apart into smaller chains of nodes corresponding to the paths taken by DFS. If you do lookups in a way that follows those chains, it's possible that you'll have no cache misses at all when going from one node to the next, which can dramatically speed up lookups.

The ordering I've actually heard most for making cache-friendly BSTs is the van Emde Boas layout, which is formed as follows:


If the tree has height two or less, lay it out in DFS or BFS order (they're the same here).
Otherwise, split the tree at the middle level into a "top tree" of the first half of the nodes and up to $\sqrt{n}$ "bottom trees" formed from the lower levels. Recursively compute the van Emde Boas layouts of each of these trees, then concatenate them together in order.


You can prove that this layout is optimal assuming that you don't know anything about the particular sizes of the caches of the machines in the computer (it's known as a cache-oblivious data structure).

If you do know the cache size, though, the "best" choice is probably to use a B-tree instead of a BST, since B-trees are specifically designed to play nicely with caches. Although they were designed for on-disk storage, they work really well in main memory, as some recent work has shown.