[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.