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 2:21 PM
Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Monday, January 27, 2014 10:14 AM
Points: 1,322, Visits: 1,091
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
Post #796017
Posted Wednesday, September 30, 2009 3:16 PM
Right there with Babe

Right there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with Babe

Group: General Forum Members
Last Login: Thursday, December 11, 2014 4:11 PM
Points: 786, Visits: 2,217
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
Post #796042
Posted Wednesday, September 30, 2009 4:34 PM
SSC Veteran

SSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC Veteran

Group: General Forum Members
Last Login: Thursday, November 1, 2012 9:43 AM
Points: 207, Visits: 125
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:

I


II


III



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.
Post #796073
Posted Wednesday, September 30, 2009 4:53 PM


Mr or Mrs. 500

Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500

Group: General Forum Members
Last Login: Tuesday, September 23, 2014 6:47 PM
Points: 525, Visits: 557
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

:P

-d

Post #796081
Posted Friday, October 2, 2009 11:04 AM
SSC-Addicted

SSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-Addicted

Group: General Forum Members
Last Login: Thursday, February 6, 2014 9:39 AM
Points: 420, Visits: 487
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.usesage.com
Post #797095
Posted Monday, October 5, 2009 11:59 AM
SSC Journeyman

SSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC Journeyman

Group: General Forum Members
Last Login: Yesterday @ 1:17 PM
Points: 96, Visits: 108
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.
Post #798102
Posted Friday, October 9, 2009 1:34 AM
SSC-Addicted

SSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-Addicted

Group: General Forum Members
Last Login: Yesterday @ 11:52 PM
Points: 459, Visits: 284
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
Post #800550
Posted Friday, October 9, 2009 3:30 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
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.
Post #800605
Posted Tuesday, October 13, 2009 2:15 AM
Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Monday, November 10, 2014 9:11 AM
Points: 1,155, Visits: 1,055
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.
Post #802009
Posted Monday, October 26, 2009 7:11 PM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Sunday, August 17, 2014 3:10 PM
Points: 2,787, Visits: 6,098
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? -- Stephen Stills
Post #809047
« Prev Topic | Next Topic »

Add to briefcase «««1234»»

Permissions Expand / Collapse