September 30, 2009 at 10:07 am
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.
September 30, 2009 at 10:10 am
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.
September 30, 2009 at 10:12 am
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.
September 30, 2009 at 10:43 am
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.)
September 30, 2009 at 10:57 am
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.
September 30, 2009 at 2:21 pm
B-trees are balanced trees.
I'm away from my old data structures book, but is there a requirement that b-trees be balanced. I remember balancing them, but I don't remember that being a requirement for a generic B-tree. It seems that there was another name for a balanced tree (AVF comes to mind, but I'll need to actually look it up when I get home)
--
JimFive
September 30, 2009 at 3:16 pm
I disagree. This is not a matter of the writers opinion. This is a SQLServer site and the question relates to SQLServer, not generic databases and structures. BOL clearly states that B-Tree stands for "Balanced". Sybase use the same definition and have done so for the 16 years I've been a dba. It was really Sybase who introduced the term, not MS, as far as I'm aware. I'm not arguing that anywhere else in the database world b-tree stands for binary, but relating to Sybase/SQLServer indexes it has always meant 'balanced'.
Cheers
Roddy
September 30, 2009 at 4:34 pm
I actually thought this one was easy. I know that the term balanced is the B in B tree.
Reason because the way the pages and indexes work in Sybase and SQL Server for example with a root node, intermediate nodes and leaf node.
Very noddy diagram warning:
There should always be the same number of jumps to pages no matter where the data is stored on table via index. Oracle has other types of storage available as well as B tree.
I think MS Book on SQL Server internals may have a reference to this.
I usually have to have a good think about the questions this one I knew the answer straight away.
September 30, 2009 at 4:53 pm
I don't think you can put a known standard term "in context" in order to change it's agreed meaning.
Although I haven't read the research paper myself, after a couple of quick discussions with others, as far as we can tell, it was actually developed to create indexes in general for searching algorithms, whether the underying data is in a RDB, a binary file, a text file, heck, maybe you are storing it in a crystal lattice 🙂
What the B Tree achieves is a balanced index, but you can't state as fact that the B is balanced, even if BOL states it.
I spose you might say in this case that an appropriate answer option to What does B stand for? might be:
E) NULL
😛
-d
October 2, 2009 at 11:04 am
Take a look at the third reference in the Bayer/McCreight paper from 1972 -
3. Landauer, W. I.: The balanced tree and its utilization in information retreival.
IEEE Trans. on electronic Computers, Vol. EC-12, No. 6, December 1963.
The term was coined before Bayer ever used it, even though NIST provides conflicting information - http://www.itl.nist.gov/div897/sqg/dads/HTML/btree.html
Joshua Perry
http://www.greenarrow.net
October 5, 2009 at 11:59 am
In computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, insertions, deletions, and sequential access in logarithmic amortized time. The B-tree is a generalization of a binary search tree in that more than two paths diverge from a single node[1]. Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. It is most commonly used in databases and filesystems. (wikipedia)
Go figure, another answer that may be, or may not be, 100% accurate...
I have also read b-tree means "self-balanced," not simply balanced...so should it be an SB-tree?
I should know not to try and answer the obvious and really research what the author is trying to convey.
October 9, 2009 at 1:34 am
Last TechEd Europe (Barcelona, November 2008) I was talking with Kim Tripp - and she is a guru in indexing, and she told about B-trees as BALANCED TREES.
Also Kalen Delaney in her books also uses the term "BALANCED TREES" and explains this as the tree is symetrical and must be like this after any modification, for example DML operation on the index.
Kindest Regards,
Damian Widera
SQL Server MVP,
MCT, MCSE Data Platform, MCSD.NET
October 9, 2009 at 3:30 am
Damian Widera-396333 (10/9/2009)
Last TechEd Europe (Barcelona, November 2008) I was talking with Kim Tripp - and she is a guru in indexing, and she told about B-trees as BALANCED TREES.Also Kalen Delaney in her books also uses the term "BALANCED TREES" and explains this as the tree is symetrical and must be like this after any modification, for example DML operation on the index.
I doubt anyone is disputing that B-Trees are balanced but we have disagreement that the "B" in the word "B-Tree" means Balanced.
The creator of that term worked for Boeing when it was created so it could stand for Boeing.
The creator's last name is Bayer so it could stand for Bayer.
The B-tree is a generalization of a binary search tree in that more than two paths diverge from a single node so the "B" could stand for binary.
The fact is, nobody really knows what the "B" stands for. Microsoft says it's Balanced but they are not the creator of the term so Microsoft is not the authority on what it means. They can only speculate like the rest of us.
October 13, 2009 at 2:15 am
cengland0 (10/9/2009)[hr
The creator of that term worked for Boeing when it was created so it could stand for Boeing.
The creator's last name is Bayer so it could stand for Bayer.
The B-tree is a generalization of a binary search tree in that more than two paths diverge from a single node so the "B" could stand for binary.
Surely the "learning point" of the question is that B-trees are not binary trees ( they may turn out to be binary trees in some special cases depending on the data that is inserted into them but as soon as any node has more than 2 child nodes, they are not binary.)
If "Boeing" or "Bayer" had been offered as a possible answer, there *might* be some kind of argument for those - but they weren't. Virtually everyone who chose the wrong answer chose "binary" - and have now had the opportunity to learn something they didn't know before.
I probably get as many questions here wrong as I get right. But I learn much more from the ones that I get wrong.
October 26, 2009 at 7:11 pm
I'm late to the party on this one, but got it right from reading the Inside SQL Server 2005 books. Kalen Delaney stressed that it was balanced. A couple of comments.
1. "Balanced" is significant because it means the structure of the indexes tries to keep accesses to different "leaves" as close to one another as possible. Some people give warnings about what particular data loads might do to a b-tree structure, but they aren't talking about "balanced" indexes.
2. People who say that it is unknown should have the humility to say that it is unknown to them. Obviously if it is being published in official Microsoft publications, it's not being hidden.
3. If things like this aren't in BOL, they ought to be.
__________________________________________________
Against stupidity the gods themselves contend in vain. -- Friedrich Schiller
Stop, children, what's that sound? Everybody look what's going down. -- Stephen Stills
Viewing 15 posts - 16 through 30 (of 33 total)
You must be logged in to reply to this topic. Login to reply