Insertion of n consecutive keys in an initially empty B-Tree

Question

Consider this question ( 18.2-4 of CLRS) which states that:

Suppose that we insert the keys ${1,2,...,n}$ into an empty B-Tree with minimum degree 2. How many nodes does the final B-tree have?

My approach:
We add each element one by one. We'll need 3 elements at first (namely 1,2 and 3), after which the $4th$ element will cause a split. This split is a root node split.
A normal node split results in one extra node.
A root node split results in 2 extra nodes.
Thus after the 4th element we have 3 nodes in total. Now, as we keep on adding more elements to the B-tree, we can see a pattern in splitting. 3 lower level splits initially produce a higher level split, and then each higher level split will require 2 splits only. Since we've to approximate only, we can disregard the initial 3 split condition and go on with the 2 lower level splits to produce an upper level split.
Notice that there is atleast a split at the insertion of these elements: $4,6,8,10,12...... $
That are all even numbers leaving 2.
Thus total such splits are $n/2$
Total higher level splits are thus:$n/4$
Total splits for the higher level than the previous one: $n/8$
Thus the total splits until the $nth$ element is inserted in the B-Tree is:
$n/2+n/4+n/8+......$
Which results in $n$. This is more than expected. I've made two approximations here:
1) Number of higher level splits is equal to half of the immediate lower level splits.This increases our answer.
2) Some starting elements don't contribute to the splits.
Maybe these are the reasons why the answer is coming more. I can't enumerate these values exactly. Finding these values exactly would help me very much. Any help appreciated.
Moon

Answer 1

We know that every node except the root must have at least t−1=1 keys, and at most 2t−1=3 keys. The final tree can have at most n−1 nodes when n≥2. Unless n=1 there cannot ever be n nodes since we only ever insert a key into a non-empty node, so there will always be at least one node with 2 keys. Next observe that we will never have more than one key in a node which is not a right spine of our B-tree. This is because every key we insert is larger than all keys stored in the tree, so it will be inserted into the right spine of the tree. The fewest possible number of nodes occurs when every node except the deepest node in the right spine has 2 keys and the deepest node in the right spline has 3 keys. So at height 1, 1 nodes, at height 2, 3 nodes, …, at level h, 2h−1 nodes. In this case, n =2^(h+1)−1 where h is the height of the B-tree, and the number of nodes in B-Tree is #nodes = 2^(h+1)−2−h = n−lg(n+1). So for any n, the final B-Tree must have n−⌊lg(n+1)⌋≤#nodes≤n−1 (if n≥2).