B-trees

[Robert Ward]

Phil Norris (pn at stc.uucp) asks in article <716 at 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 at 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 at cernvax.bitnet
Arpa:	    hslrswi!robert%cernvax.bitnet at WISCVM.ARPA
Edunet:	    hslrswi!robert%cernvax.bitnet at UCBJADE.Berkeley.EDU
******************************************************************************