Click here to monitor SSC
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


B-tree


B-tree

Author
Message
abinder-1080408
abinder-1080408
SSC Rookie
SSC Rookie (25 reputation)SSC Rookie (25 reputation)SSC Rookie (25 reputation)SSC Rookie (25 reputation)SSC Rookie (25 reputation)SSC Rookie (25 reputation)SSC Rookie (25 reputation)SSC Rookie (25 reputation)

Group: General Forum Members
Points: 25 Visits: 23
If I had asked a question like this of my students in college, they would have stoned me.

Wikipedia says not to confuse it with a binary tree but goes on to say that it is a generalized form of a binary tree search. Searchsqlserver.techtarget.com says, "A B-tree is a method of placing and locating files (called records or keys) in a database. (The meaning of the letter B has not been explicitly defined.) The B-tree algorithm minimizes the number of times a medium must be accessed to locate a desired record, thereby speeding up the process."

Someone replied that since this is an MS SQL forum that MS should be the deciding authority. If MS said that the B in VB stoof for "balance" does that make it so?
cengland0
cengland0
UDP Broadcaster
UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)

Group: General Forum Members
Points: 1484 Visits: 1300
Warren Gilbert (9/30/2009)
There are several references to the fact that the meaning of the 'B' in B-Tree is undefined, but since this site is 'Microsoft' SQL Server related, the following page makes it quite clear -

http://msdn.microsoft.com/en-us/library/aa964133(SQL.90).aspx

... B-Trees, where B stands for "balanced" (not "binary," as is sometimes thought)...


You cannot trust what Microsoft says about what the "B" stands for because they didn't coin the term. I thought it was Binary because Wikipedia says that it's a binary search tree. Binary seems a more logical explanation of what the B stands for instead of Balanced.

http://en.wikipedia.org/wiki/B-tree
BudaCli
BudaCli
Ten Centuries
Ten Centuries (1.2K reputation)Ten Centuries (1.2K reputation)Ten Centuries (1.2K reputation)Ten Centuries (1.2K reputation)Ten Centuries (1.2K reputation)Ten Centuries (1.2K reputation)Ten Centuries (1.2K reputation)Ten Centuries (1.2K reputation)

Group: General Forum Members
Points: 1166 Visits: 598
I'll call this a thriller...Nice one!!!

What you don't know won't hurt you but what you know will make you plan to know better
Jeff Welcome-130556
Jeff Welcome-130556
Ten Centuries
Ten Centuries (1.4K reputation)Ten Centuries (1.4K reputation)Ten Centuries (1.4K reputation)Ten Centuries (1.4K reputation)Ten Centuries (1.4K reputation)Ten Centuries (1.4K reputation)Ten Centuries (1.4K reputation)Ten Centuries (1.4K reputation)

Group: General Forum Members
Points: 1384 Visits: 47
Don't pick binary
Don't pick binary
Don't pick binary
.
.
.
ACK! Picked binary
Matt Marston
Matt Marston
SSCommitted
SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)

Group: General Forum Members
Points: 1963 Visits: 412
A B-tree could only be confused with a binary tree if it is binary with each node having at most 2 children. Wikipedia states this clearly, "a binary tree is a tree data structure in which each node has at most two children." The SQL Server documentation that references B-tree doesn't clearly state how many children a node can have, but I can tell you it is more than 2.

The Wikipedia reference to a B-tree as a generalized form of a binary tree is accurate. But it doesn't mean that a B-tree is a binary tree any more than saying a polygon is a generalized form of a rectangle means that a polygon is a rectangle.
cengland0
cengland0
UDP Broadcaster
UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)UDP Broadcaster (1.5K reputation)

Group: General Forum Members
Points: 1484 Visits: 1300
Matt Marston (9/30/2009)
A B-tree could only be confused with a binary tree if it is binary with each node having at most 2 children. Wikipedia states this clearly, "a binary tree is a tree data structure in which each node has at most two children." The SQL Server documentation that references B-tree doesn't clearly state how many children a node can have, but I can tell you it is more than 2.

The Wikipedia reference to a B-tree as a generalized form of a binary tree is accurate. But it doesn't mean that a B-tree is a binary tree any more than saying a polygon is a generalized form of a rectangle means that a polygon is a rectangle.



I actually agree with your analogy but I still believe this question should be thrown out. Technically, the B doesn't have an official meaning and there's lots of debate about that. So it's a bad question.

I work for a training organization and have become an expert in question writing and I can tell you that if I asked a question like this on any of my quizzes, the students would have good reason to question the accuracy of my answer.

Microsoft is not the authority on what the "B" means. I'd say it's Rudolf Bayer and Ed McCreight who have the authority since they invented the B-tree while working at Boeing. For all we know, the B could mean Bayer or Boeing regardless of what Microsoft thinks it means.
Tom Garth
Tom Garth
Ten Centuries
Ten Centuries (1K reputation)Ten Centuries (1K reputation)Ten Centuries (1K reputation)Ten Centuries (1K reputation)Ten Centuries (1K reputation)Ten Centuries (1K reputation)Ten Centuries (1K reputation)Ten Centuries (1K reputation)

Group: General Forum Members
Points: 1013 Visits: 1499
SQL Server indexes are organized in a B-tree structure. The "B" in B-tree stands for what?


The question is specifically referring to SQL Server indexes. The Microsoft definition would make the most sense.

Tom Garth
Vertical Solutions

"There are three kinds of men. The one that learns by reading. The few who learn by observation. The rest of them have to pee on the electric fence for themselves." -- Will Rogers

Matt Marston
Matt Marston
SSCommitted
SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)

Group: General Forum Members
Points: 1963 Visits: 412
cengland0 (9/30/2009)

I actually agree with your analogy but I still believe this question should be thrown out.


I agree that is is a very poor question. I was only arguing that we know what it does not mean (binary). Beyond that we can only hypothesize about what the creators meant the B to stand for.
sknox
sknox
SSCrazy
SSCrazy (2K reputation)SSCrazy (2K reputation)SSCrazy (2K reputation)SSCrazy (2K reputation)SSCrazy (2K reputation)SSCrazy (2K reputation)SSCrazy (2K reputation)SSCrazy (2K reputation)

Group: General Forum Members
Points: 2036 Visits: 2711
Tom Garth (9/30/2009)
SQL Server indexes are organized in a B-tree structure. The "B" in B-tree stands for what?


The question is specifically referring to SQL Server indexes. The Microsoft definition would make the most sense.


Except that the term B-tree is NOT a Microsoft term. By that logic, someone implementing any standard gains the right to redefine the definition of that standard to their consumers. This simply leads to standards dilution.

B-trees are balanced trees. They are not binary trees. But that's not what the question asks. The question asks what the B stands for. And that we don't know.

The best solution is to rephrase the question to "These B-trees are what?", and add "trees" to the answer (as well as verify that answers other than "balanced" and "binary" don't fit.)
Noel McKinney
Noel McKinney
SSCrazy
SSCrazy (2K reputation)SSCrazy (2K reputation)SSCrazy (2K reputation)SSCrazy (2K reputation)SSCrazy (2K reputation)SSCrazy (2K reputation)SSCrazy (2K reputation)SSCrazy (2K reputation)

Group: General Forum Members
Points: 2017 Visits: 796
Tom Garth (9/30/2009)
SQL Server indexes are organized in a B-tree structure. The "B" in B-tree stands for what?


The question is specifically referring to SQL Server indexes. The Microsoft definition would make the most sense.

Thanks for pointing this out Tom... the question is prefaced with a statement to set the context, which is SQL Server indexes. An important characteristic of SQL Server indexes is the balanced structure, and if nothing else this question highlights that.
Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search