[rewmie]

It might be of interest to anyone that there's an implicit binary tree data structure dubbed Eytzinger's tree/method that only requires a single vector.

https://opendatastructures.org/ods-cpp/10_1_Implicit_Binary_...

I dare say that no tree data structure beats Eytzinger's method in cache locality.

[amluto]

> I dare say that no tree data structure beats Eytzinger's method in cache locality

Cache locality is good toward the leaves and bad everywhere else. This is why binary search on a sorted array is actually quite slow.

ORC in Linux, for example, was first prototyped as a sorted array of little structures. It got much faster by adding an auxiliary index giving O(1) access to a credible starting point for a search.

[funcDropShadow]

> Cache locality is good toward the leaves and bad everywhere else.

1. That depends on the operation performed. I'd say cache-locality is near perfect for depth-traversal.

2. Whether the effective performance of the cache is good or bad depends on the alternative. If the alternative is adding two 64 bit pointer to every 32 bit value in the tree node. And each of those node may be spread through out the heap. Then this representation starts to look quite good.

[ulatich]

There is also the “Binary Ostensibly-Implicit Tree”. Like Eytzinger‘s tree/method but without the need to pad memory. Generalises to n-ary trees too.

[bjourne]

Van Emde Boas trees are asymptotically cache optimal. In practice when cache sizes are known they may be slower than other tree types however.