Re:God: Scalable in Memory Data Structure Server in Go
by amalcon on Tuesday February 05, 2013 @08:47PM
(#5174462)
Radix trees are great, with the right workload. The main competition (for strings) are the ternary search tree (for sparse keyspaces with rare insertions) and the B-Tree (which is nominally disk-optimized, but that optimization also tends to help with the L3 cache).
None of those are best for all workloads. There are situations where using a radix-tree is actually faster than a hashtable with a good hash function, and situations where it is slower than a red-black tree.
None of those are best for all workloads. There are situations where using a radix-tree is actually faster than a hashtable with a good hash function, and situations where it is slower than a red-black tree.