A "simple" memory layout for cache friendliness (assuming you don't have to do updates on your tree; there exists a more complicated cache-friendly dynamic tree

A "simple" memory layout for cache friendliness (assuming you don't have to do updates on your tree; there exists a more complicated cache-friendly dynamic tree structure, too) is a recursive van Emde Boas layout. This memory layout will achieve performance no more than a (small) constant multiple worse than an omniscent cache in terms of the number of cache misses, and it requires almost no tuning to work in any caching hierarchy. http://supertech.csail.mit.edu/cacheObliviousBTree.html http://supertech.csail.mit.edu/cacheObliviousBTree.html More generally: in the last 10-15 years there has been a lot of work on developing algorithms that are compatible with caching, but which do not need to be tuned to the details of a particular cache hierarchy on which they run. For more info, see Demaine, Erik D. "Cache-Oblivious Algorithms and Data Structures." http://erikdemaine.org/papers/BRICS2002/paper.pdf http://erikdemaine.org/papers/BRICS2002/paper.pdf Erik Demaine's 6.046 lectures on this topic are available on YouTube: https://www.youtube.com/watch?v=cJOHERGcGm4 https://www.youtube.com/watch?v=cJOHERGcGm4 and https://www.youtube.com/watch?v=zjUDy6a5vx4 https://www.youtube.com/watch?v=zjUDy6a5vx4 One cache-oblivious dynamic tree structure is also due to Demaine: http://erikdemaine.org/papers/CacheObliviousBTrees_SICOMP/ http://erikdemaine.org/papers/CacheObliviousBTrees_SICOMP/