What order B-tree is this?

Question

I am studying B-trees and reading Introduction to Algorithms by Cormen et al.

Unfortunately, they have this diagram Figure 18.1 and they do not list the order of the tree.

I understand that for a B-tree of order $m$, the tree has 5 properties:

1. Every node has at most $m$ children.
2. Every internal node except the root has at least $\left\lceil \frac{m}{2}\right \rceil$ children.
3. Every non-leaf node has at least two children.
4. All leaves appear on the same level and carry no information.
5. A non-leaf node with $k$ children contains $k−1$ keys.

Based on this however, I wasn't sure if you could just tell the order of a given tree. To me, it seems this looks like it could be order 4,5, or 6. By the $\left\lceil \frac{m}{2}\right \rceil$ criteria, 6 would be the most since 6/2 = 3 and therefore anything larger would automatically mean that this criteria wouldn't be satisfied for the node with keys D,H.

Is the order of a B-tree unique? If so, what is the order of this B-tree?

Answer 1

Good question.

You have given the answer. A B-tree of order $4$ can also be a B-tree of order $5$ or $6$. So, "the order" of a B-tree may not be unique.

Knuth, who gave the definition of B-tree as in the question, avoids the problem of non-uniqueness by defining the order to be the maximum number of children of a node, which is one more than the maximum number of keys. [1]

So, according to Knuth, the order of the B-tree in the question is $4$.

[1] Knuth, Donald (1998), Sorting and Searching, The Art of Computer Programming, vol. 3 (Second ed.), Addison-Wesley, ISBN 0-201-89685-0. Section 6.2.4: Multiway Trees, pp. 481–491.