Talk:B+ tree

From Wikipedia, the free encyclopedia

inner insert break the B+ tree definition

b+ tree is a tree with leaves if it has height n than its order is n . it has keys .

Why all that code?! Is this the way a Wikipedia article should be written? Please consider fleshing out the article to add more "information" and less "code". --221.134.26.57 17:43, 21 May 2006 (UTC)


The code really needs to be pared down to the minimum amount to demonstrate the ADT. I'm in favor of rewriting the C++ and dropping the java. The third party libraries and debug code should definately go for an encyclopedic article. I'll try and get the code written this weekend.
A brisson 08:48, 7 June 2006 (UTC)
Why have sample code here at all? -- Mikeblas 14:37, 7 June 2006 (UTC)
I propose moving the code to another Wiki-project (like WikiSource), or at least to a separate page on Wikipedia, and then have a link to that page in this article. As it stands now, it's pretty confusing (IMHO).
--User:aadnk 19:48, 2 June 2006 (UTC)
I agree that the source should be in a different article. I put it here because I didn´t find any better place. As for de violation of the B+ invariants during insertion, that is a known feature of the code to make it easier to understand. If you can make the code canonical and keep it simple at the same time, please be my guest. Simplicity is the reason I did not implement key deletion. It is usually implemented in a non-canonical way (deleting a node only when it is completely empty) because it is both easier to implement and its usually at least as efficient as the canonical one. (David Garcia -- unlogged)


Agreed. Alot of the code is also incorrect (maybe its formatted wrong) - there are lots of underscores missing. I think too much code. Pseudo code would do just fine. --Smremde 08:49, 13 June 2006 (UTC)


A picture would be nice.

Contents

[edit] How is the subject pronounced?

Lipatden 14:45, 11 July 2006 (UTC)

"bee plus tree". If someone knows IPA, it would be great if they could add a pronunciation guide to the article. -- Mikeblas 15:40, 11 July 2006 (UTC)

[edit] Removed "dancing tree" reference

I removed the ambiguous reference to dancing tree, as that term doesn't refer to a particular data structure, only to an implementation detail (lazy rebalancing) that can be implemented on any self-balancing tree. -- Tlesher 00:13, 19 April 2007 (UTC)


[edit] Description of order incorrect?

I believe the description of order is incorrect here and has been since the page's first cut.

In Database Management Systems by Ramakrishnan and Gehrke, they describe order as being a measure of the capacity of a B+ tree where every node contains m entries, the order d is d ≤ m ≤ 2d. The only exception is the root node which is 1 ≤ m ≤ 2d.

Unless there is ambiguity in this terminology, I propose that this should be corrected.

Ikershaw 22:52, 26 May 2007 (UTC)

[edit] Quarternary Tree

Just wanted to make sure this really is called a Quarternary Tree by others, my lecturer and past exam papers describe a Quarternary Tree as if it is a B+ Tree, so if you have heard of this phrase being used elsewhere please cite it. --Olivia Guest 14:39, 27 May 2007 (UTC)

  • A Quaternary Tree is not the same thing as a B+ Tree. They are completely orthogonal concepts. See [1]. I have removed the reference from the wiki page. Mdmkolbe (talk) 02:26, 18 March 2008 (UTC)

[edit] Relationship to B-Tree

In reading the article, I didn't get a clear idea of what the differences are between a B-Tree and a B+Tree. If someone could clarify this difference, that would be a useful contribution. KellyCoinGuy (talk) 18:42, 19 November 2007 (UTC)

[edit] Faulty diagram

I'm rather certain the diagram demonstrating this algorithm is incorrect. Consistently, this diagram erringly splits nodes right when they reach capacity, thus precluding there ever being any "full" nodes. B-tree algorithms (and B+-tree) are supposed to split nodes only after capacity is reached and a new value is tried to be inserted in a full node. 132.198.12.98 21:30, 30 November 2007 (UTC)

The diagram is incorrect and has been removed. While there are some implementations of B+ trees that do split before the block is full (this allows you to perform the split after insertion is completed), this is not the "normal" procedure.78.91.39.182 15:13, 1 December 2007 (UTC)

[edit] Diagram

The diagram isn't very clear. It doesn't show that the data matches the keys, and it makes the 'linked list' pointers much different than the data pointers. —Preceding unsigned comment added by 24.26.131.178 (talk) 04:46, 4 December 2007 (UTC)


There should be step-by-step insertion/deletion diagrams showing a few common scenarios. --Aelon (talk) 10:32, 22 December 2007 (UTC)