Exercise 18.1-1

Why don’t we allow a minimum degree of \(t = 1\)?

Consider a hypothetical non-empty B-tree with \(t = 1\). By property 5a, the root node has at least one key. Additionally, every node has at least \(t-1\) keys and since B-tree nodes cannot have 0 keys without being considered a leaf, we know each non-leaf node has at least one key. Property 5b says each node may contain at most \(2t-1\) key and at most \(2t\) children. So our \(t = 1\) B-tree has at most \(1\) key and \(2\) children.

Thus \(t=1\) is basically describing a form of binary search tree and includes no specifications that cannot also be reached by setting \(t=2\). Because of this, and the fact that \(t=1\) inaccuratly includes minimum caes that cannot exist, we need not allow \(t\) values less than 2.