b+ tree order

Question

Assume block size 4096 bytes,size of key is 4 bytes,size of pointer is 8 bytes.How many keys are possible per blocks for b+ tree organisation?

(a) 155

(b) 154

(c) 341

(d) 340

Comments

i was solving in this way ...

p*key_size+(P+1)size of_pointer<=block size

where p is keys possible in b+tree node....
and getting p as 340.66667....after taking ceiling value.. ie (341)

is this method correct..??

---

For B+ tree

(m* block pointer)+(m-1)(key)<= Block size

so 8m+(m-1)4<=4096

12m<=5100

so m =341

---

correct option is (d) but i don't how it is.??

Answer 1

search field is V = 4 bytes long, the block size is B = 4096 bytes, and a block pointer is P = 8 bytes. As internal node of the B+ tree can have up to p tree pointers and p-1 search field values, these must fit into a single block. Hence, we have,
 
 
(p * 8) + (( p – 1 ) * 4 <= 4096
 
or (12 * p) <= 5000
 
p = 416.66 , So max keys are possible is 415 ( we cant consider the fraction )

But is this problem they done it this way 

 As internal node of the B+ tree can have up to p+1 tree pointers and p search field values, these must fit into a single block. Hence, we have,

 
(p+1) * 8 + p * 4 <= 4096
 
or (12 * p) <= 4088 

p = 340.66 , So max keys are possible is 340 ( we cant consider the fraction ) 

Comments

--->  (p * 8) + (( p – 1 ) * 4 <= 4096
--->(p+1) * 8 + p * 4 <= 4096

i did not understand which equation is to take .durng solving above  type of question??

link   https://gateoverflow.in/8555/gate2015-3_46 

in above link why they take that equation.?? why not this --> P*12+(P+1)*8<=1024?????

---

I dont know which equation to take (maybe hit and trail) , its kind a guessing game . If you guess right then bullseye :D .

---

i am confused between this which equation to use and  when .??

Answer 2

# of key =lower bound of ( block size/ (key + pointer))=lower bount of ( 4096/(4+8)= lower bound of (341.33)= 341

Comments

i was solving in this way ...

p*key_size+(P+1)size of_pointer<=block size

where p is keys possible in b+tree node....
and getting p as 340.66667....after taking ceiling value.. ie (341)

is this method correct..??

Answer 3

Ans: (d)

Order P = max. keys possible

So, the formula to use: P*K + (P+1)*Bp <= BS

Here, BS is block size, K is key, Bp is block pointer and P is order.

therefore, 4P + (P+1)8 <= 4096 gives 4P + 8P + 8 <= 4096 gives 12P <= 4088 gives P = 340.