algorithmdata-structuresb-tree

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!


Solution

  • 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.