Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!xylogics!merk!alliant!cairo!tony
From: tony@cairo.UUCP (Tony Anzelmo)
Newsgroups: comp.databases
Subject: Re: What is a B+ tree? (was Re: Index Managers and B+ trees)
Keywords: B tree, B+ tree
Message-ID: <125@cairo.UUCP>
Date: 19 Mar 90 19:55:23 GMT
References: <1467@mountn.dec.com>
Reply-To: tony@cairo.UUCP (Tony Anzelmo)
Organization: Anzelmo Associates, Inc.
Lines: 27

In article <1467@mountn.dec.com> wallis@labc.dec.com (Barry L. Wallis) writes:
>
>In article <33095@shemp.CS.UCLA.EDU>, ravi@maui.cs.ucla.edu (T.M Ravi) writes...
>> 
>>I remember seeing a bunch of messages a few months back about B/B+ trees. 
>>We already have the design of locking and transaction and buffer management
>>worked out and are trying to design a traditional high performance index
>>manager using B+ trees. 
>> 
>
>This brings up a question that I've wondered about from time to time (bit never
>for very long ;-) ). What is the difference between a B tree and a B+ tree?
>

In a B+ tree, all data is moved to the leaf nodes. The upper level nodes
only provide the search path. In addition, leaf nodes are linked together
into a "sequence set" that allows simple sequential access in addition to
efficient random access normally associated with B trees.

The best paper on B trees I've seen is "The Ubiquitous B-Tree" by Douglas
Comer. Computing Surveys, Vol. 11, No. 2, June 1979.


Tony Anzelmo
Anzelmo Assoc. Inc.
508-568-1880
...!linus!alliant!cairo!tony