Researching a New NSD Database: Adaptive Radix Tree

NLnet Labs' authoritative nameserver NSD currently supports two different data structures for its main memory database: red-black tree en radix tree. Both data structures have their strengths and weaknesses, red-black tree implementation is more memory efficient and the radix tree is more performant (faster). Jeroen Koekkoek explores a new data structure for NSD database, namely adaptive radix tree. This data structure was proposed in 2013 and is designed for modern computer systems for which it offers great performance and space efficiency.

Jeroen has written a blog post where he introduces the adaptive radix tree and details how the data structure can be used for a nametree and what design decisions have been made to fit the nametree on modern CPUs with SIMD instruction support.