rob@alice.UucP (Rob Pike) (11/20/85)
When in Rome, do as the Romans... The shell does not use B-trees, it uses a binary tree. Despite what you may read in Byte, they are not the same thing. B-trees are to binary trees what ksh is to sh. Rob Pike
pn@stc.UUCP (11/26/85)
In article <4590@alice.UUCP> rob@alice.UucP writes: >The shell does not use B-trees, it uses a binary tree. >...... B-trees are to binary trees what ksh is to sh. > > Rob Pike 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> {root44, ukc, datlog, idec, stl, creed, iclbra, iclkid}!stc!pn
tim@ISM780B.UUCP (11/28/85)
> B-trees are to binary trees what ksh is to sh. > Rob Pike Does this mean that B-trees are something that every binary tree user would want to use, or does it mean that they take up a lot of space to add functionality that should be done in another way? Also, what data structures correspond to csh and the 8th edition sh? :-) Tim Smith ima!ism780!tim ihnp4!cithep!tim
hes@ecsvax.UUCP (Henry Schaffer) (11/28/85)
> In article <4590@alice.UUCP> rob@alice.UucP writes: > > >The shell does not use B-trees, it uses a binary tree. > >...... B-trees are to binary trees what ksh is to sh. > > Rob Pike > > 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> An early issue of the ACM publication Computer (Computing?) Surveys had a tutorial article on B-Trees. Very readable. --henry schaffer
henry@utzoo.UUCP (Henry Spencer) (12/01/85)
> > B-trees are to binary trees what ksh is to sh. > > Does this mean that B-trees are something that every binary tree user > would want to use, or does it mean that they take up a lot of space to > add functionality that should be done in another way? It means that they are far more complex and should not automatically be considered a preferred alternative, even though they definitely do have certain advantages. > Also, what data structures correspond to csh and the 8th edition sh? :-) Csh is probably a hash table that everyone has forgotten the hashing function for. The V8 sh... maybe balanced or semi-balanced binary trees? -- Henry Spencer @ U of Toronto Zoology {allegra,ihnp4,linus,decvax}!utzoo!henry
jpl@allegra.UUCP (John P. Linderman) (12/01/85)
The ubiquitous standard reference is Doug Comer's ``The Ubiquitous B-Tree'', ACM Computing Surveys, Vol. 11, No. 2, June 1979, pp. 121- 137. There's an additional page of references at the end of the article. John P. Linderman Dept. of Tree Surgery allegra!jpl
robert@hslrswi.UUCP (Robert Ward) (12/02/85)
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 ******************************************************************************
darin@ut-dillo.UUCP (Darin Adler) (12/03/85)
<>
Aside from sarcastic remarks about B-trees, someone wanted to know
what they were, an what relationship they had to binary trees.
B-trees are a more general case of the type of tree that a binary tree
is. They allow any given number of children per node. They are, by
definition, always balanced. In addition, since the number of
children can be adjusted, the nodes can be made any size. It is often
useful to make the size of a single node equal to the block size of
the mass storage device that the B-tree is stored on. This will help
minimize the number of disk accesses. (A similar thing can be done
with virtual memory, if you know the appropriate block size.)
--
Darin Adler
{gatech,harvard,ihnp4,seismo}!ut-sally!ut-dillo!darinperry@well.UUCP (Perry S. Kivolowitz) (12/04/85)
In article <212@ut-dillo.UUCP>, darin@ut-dillo.UUCP (Darin Adler) writes: > B-trees are a more general case of the type of tree that a binary tree > is. They allow any given number of children per node. They are, by... First: Why are B-Trees called B-Trees? Some people say B (as in Baer, the inventor) or B as in Boeing (where Baer was when he did his work). Next: Are B-Trees binary? No. For a given B-Tree, a node may between n and 2n elements. No node (except the root) may have less than n. No node (including the root) may have more than 2n. During an insertion, if the node being inserted in would grow to 2n + 1 elements, the node is split into two nodes one of n elements the other of n elements. The middle element is graduated to the original nodes parent (where a similar process will occurr). During deletion, if the node being deleted from should shrink to less than n elements is is combined with a neighbor to produce two nodes each having greater than n elements. And: What's so neat about B-Trees. They are always balanced insuring logarithmic operations. The logarithmic time is dependent of course on the choice. N is usually chosen so as to make an integer number of records fit reasonably in an integer number of blocks. Also, you are always assured that space utilization is greater than 50 percent while leaving as much as percent space for expansion. Are there other types of B-Tree? yes, B+ and B* Trees. B* trees change in minimum number of elements per non root node fro 2n/3 elements giving you 2/3 space utilization. Oh yeah, why is space utilization important? Becuase the better you use the space you have the less deep the tree. B+ Trees are different in that they seperate indices from data. You have an index set, and a data set. All leave nodes are at the same level and contain ONLY data (perfect for indexed and sequential operations) while b-trees can stuff records (index and data) anywhere in the tree. (the above is what happens when you write a b+ tree based data base system in two weeks four years ago). any one wanna buy it for the amiga? :-) Perry S. Kivolowitz ihnp4!ptsfa!well!perry
darin@ut-dillo.UUCP (Darin Adler) (12/05/85)
I have always (since I have been aware of, and used the B-tree data
structure) thought of binary trees as being a degenerate case of a
B-tree. In other words, where B-trees have between n and 2n children
per node, a binary tree has between 1 and 2 children per node (n=1).
Unfortunately, the algorithms for B-trees do not work in this
degenerate case (thus binary trees cannot be balanced in the simple
way that B-trees are). I am sure that there is something else
fundamentally wrong with this analogy. Any data structures expert
want to comment and/or enlighten me?
--
Darin Adler
{gatech,harvard,ihnp4,seismo}!ut-sally!ut-dillo!darin