This is getting deep into some wizardry, but if you used a custom pool-like allocator you could group contents close together in cache, and, if necessary/appropriate, even rearrange the elements in the container to be more cache-friendly for your purposes.
You could, but the premise of using a tree was to avoid unpredictable rehashing latency, if you start compacting the tree every now and then, you basically pay the same price.
Right. When you ask "how could we support deletion of nodes", am I right to assume you mean "how could we reclaim memory of deleted nodes"?
Conventionally, a free list would be used, though admittedly that sacrifices locality which was one of the original motivating factors. To the extent that deletion is a significant component of the workload, then yeah, this doesn't help.