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

if this type of question come in GATE as numerical answer !!. than how we can conclude that we have to take our answer as 340 or 341 .???? ho we will distinguish between above those two method that u have expalin.???

---

you have to take the floor value , in case pointer .

and for block size if asked then we have to take the celin value .

---

i did not understand properly.?? :(

---

--->  (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.