CODEWITHSUNDEEP
algorithmdata-structuresb-tree
Kiril Kirov
Kiril Kirov

Reputation: 38173

What are the differences between B-tree and B*-tree, except the requirement for fullness?

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!

Upvotes: 11

Views: 9109

Answers (2)

Apoorv
Apoorv

Reputation: 1101

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.

Upvotes: 14

mkn
mkn

Reputation: 13081

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.

Upvotes: 1

Related Questions