Hi there,
Can someone tell me what does b-trees stand for?
Balanced trees? Or is it just simply b-trees (without
any meaning)?
Thanks,
- Allan
--
========================================
-- Allan Teo
-- Centre For Computer Studies,
-- Ngee Ann Polytechnic,
-- Singapore
-- Email: ········@mbox2.singnet.com.sg
========================================
Binary trees.
> Hi there,
>
> Can someone tell me what does b-trees stand for?
>
> Balanced trees? Or is it just simply b-trees (without
> any meaning)?
>
> Thanks,
> - Allan
In article <··························@keeper.1.acs.ohio-state.edu>,
Kyle Keeper <········@osu.edu> wrote:
>Binary trees.
>
>> Hi there,
>>
>> Can someone tell me what does b-trees stand for?
>>
>> Balanced trees? Or is it just simply b-trees (without
>> any meaning)?
*NO!* B-trees are not at all binary trees! B-trees are balanced
multiway trees designed for external (read: disk) storage of data with
efficient data access operations. Binary trees are two-way trees
designed for effecient internal (read: RAM) access. Beyond the fact
that they both start with a B and are both instances of tree structures
they are completely different.
--Ken Pizzini
In article <··························@keeper.1.acs.ohio-state.edu>
········@osu.edu "Kyle Keeper" writes:
>Binary trees.
No, a B-tree is a very different beast to a binary tree.
>> Can someone tell me what does b-trees stand for?
>>
>> Balanced trees? Or is it just simply b-trees (without
>> any meaning)?
If it has any meaning I believe it would be "balanced". However it really
just refers to a specific datastructure.
However I'm not quite sure why this was posted to 3 language newsgroups
since it is not a language issue.
--
-----------------------------------------
Lawrence Kirby | ····@genesis.demon.co.uk
Wilts, England | ·········@compuserve.com
-----------------------------------------
Allan Teo (········@singnet.com.sg) wrote:
: Hi there,
: Can someone tell me what does b-trees stand for?
: Balanced trees? Or is it just simply b-trees (without
: any meaning)?
Hi,
B-tree stands for Bayer-tree. Like in AVL-trees the first letter of the
inventors name is used. Prof. Bayer was with the University of Munich
when I studied there 5 years ago.
B-tree's are not binary trees and most times not balanced. They are
efficient for indexing large amounts of data on slower storage medias.
They try to reduce the access time to these medias.
Regards
Kai
____________________________________________________________________________
Kai Zimmermann FB Informatik, WSV, University Hamburg, Vogt-Koelln-Str. 30
D-22527 Hamburg, Germany, Phone +49-40-5494-2368, Fax -2385
Please note: http://www.informatik.uni-hamburg.de/WSV/hp/kai-english
New phone & fax number ········@informatik.uni-hamburg.de
In article <··························@stealth> "Allan Teo" <········@singnet.com.sg> writes:
>Hi there,
>
>Can someone tell me what does b-trees stand for?
>
>Balanced trees? Or is it just simply b-trees (without
>any meaning)?
B=Balanced. The reason is that the algorithm forces the tree to have
uniform depth at all times.
Hi guys,
Searching the 'Net on "B-tree" I found few interesting things. First of all
the it's probably pronounced "bee-minus-tree", not just "bee-tree" (there
is an alternative which is called "B+tree"). Second, yes, it's a balanced
tree. But there was no source available on why it was called "B-tree",
exactly.
Victor.
PS. Search the Web, and thou shalt find what thou seekt.
PPS. Pardon me for following up on off-topic.
Allan Teo <········@singnet.com.sg> wrote in article
<··························@stealth>...
> Hi there,
>
> Can someone tell me what does b-trees stand for?
>
> Balanced trees? Or is it just simply b-trees (without
> any meaning)?
>
> Thanks,
> - Allan
> --
> ========================================
> -- Allan Teo
> -- Centre For Computer Studies,
> -- Ngee Ann Polytechnic,
> -- Singapore
> -- Email: ········@mbox2.singnet.com.sg
> ========================================
>
Victor Bazarov wrote:
> Searching the 'Net on "B-tree" I found few interesting things. First of all
> the it's probably pronounced "bee-minus-tree", not just "bee-tree" (there
> is an alternative which is called "B+tree"). Second, yes, it's a balanced
> tree. But there was no source available on why it was called "B-tree",
> exactly.
It's *not* "bee-minus-tree", "B+tree" notwithstanding.
Also, saying "it's a balanced tree" may mislead some people;
note that it's not a balanced *binary* tree, but a balanced
tree with rather more branching than that.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
Dear Gareth,
Gareth McCaughan <·····@pmms.cam.ac.uk> wrote in article
<···············@jay.dpmms.cam.ac.uk>...
> Victor Bazarov wrote:
>
> > Searching the 'Net on "B-tree" I found few interesting things. First of
all
> > the it's probably pronounced "bee-minus-tree", not just "bee-tree"
(there
> > is an alternative which is called "B+tree"). Second, yes, it's a
balanced
> > tree. But there was no source available on why it was called "B-tree",
> > exactly.
>
> It's *not* "bee-minus-tree", "B+tree" notwithstanding.
"notwithstanding" what? Is "B+tree" pronounced "bee-plus-tree"? My English
is not so great, please excuse me.
> Also, saying "it's a balanced tree" may mislead some people;
> note that it's not a balanced *binary* tree, but a balanced
> tree with rather more branching than that.
Thank you for clarifying what B-tree is. I know it now. And I know that I
misled some people. Sorry, some people, I wasn't intended to mislead you.
:-/
Yes, B-tree is *not* binary, also a binary tree could be a kind of B-tree,
AFAIU. In any case, the information in the books on my shelf was not enough
to find out why B-tree is called "B-tree". If someone (yes, Gareth, you're
included) has the correct definition or a comprehensive source, I'd
appreciate to be informed.
> --
> Gareth McCaughan Dept. of Pure Mathematics & Mathematical
Statistics,
> ·····@dpmms.cam.ac.uk Cambridge University, England.
Victor.
In article <··························@victor.imsisoft.com>,
> Victor Bazarov (········@imsisoft.com) spake:
[ deletia ]
> Yes, B-tree is *not* binary, also a binary tree could be a kind of B-tree,
> AFAIU. In any case, the information in the books on my shelf was not enough
> to find out why B-tree is called "B-tree". If someone (yes, Gareth, you're
> included) has the correct definition or a comprehensive source, I'd
> appreciate to be informed.
In the excellent article I have _The_Ubiquitous_B-Tree_
(Douglas Comer, Purdue University) from the ACM "Computing Surveys",
vol 11, No. 2, 1979, when referring to the original Bayer/MacCreight
article he states:
The origin of "B-tree" has never been explained by the
authors. As we shall see, "balanced", "broad" or "bushy"
might apply. Others suggest that the "B" stands for
Boeing (where Bayer worked, parenthesis mine). Because
of his contributions, however, it seems appropriate to
think of B-trees as "Bayer"-trees.
I have found this article excellent in explaining the construction
of all the major variants of B-trees, to wit, B-trees, B+trees
(B plus trees), B*trees (B star trees), prefix B*trees and
virtual B-trees.
Happy coding.
Andrew.
--
······@snowhite.cis.uoguelph.ca ········@uoguelph.ca
"Victor Bazarov" <········@imsisoft.com> writes:
>
> Yes, B-tree is *not* binary, also a binary tree could be a kind of B-tree,
> AFAIU. In any case, the information in the books on my shelf was not enough
> to find out why B-tree is called "B-tree". If someone (yes, Gareth, you're
> included) has the correct definition or a comprehensive source, I'd
> appreciate to be informed.
>
Knuth writes about the B-tree in his "The art of computer programming"
in chapter 6.2.4 Multiway trees. He gives the original source [Acta
Informatica (1972), 173-189], but does not give any explanation for
the name.
I'll give his description of it though:
A B-tree of order m is a tree which satisfies the following
properties:
1. Every node has <= m sons.
2. Every node, except for the root and the leaves, has >= m/2 sons.
3. The root has at least 2 sons (unless it is a leaf).
4. All leaves appear on the same level, and carry no information.
5. A nonleaf node with k sons contains k-1 keys.
I have been using b-trees for a long time (my marker in the book for
that chapter is a punching-card :-) ), and I'm happy about this
data-structure, even though I must admit I have broken some of the
above rules slightly.
Hans
····@dnv.com