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.
> 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.
> 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.
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.