B-tree

SQLServerCentral is supported by Red Gate Software Ltd.

Popular Topics

Home

Members

Calendar

Who's On

Home » Article Discussions » Article Discussions by Author » Discuss content posted by Noel McKinney » B-tree

34 posts, Page 2 of 4

««1 2 3 4 »»»

B-tree

Rate Topic

Display Mode

Topic Options

Author

Message

abinder-1080408

Posted Wednesday, September 30, 2009 7:33 AM

SSC Rookie

Group: General Forum Members
Last Login: Monday, November 02, 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

cengland0

Posted Wednesday, September 30, 2009 9:03 AM

Ten 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

BudaCli

Posted Wednesday, September 30, 2009 9:28 AM

Ten Centuries

Group: General Forum Members
Last Login: Wednesday, March 27, 2013 9:02 AM
Points: 1,046, Visits: 573

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

Jeff Welcome-130556

Posted Wednesday, September 30, 2009 9:32 AM

Ten 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

Matt Marston

Posted Wednesday, September 30, 2009 9:54 AM

SSCommitted

Group: General Forum Members
Last Login: Monday, May 13, 2013 9:56 AM
Points: 1,808, Visits: 369

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

cengland0

Posted Wednesday, September 30, 2009 10:07 AM

Ten 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)

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

Tom Garth

Posted Wednesday, September 30, 2009 10:10 AM

SSC Eights!

Group: General Forum Members
Last Login: Friday, February 04, 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

Matt Marston

Posted Wednesday, September 30, 2009 10:12 AM

SSCommitted

Group: General Forum Members
Last Login: Monday, May 13, 2013 9:56 AM
Points: 1,808, Visits: 369

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

sknox

Posted Wednesday, September 30, 2009 10:43 AM

Ten Centuries

Group: General Forum Members
Last Login: Tuesday, May 21, 2013 9:31 AM
Points: 1,041, Visits: 1,356

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

Noel McKinney

Posted Wednesday, September 30, 2009 10:57 AM

SSCrazy

Group: General Forum Members
Last Login: Thursday, April 05, 2012 2:35 PM
Points: 2,007, Visits: 767

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 »

34 posts, Page 2 of 4

««1 2 3 4 »»»

Permissions