At most how many keys can be inserted without splitting the root node?

Consider the following B+ tree:

13 keys. This is a tedious, but simple count. As in (a), we should be adding keys as conservatively as possible trying to delay splits as long as possible.

Add 3 keys, b, i, m, to fill up the free spots at the leaves.

Add 2 keys: c to n1 and j to n3. This will split those nodes and will ll up m1 and m2.

Add 2 keys, d and jj, to fill up the free slots in the newly created leaves.

Add 1 key, ee, to n2 to split it into n21 and n22. This will cause a split of m1 into m11 and m12 causing the root to be filled up. This stage of the tree is depicted below:







Now, adding 2 keys to n22 will split it into n221 and n222 and will fill up m12.

Add 1 key to n222 to fill it up.

Add 1 key to n12. This will split it up into n121, n122 and fill up m11. n121 will be full, but n122 will have one free slot.

Add 1 key to n122.

At this stage, all slots in the tree will be occupied and adding any additional key will cause a split at the root. It is easy to see that we have added 3+2+2+1+2+1+1+1=13 keys.