I still think splay trees (aka. self-adjusting trees) are good, because
they have automatic cacheing properties which plain skip lists or the
other tree structures don't.
The downside is some pointer writing takes place when searching, except
when you get the same node as last time. Perhaps the memory write times
are significant. But then, any cache does this, including the one entry
VMA cache.
> Have you considered the relatively new data structure called a 'skip
> list'? I have replaced several subsystems in our system at work that
> would have been ready candidates for AVL or RB trees (or any of a cast
> of thousands of others) with skiplists to very good effect in
> insertion, deletion and search speed.
Have you ever tried splay trees? I would be interested to know of
applications in which skip lists outperform splay trees, and vice versa.
I would expect it to depend on whether the automatic cacheing is useful
or not.
-- Jamie
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/