Trie
前缀树或字典树，是一种有序树，其发明者 Edward Fredkin 把它读作/ˈtriː/ "tree"，但更多人把它读作/ˈtraɪ/ "try"。朴素的 Trie 由于存储稀疏，存在空间利用率低下的问题。Radix tree (又被称为 radix trie、压缩前缀树、compressed trie) 将作为唯一子节点的每个节点都与其父节点合并，是一种更节省空间的前缀树，Rax 是一个 Radix tree 的 C 语言实现。
- The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases
- HOT: A Height Optimized Trie Index for Main-Memory Database Systems
Optional readings
- V. Alvarez, et al., A Comparison of Adaptive Radix Trees and Hash Tables, in ICDE, 2015
- Viktor Leis, et al., The ART of Practical Synchronization, DaMoN '16. 介绍了 ART 实现中使用的两种多线程同步技术 — 1) OPTIMISTIC LOCK COUPLING 2) READ-OPTIMIZED WRITE EXCLUSION (ROWEX)
References
- Trie
- Radix tree
- Trees I: Radix trees by J. Corbert, 2006