Solution

The correct answer is 5

Key Points 

• Formula:
  • Considering all nodes are completely full means every node has N − 1 key.
• If a new key is inserted, then at every level there will be a new node created, and in the worst-case root node will also be broken into two parts. Since we have 4 levels, then 5 new nodes will be created 

Additional Information 

• Diagram needs to be updated
• First, the overflow happens at the leaf, and second on the parent of that leaf, and so on until the last overflow happens at the root node.

• Therefore 4 nodes are created

​If the database table has h levels and the level of the root node is 1 then on a new key insertion, the maximum number of nodes newly created is h + 1