Efficient binary search tree stored in a flat array?

[Paul Rubin]

Douglas Alan <darkwater42 at gmail.com> writes:
> I can't see that a binary search tree would typically have
> particularly good cache-friendliness, so I can't see why a flat-array
> representation, such as is done for a binary heap, would have
> particularly worse cache-reference.

That is a good point.  Maybe we should be paying more attention to
cache-oblivious algorithms.

  http://en.wikipedia.org/wiki/Cache-oblivious_algorithm

H. Prokop's masters' thesis cited in the wiki article explains the
subject very well.  A fair amount of work has been done on it since
then, but not as much as one might expect.