B+ TREE

Question

Comments

can you post the solution ?? Sinchit

---

If I had a solution, I wouldn't have asked it.

---

with my respect answer should be 4

 I'm also waiting for someone for clarification

Answer 1

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.

Comments

Tejasvi96  thanks

---

Tejasvi96   can you clear my one more doubt ..if it's given that the order of leaf node = 3 then it means number of keys we inserted  inserted = 3

and if it's given that order of the internal node = 3 that means 2 keys we can  inserted and each internal node have 3 children

it's right ??

---

@ magma right

bt in gate question they will say what they meant by order of leaf and order of node

---

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

 

---

Thanks to both