Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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!

like image 941
Kiril Kirov Avatar asked May 31 '11 06:05

Kiril Kirov


People also ask

What are the differences between B-tree and B+ tree?

B+ tree is an extension of the B tree. The difference in B+ tree and B tree is that in B tree the keys and records can be stored as internal as well as leaf nodes whereas in B+ trees, the records are stored as leaf nodes and the keys are stored only in internal nodes.

How b * tree is different from B-tree in file structure?

Deletion in B+ tree is very fast because all the records are stored in the leaf nodes so we do not have to consider the child of the node. In Btree, sequential access is not possible. In the B+ tree, all the leaf nodes are connected to each other through a pointer, so sequential access is possible.


2 Answers

Edited No difference other than min. fill factor.

Page #489

The Great Book

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.

like image 170
Apoorv Avatar answered Nov 14 '22 04:11

Apoorv


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.

like image 43
mkn Avatar answered Nov 14 '22 05:11

mkn