...
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 allEven with some cache pressure (1000 lines touched randomly) still responds in about 1800 cycles.
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)
...