Kerala PSC AP Exam

Question

A B-tree used as an index for a large database table has four levels including root node. If a new key is inserted in this index, then the maximum number of nodes that could be newly created in this process are

A) 5

B) 4

C) 3

D) 2

Answer 1

Starting from the last level, if we do a new entry, then the node may be filled and split into 2 nodes and middle element goes one above.. similarly at third level on adding middle element that node may get filled and requires splitting and split into two nodes.. similarly for level 2 and level 1(root level)..

then max number of nodes that could be created is 4.

Comments

I don't understand.if possible can you explain with diagrams

---

See,if any element will come it will first try at any leaf node and splitting will happen that element will go at upper level (internal node) again there splitting will happen bcoz as per question "maximum node"...this will be happening till root node ...so number of newly node created will same as number of levels

---

Mam actually i think answer should be 5 because at every level one new node is created (considering overflow condition at every node) and additionally one new root will be created as there is overflow in the root so answer should be 4+one new root

Correct me if i am wrong