in Databases
1,993 views
0 votes
0 votes

in Databases
by
2.0k views

4 Comments

can you post the solution ?? Sinchit

0
0
If I had a solution, I wouldn't have asked it.
0
0
with my respect answer should be 4

 I'm also waiting for someone for clarification
0
0

1 Answer

3 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.
selected by

4 Comments

@ magma right

bt in gate question they will say what they meant by order of leaf and order of node
1
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
1
Thanks to both
0
0

Related questions