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!
Edited No difference other than min. fill factor.
Page #489
(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.