On Thursday, October 23, 2003, at 10:13  AM, Charles M. Hannum wrote:

> I have to say that at first sight, using a splay tree in this fashion 
> seems a
> bit strange.  You're inserting and looking up nodes in the tree in 
> exactly
> one place -- there is no locality to be gained WRT looking up the same 
> node
> more than once.  It seems to me that the real gain of the splay tree 
> in this
> case is not from the rebalancing and self-optimization, but from the 
> simple
> fact that on average it's somewhere closer to an AVL tree than a 
> completely
> unbalanced tree, and so the average search time is better.  However, 
> an AVL
> tree would bound the worst case time as well...

I agree with Charles, here.  We still need to be able to efficiently 
traverse the entire list of PV entries for a given page, because that 
is used to write-protect mappings for COW.  We don't really want to 
modify the tree while we do this.

         -- Jason R. Thorpe <thorpej@wasabisystems.com>