Difference between B-Trees and 2-3-4 Trees
What is the difference between B-Trees and 2-3-4 Trees?
Also, how would you find the maximum and minimum height of each?
Answer
...a link to Wikipedia and a quote:
"2-3-4 trees are B-trees of order 4."
A 2-3-4 is a B-tree.
It is called 2-3-4 tree because the number of children for a non-leaf, non-root node is 2,3 or 4.
Had it been 6, it could have been called a 3-4-5-6 tree, or 3-6 tree for short.
Since the minimum number of children is half of the maximum, one can just usually skip the former and talk about a B-tree of order m.
The order of a B-tree is defined as the maximum number of children a node can have.
In a 2-3-4 tree, as we have seen, the maximum is 4.
It's worst and best-case height is given by the general formula for B-trees.
Best case: logmn. (all nodes are full)
Worst case: logm/2n. (all nodes are half-empty)
where
- m is the order of the tree - the maximum number of children a node can have, in this case, 4 - and
- n is the number of entries in the tree
"B tree can have an order of any number " - yes, but for a particular subclass of B-trees, you fix that number in advance. It's like talking about butterflies in general vs talking about the Monarch butterfly. B-trees are a class of data structures, just like butterflies are a class of insects. Monarch butterflies are a subclass of butterflies, just like 2-3-4 trees are a subclass of B-trees.