I learned B trees recently and from what I understand a node can have minimum t-1 keys and maximum 2t-1 keys given minimum degree t. Exception being root can have even 1 key.

Here is the example from CLRS 3rd edition Fig 18.7 (Page 498) where t=3

min keys = 3-1 = 2
max keys = 2*3-1 = 5

In the d) example when L is inserted why is the root splitted when it doesn't violate the B tree properties at the moment (It has 5 keys which is maximum allowed).
Why isn't inserting L into [J K L] without splitting [G M P T X] considered.
Should I always split the root when it reaches the maximum?

CodePudding user response：

There are several variants of the insertion algorithm for B-trees. In this case the insertion algorithm is the "single pass down the tree" variant.

The background for this variant is given on page 493:

Since we cannot insert a key into a leaf node that is full, we introduce an operation that splits a full node