ART radix trie

Main paper can be found here and its condensed version is in this blog.

  • create a sort of 'union' struct with different nodes
  • they support a different struct for upto 4, 16, 48, 256 children per nodes
    • Node4: one can do a brute search on its contents
    • Node16: sort its children and do binary search
    • Node48: store the children indexed with a 256 element array itself
    • Node256: the usual radix trie
  • these data structures help improve L1 cache locality
  • they have a paper on parallel ART: https://db.in.tum.de/~leis/papers/artsync.pdf