Re:The Trie: A Neglected Data Structure
by swannodette on Friday September 13, 2013 @12:22PM
(#6381439)
It depends on the kind of trie that you build - it's worth taking a look at Hash Array Mapped Tries http://lampwww.epfl.ch/papers/idealhashtrees.pdf
The Clojure programming language is completely designed around several immutable variants.
See also: HAT-trie by Askitis and Sinha.
Tries are the fastest tree-based data structures for managing strings in-memory, but are space-intensive. The burst-trie is almost as fast but reduces space by collapsing trie-chains into buckets. This is not however, a cache-conscious approach and can lead to poor performance on current processors. In this paper, we introduce the HAT-trie, a cache-conscious trie-based data structure that is formed by carefully combining existing components.
A B-Tree is better due to better exploitation of locality of reference in memory.