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

algorithm data-structures b-tree
Kiril Kirov picture Kiril Kirov · May 31, 2011 · Viewed 8.6k times · Source

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!

Answer

Apoorv picture Apoorv · May 31, 2011

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.

Related questions

How to implement a queue using two stacks?

Suppose we have two stacks and no other temporary variable. Is to possible to "construct" a queue data structure using only the two stacks?

Read More
How to create the most compact mapping n → isprime(n) up to a limit N?

Naturally, for bool isprime(number) there would be a data structure I could query. I define the best algorithm, to be the algorithm that produces a data structure with lowest memory consumption for the range (1, N], where N is a …

Read More
What is the difference between tree depth and height?

This is a simple question from algorithms theory. The difference between them is that in one case you count number of nodes and in other number of edges on the shortest path between root and concrete node. Which is which?

Read More