Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!parc!cutting
From: cutting@parc.xerox.com (Doug Cutting)
Newsgroups: comp.lang.scheme
Subject: Re: looking for balancing (binary/avl) tree programs
Message-ID: <CUTTING.91May20211202@kolsaas.parc.xerox.com>
Date: 21 May 91 02:12:02 GMT
References: <1991May20.150025.16099@uicbert.eecs.uic.edu>
Sender: news@parc.xerox.com
Distribution: comp
Organization: Xerox PARC, Palo Alto, CA
Lines: 19
In-Reply-To: lam@uicbert.eecs.uic.edu's message of 20 May 91 15:00:25 GMT

In article <1991May20.150025.16099@uicbert.eecs.uic.edu> lam@uicbert.eecs.uic.edu (Michael Lam) writes:

> I am looking for scheme programs written for balancing 
> binary/avl tree for database applications.  Any related
> things (like B-trees) are also of interest.  Thanks in
> advance.

FYI, Skip lists are an attractive alternative to balanced trees.  The
order of the various operations is similar (log insert & delete,
linear enumeration) but the constant factors (space & time) tend to be
lower and the implementation is *much* simpler.  They're described in
the June 1990 CACM (v33#6) pp668-680.

B-trees are really designed for indices which are too large to fit in
main memory.  A proper implementation is a tricky matter.  For some
reason, people like to implement memory-resident B-trees, but there
other data structures better suited to this purpose (e.g. above).

	Doug