[sambeau]

I'd take his word for it as my tests are 10 years old!

And my apologies - looking back it was Patricia trees I was using as you can take a pointer to a mid-point in the path: useful for disk caches etc.

I was using them for small dictionaries (mainly symbol table-size structures) comparing them against an early super-fast hash (and I recall for really small dictionaries linear search as I naively assumed that a linear search would win for tiny dictionaries - it didn't). In all my tests then (as I say, 2003, on a 3 year old IBM Thinkpad) the tries won.