B+ tree maximum and minimum height

Question

Comments

i think i am not getting the clear aspect of what the question is saying. though i will try this once.

---

@Vishnathan min =3 max =4 is this the answer?

---

@minipanda : see the solution i did it .

@prince : yes bro u are right.

Answer 1

#records= 1000000     #keysize=8B       #recordsize=100B      #pointersize=8B (as nothing is mentioned so i am assuming both i.e. index and block pointer to be equal to 8B).

as we know that when blockpointer=indexpointer(size) than the degree of internal node and the leaf node will be same.

so we need to find only one. so i am finding the degree of internal node. i.e,

p(BP) + (P-1)KEY<=4*1024

8(P) + 8(P-1)<=4*1024

2P-1<=512

P<=256.5                           ,  P=256.

---------------------------------------------------------------------------------------------

For a b order B+ tree with h level of index.

maximum record stored(for min^m ht) : 

                                         1000000= b^h-1(b-1)

                                         b^h-1  =1000000/255

                                         h-1 = log ₂₅₆ 3922

                                         h= ceil(1.49+1)  =3 (level) 

                                     height = level-1 = 2

minimum records stored(for max^m ht) =    

                                       1000000= 2 (ceil (b/2)^h-2 (ceil(b/2)-1))

                                                     = 2*ceil(b/2)^h-2 (127)

                                        ceil(b/2)^h-2= 3937

                                            h-2 = 1.70

                                           h= ceil(1.70+2)

                                         h= 4 (level) 

                                     height= level -1= 3

----------------------------------------------------------------------------------------------

source for formula : https://en.wikipedia.org/wiki/B%2B_tree

--------------------------------------------------------------------------------------------

Comments

h here denotes levels right? Then min height is 2 and max is 3 (height=level-1)?

I got it by some other method..it's tough for me to remember these formulae but Thanks for the help :D

---

MiNiPanda i know how to calculate min but how to calc max? i don't want to remember the formular

---

@Mk Utkarsh 

For max height we have to try to màke the nodes minimally filled. Note that the root node can have min. 1 key only.

​​​​​

---

thanks (y)

---

At first,when u say index pointer,u mean record pointer,rght?

How when index pointer & block pointer are same,order of data node and leaf nodes are same ? A data node contains key+index pointer + block pointer whereas index node or internal node contains only key+block pointer ?

---

B+ tree primary index means that indexing will b sparse but you have considered dense index why?

---

you didn’t consider the fact that its primary index means it is also sparse

so 2500 blocks and records are required in leaf node