[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

high-arity splay trees?

Actually my major objection to splay trees has to do with write-once
      media and write-a-few-times media.

   Our read algorithms don't insist that the splay operation succeed
   (Dean, is this still true?).  If the tree is pre-balanced before
   writing it to a not-very-writable media, then everything should still
   be log-bounded despite the old orgl's refusal to splay itself.

The read algorithm currently expects the entire contents to be in a
single subTree.  This won't be difficult to change, though.  An
alternative is go ahead and splay in memory, and just don't write out
the files to disk.