Difference between B-Trees and 2-3-4 Trees

Question

What is the difference between B-Trees and 2-3-4 Trees?

Also, how would you find the maximum and minimum height of each?

Solution

...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: log_mn. (all nodes are full)
Worst case: log_m/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.

Comments

[jrouquie]

You can have cascade splitting in B Trees: en.wikipedia.org/wiki/B_Tree#Insertion