Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase ««1234»»»

B-tree Expand / Collapse
Author
Message
Posted Wednesday, September 30, 2009 7:33 AM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Monday, November 2, 2009 7:39 AM
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?

Post #795716
Posted Wednesday, September 30, 2009 9:03 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Thursday, January 24, 2013 9:59 PM
Points: 1,354, Visits: 1,299
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
Post #795797
Posted Wednesday, September 30, 2009 9:28 AM
Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Tuesday, November 5, 2013 6:08 AM
Points: 1,079, Visits: 591
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
Post #795818
Posted Wednesday, September 30, 2009 9:32 AM
Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Tuesday, November 23, 2010 4:09 PM
Points: 1,384, Visits: 47
Don't pick binary
Don't pick binary
Don't pick binary
.
.
.
ACK! Picked binary
Post #795826
Posted Wednesday, September 30, 2009 9:54 AM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Wednesday, September 17, 2014 11:06 AM
Points: 1,921, Visits: 396
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.

Post #795855
Posted Wednesday, September 30, 2009 10:07 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Thursday, January 24, 2013 9:59 PM
Points: 1,354, Visits: 1,299
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.
Post #795866
Posted Wednesday, September 30, 2009 10:10 AM


SSC Eights!

SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!

Group: General Forum Members
Last Login: Friday, February 4, 2011 7:20 AM
Points: 977, Visits: 1,499
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
Post #795870
Posted Wednesday, September 30, 2009 10:12 AM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Wednesday, September 17, 2014 11:06 AM
Points: 1,921, Visits: 396
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.
Post #795871
Posted Wednesday, September 30, 2009 10:43 AM
Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: 2 days ago @ 6:45 AM
Points: 1,333, Visits: 1,701
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.)
Post #795887
Posted Wednesday, September 30, 2009 10:57 AM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Tuesday, February 11, 2014 4:12 PM
Points: 2,007, Visits: 768
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.
Post #795895
« Prev Topic | Next Topic »

Add to briefcase ««1234»»»

Permissions Expand / Collapse