B-Tree - I don't get the "minimal degree" thing

Question

I'm trying to implement a B-Tree according to the chapter "B-Trees" in "Introduction To Algorithms"... what I don't quite get is the "minimal degree"... it says it's a number which expresses the lower/upper bound for the number of keys a node can hold. It it further says that:

1. every non-root node stores at least t-1 keys and has t children
2. every node stores at most 2t - 1 keys and has 2t children

So you get for t = 2

1. t-1 = 1 keys and t = 2 children
2. 2t-1 = 3 keys and 4 children

for t = 3

1. t-1 = 2 keys and t = 3 children
2. 2t-1 = 5 keys and 6 children

Now here's the problem: It seems that the nodes in a B-Tree can only store an odd number of keys (when full)?! Why can't there be a node with, let's say at most 4 keys and 5 children? Does it have something to do with splitting the node?

Answer 1

it's not impossible but suboptimal. how do you split a node with an odd number of children?

Answer 2

It seems that the nodes in a B-Tree can only store an odd number of keys?

Definitely not. The numbers you have written is minimal/maximal respectively, so for t=2, nodes with 1,2,3 keys are allowed. For t=3, 2,3,4,5 is allowed, + the root of the tree is allowed to have only one key.

It is possible to define (and implement) trees that have eg. 1 or 2 keys in a node (so-called 2-3 trees). The reason B-trees are defined to accommodate one more, is that this leads to faster performance. Particularly, this allows amortized O(1) (counting splitting and joining operations) delete and insert operations.