Memory and performance optimized prefix tries for NVMM

Indexes are essential in data management systems to increase the speed of data retrievals. Wide-spread data structures to provide fast and memory-efficient indexes are prefix tries and this talk will give an introduction in their use cases and optimization directions for non-volatile main memory (NVMM). Most trie implementations today optimize their internal data alignment for cache and vector unit efficiency. These measures usually improve performance, while having a negative impact on memory efficiency.

We will therefore discuss trade-offs within the design space of trie-based main memory and NVMM key-value stores and present new approaches to achieve extreme space efficiency. The talk compares performance optimized tries with data structures which even optimize their memory allocator to pack each node as efficiently as possible. Such data structures, like the Hyperion search trie, do not depend on CPU vector units, but scan the internal data structures linearly. Interestingly, these linear data structures are able to achieve a competitive point query and an exceptional range query performance, especially for string data sets.