Sticky tries
Pramod G. Joisha · 2014
We present the sticky trie, a new variant of the standard trie data structure that achieves high-performing atomic insertions and lookups for large key universes by precluding deletions. It has applications in several areas, including address tracking, logging, and garbage collection. By leveraging features of a modern operating system, we show how a runtime can exploit the absence of deletions to realize an efficient sticky-trie implementation.