...
Tried this with off-the-shelf radix tree that claims to be fast and cache optimized (Judy): with 2^20 nodes average lookup time of about 1000 cycles on an AMD64 and 520 cycles on a recent Core 2 Duo and a Xeon, allocated 15 MB of RAM during inserts. This doesn't account for cache pressure from the actual data accesses at all.
B-Trees
- + Supports range queries on totally ordered keys
- +/- Allows several records from the same table to be returned with a single request
- Can give control over placement if they can take advantage of it for locality
- May cause a server to become a hot spot
- Is this anymore true than with hashing?
- - Latency (at least as bad as DHT)
...