[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]
high-arity splay trees?
- To: <mark>
- Subject: high-arity splay trees?
- From: Eric Dean Tribble <tribble>
- Date: Sat, 17 Feb 90 23:25:56 PST
- Cc: <roger>, <michael>, <xtech>
- In-reply-to: <MarkS.Miller'smessageofFri>,39 PST <9002170424.AA03552@xanadu>
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.