Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83 (MC840302); site hslrswi.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!genrad!decvax!ucbvax!ucdavis!lll-crg!seismo!mcvax!cernvax!hslrswi!robert
From: robert@hslrswi.UUCP (Robert Ward)
Newsgroups: net.unix
Subject: Re: B-trees
Message-ID: <142@hslrswi.UUCP>
Date: Mon, 2-Dec-85 14:51:53 EST
Article-I.D.: hslrswi.142
Posted: Mon Dec  2 14:51:53 1985
Date-Received: Thu, 5-Dec-85 05:24:12 EST
Organization: Hasler AG, Bern, Switzerland
Lines: 35

Phil Norris (pn@stc.uucp) asks in article <716@stc-b.stc.UUCP> -
> Anybody out there prepared to offer a *brief* explanation of what
> B-trees are?  Pointers to good literature on the subject would be
> much appreciated too.  Thanks muchly.
> Phil Norris	<pn@stc.UUCP>

Here, then, are some references explaining all about B-trees -
1.	"The Art Of Computer Programming",
	by D. E. Knuth, Volume 3, pp. 471 - 479, (Addison-Wesly, 1973) ;
2.	"Design Of Database Structures",
	by T. J. Teorey and J. P. Fry, pp. 305 - 327, (Prentice-Hall, 1982) ;
3.	"Organisation And Maintenance Of Large Ordered Indexes",
	by R. Bayer and E. McCreight, Acta Informatica, 1, (1972), pp. 173-189;
4.	"The Ubiquitous B-Tree",
	by D. Comer, ACM Computer Survey, 11,2 (June 1979), pp. 121-137.

The most readable of these is the last one (by Douglas Comer of the
Xinu operating system fame). Knuth only gives a brief and incomplete
description of B-trees. Bayer and McCreight invented B-trees : their
article, therefore, is the original collector's item.

Hope this helps,
Cheers,
	Robert.

******************************************************************************
    Robert Ward,
    Hasler AG, Murtenstrasse 137a, CH-3008 Bern, Switzerland

Tel.:	    (031) - 65 23 19
Uucp:	    ... {seismo,decvax,ukc, ... }!mcvax!cernvax!hslrswi!robert
Bitnet:	    hslrswi!robert@cernvax.bitnet
Arpa:	    hslrswi!robert%cernvax.bitnet@WISCVM.ARPA
Edunet:	    hslrswi!robert%cernvax.bitnet@UCBJADE.Berkeley.EDU
******************************************************************************