[saurik]

So, a "binary search tree in an array, like the way heaps are implemented" actually would not experience the problem described in this article. The typical layout of the tree for a heap is "breadth-first, level-order" as opposed to the "depth-first, in-order" tree that is implicit to a sorted array. This means that your accesses to the first couple levels are in the same cache line, and your subsequence accesses as you move down the tree are less likely to line up. This is definitely not to say this is "optimal", however.