Comment by ztorkelson
8 years ago
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.
Yes, exactly. It would of course be trivial to unlink a node without reclaiming it, but then you're leaking.
Radix trees never rotate, right? Can that be leveraged to help with locality?