can you post the solution ?? Sinchit

Dark Mode

0 votes

3 votes

Best answer

The answer should be 10. In a B+ tree the data is stored in the last level i.e on the leaf node. So going by the question-

Order_leaf=2

Order_internal=3

Thus for a complete b+tree each internal level should have order_internal children.

if order is k and tree is complete-

Level 1 has k-1 keys and k children

Level 2 has k*(k-1) keys and k*k children if its internal node

Level 3 has k*k*(k-1) keys and k*k*k children if its internal node

and so on

Clearly here we have two levels of internal node whihc means k*k children i.e 3*3=9 leaf nodes

Also the order of leaf node is 2 so the number of total keys at leaf nodes=

No of leafnodes* order_leaf=9*2=18

Clearly here only 8 keys are present in leaf nodes so we can have 10 more keys inserted.

Order_leaf=2

Order_internal=3

Thus for a complete b+tree each internal level should have order_internal children.

if order is k and tree is complete-

Level 1 has k-1 keys and k children

Level 2 has k*(k-1) keys and k*k children if its internal node

Level 3 has k*k*(k-1) keys and k*k*k children if its internal node

and so on

Clearly here we have two levels of internal node whihc means k*k children i.e 3*3=9 leaf nodes

Also the order of leaf node is 2 so the number of total keys at leaf nodes=

No of leafnodes* order_leaf=9*2=18

Clearly here only 8 keys are present in leaf nodes so we can have 10 more keys inserted.

1

Actually in leaf node of B+ tree number of keys = number of child pointers. Because each pointer points to a specific record. So we can assume here order of leaf node=number of children=number of keys.

PLease refer this-

https://en.wikipedia.org/wiki/B%2B_tree#Overview

1