3 ms·

This paper is very well laid out and a joy to read. The conclusion seems to be that Adaptive Radix Trees [1] outperform all b-tree variants, skiplists and Mass

This paper is very well laid out and a joy to read. The conclusion seems to be that Adaptive Radix Trees [1] outperform all b-tree variants, skiplists and Masstree [2] for all ops except range scans. The claim is more credible if one considers that the authors of this paper are not the authors of [1]. Since ARTs are significantly faster, it would be nice to throw in the benchmarking mix one hash map as well, such as dense_hash_map<>, if only to see what is currently the gap between ordered and unordered containers. [1] https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6544812 https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=654... [2] a hybrid trie/B+tree data structure

rurban 8y ago
ART is just another Judy variant. And they being faster than a hash table is popular myth, but wrong. They are only faster than a very bad hash table. The linux page table implementation as hash e.g. would be much faster than the current radix tree plus cache. The Power CPU e.g uses a hash, not an ART for it's page table cache. A Comparison of Adaptive Radix Trees and Hash Tables - Big Data Analytics PDF https://bigdata.uni-saarland.de https://bigdata.uni-saarland.de › ARCD15
- utopcell 8y ago
  Thank you for the reference [1]. Maybe I missed something on the post's paper, but I don't think they make any claims wrt ARTs and hash tables. They do seem to conclude that ARTs are better than the ordered containers they compared them against. [1] https://bigdata.uni-saarland.de/publications/ARCD15.pdf https://bigdata.uni-saarland.de/publications/ARCD15.pdf