11

I know about this question, but it's about B-tree and B+-tree. Sorry, if there's similar for B*-tree, but I couldn't find such.

So, what is the difference between these two trees? The wikipedia article about B*-trees is very short.

The only difference, that is noted there, is "non-root nodes to be at least 2/3 full instead of 1/2". But I guess there's something more.. There could be just one kind of tree - the B-tree, just with different constants (for the fullness of each non-root node), and no two different trees, if this was the only difference, right?

Also, one more thing, that made me thing about more differences:

"A B*-tree should not be confused with a B+ tree, which is one where the 
leaf nodes of the tree are chained together in the form of a linked list"

So, B+-tree has something really specific - the linked list. What is the specific characteristic of B*-tree, or there isn't such?

Also, there are no any external links/references in the wikipedia's article. Are there any resources at all? Articles, tutorials, anything?

Thanks!

Community
  • 1
  • 1
Kiril Kirov
  • 37,467
  • 22
  • 115
  • 187
  • "Not a real question" ? What is the "not real" part here? – Kiril Kirov May 31 '11 at 06:53
  • can you give a bit of context? if there's so little info about B*-trees, how did you become interested in them? a) out of curiosity, but also b) because it may help people think into the right direction – Nicolas78 May 31 '11 at 08:31
  • I haven't said, that "there's so little info about B*-trees". Short wikipedia article doesn't mean that there's no info in the net and that these trees are unfamiliar. Also, I don't think, that the reason I'm interested in B*-trees is important.. :) Anyway. I'm just learning advanced data structures and I didn't note any other differences, than the different fullness. And I wanted to ask for some help :) We're here for that, right? – Kiril Kirov May 31 '11 at 08:55
  • didn't mean to criticize the fact that you're asking. just had the intuition that if there's a particular use case, you might get additional answers. happens often to me: "no idea what that's... oh that's what he's talking about". nevermind :) – Nicolas78 May 31 '11 at 09:14
  • You're right, but no - no other information. Just out of curiosity (: – Kiril Kirov May 31 '11 at 09:55

2 Answers2

14

Edited No difference other than min. fill factor.

Page #489

The Great Book
(source: mit.edu)

From the above book,

B-tree* is a variant of a B-tree that requires each internal node to be at least 2/3 full, rather than at least half full.

Knuth also defines the B* tree exactly like that (The art of computer programming, Vol. 3).

"The Ubiquitous B-Tree" has a whole sub-section on B-trees*. Here, Comer defines the B-tree* tree exactly as Knuth and Corment et al. do but also clarifies where the confusion comes from --B-tree* tree search algorithms and some unnamed B tree variants designed by Knuth which are now called B+-trees.

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
Apoorv
  • 1,091
  • 6
  • 19
1

Maybe you should look at Ubiquitous B-Tree by Comer (ACM Computing Surveys, 1979).

Comer writes there something about the B*Tree (In the section B-Tree and its variants). And in that section, he also cites some more paper about that topic. That should help you to do further investigations on your own :)! (I'm not your researcher ;) )

However, I don't understand the point where you cite a part which says that the B*Tree does not have a linked list in the leaf node level. I'm pretty sure, that also those nodes are linked together.

Regarding having only one B-Tree. Actually, you have that. The other ones like B+Tree, Prefix B+Tree and so on are just variants of the standard B-Tree. Just look at the paper Ubiquitous B-Tree.

mkn
  • 12,024
  • 17
  • 49
  • 62
  • Not yet. +1 from me for pointing me to the paper. I'll read it later, as I can't now. And no, I didn't post here, to find a "researcher", but just to ask someone to point me to some papers/tutorials/implementations/etc, as I already noted in my question ;) – Kiril Kirov May 31 '11 at 10:17