[yjh0502]

Adaptive radix tree (https://github.com/armon/libart) is also an impressive data structure. It also supports ordered iterations while showing similar random read/write performance to hash tables. Crit-bit tree is memory efficient, but it suffers for cache misses with many keys (> 1M).

[eloff]

That's the problem I see, it's memory efficient, but lookups will cost thousands of cycles for modestly sized trees. A hash table on the other hand can do lookups in a couple hundred cycles (cold cache for both.)

[sprachspiel]

But cold caches are an unrealistic assumption. The top-most levels of a tree will always be in cache, unless you almost never access them -- in which case there's no problem either. Additionally, a radix tree is ordered, whereas a hash table is not.

[eloff]

Yes, that's correct. However, that's still over a thousand cycles for a tree of depth 5 below the cached part. That's a modestly sized tree (or several smaller trees.) Don't forget lot's of things compete for cache, it's usually safer to assume a cold cache unless you know your data structure is very high traffic.