...
Tried this with off-the-shelf radix tree that claims to be fast and cache optimized: with 2^20 nodes average lookup time of about 3300 cycles (e.g. about 1 us)on an AMD64 and 524 cycles on a Core 2 Duo
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)
...