B+Tree

Question

1.Following key values are inserted into B+ tree where each node have 2 key values .The sum of keys present    at height 1 (height is at 0) is 8,5,1,7,3,12,9,6 .

2.In a database field the search key field is 9 bytes long the block size is 512 bytes , a record pointer is 6 bytes and block pointer is 7 bytes .The largest possible order of a non leaf node in B+ Tree implementing this file structure{order defines max no. of keys present} is

Comments

whats  the given ans for 1st one is it 29 ?

Answer 1

1st one i'm not getting it..

for 2nd :

given,  search key field=9B

            Record Pointer=6B ,

           Block Pointer=7B

           Block Size=512B

leaf node in B+tree:

             Block_pointer+P*(Search_key_field+Record_Pointer) <=Block_Size  "here P is order"

non-leaf node in B+tree:

              P*Block_pointer +   (P-1)*Search_key_field   <=Block_Size  

So,    P*7 + (P-1)9  <= 512
              16P   <=  521

          P<=32.5 means P=32

Order P=32 So max. number of key present in non leaf node is 32-1=31 (Ans)

Comments

I think Order of leaf node in a B+ Tree is P*k+P*r+ b = block size and 2nd formula what u have written is for B- tree.

As per the que 2 i m also getting this but doubt is as Search key field is Less than block size so p comes out to be 32  , But ans given is 31 as but in que.The largest possible order of a non leaf node in B+ Tree is asked  then why 31 is the ans.

---

ohh yes you are right 2nd formula belong to B tree my mistake correcting ....
largest possible order is based on the condition <=Block_size ..
if in question it is leaf node then we get order=34 and key=33

---

@akanksha formula mentioned in the answer is correct. Formula u are telling is for ordrr of leaf node. I have cross chked it.

www.ctp.bilkent.edu.tr › BPlusTrees