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