I don't remember the reference but I read a comprehensive comparison
between various indexing methods about a year ago and the splay tree
did considerably better than a RB-tree. The RB-tree actually did
fairly poorly.
Any binary tree-like structure makes fairly poor use of cpu caches.
Splay trees work somewhat better as long as there is some locality
of reference in the lookups, since the node being looked up is moved
to the root. It isn't a bad trade-off.
On the negative side all binary-tree-like structures tend to be
difficult to MP-lock in a fine-grained manner (not that very many
structures are locked at that fine a grain anyway, but it's a data
point). Splay-trees are impossible to lock at a fine-grain due to
the massive modifications made on any search and the movement
of the root, and there are MP access issues too.
--
What turned out to be the best indexing mechanism was a chained
hash table whos hoppers were small linear arrays instead of single
elements. So instead of pointer-chaining each element you have a small
for() loop for 4-8 elements before you chain. The structure being
indexed would NOT be integrated into the index directly, the index
would point at the final structure from the hopper.
For our purposes such linear arrays would contain a pointer and
an indexing value in as small an element as possible (8-16 bytes),
the idea being that you make the absolute best use of your cache line
and L1 cache / memory burst. One random access (initial hash index),
then linear accesses using a small indexing element, then one final
random access to get to the result structure and validate that
it's the one desired (at that point we'd be 99.9% sure that we have
the right structure because we have already compared the index value
stored in the hopper). As a plus the initial hash index also makes
MP locking the base of the chains ...
