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

From the above book,

B* 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.^{}-tree

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

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?