8,175 views
0 votes
0 votes

1 Answer

3 votes
3 votes

#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 minm ht) : {\displaystyle n_{\max }=b^{h}-b^{h-1}}

                                         1000000= bh-1(b-1)

                                         bh-1  =1000000/255

                                         h-1 = log 256 3922

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

                                     height = level-1 = 2

minimum records stored(for maxm ht) =    {\displaystyle n_{\min }=2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-1}-2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-2}}

                                       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 formulahttps://en.wikipedia.org/wiki/B%2B_tree

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

edited by

Related questions

0 votes
0 votes
1 answer
1
Salazar asked Jan 29, 2018
3,931 views
Maximum height of a B+ tree of order m with n key values is (With Derivation), the answer is known Logceil(m/2) NI tried deriving but had some trouble, could someone assi...
0 votes
0 votes
0 answers
2
bts1jimin asked Jan 9, 2019
375 views
Can anyone suggest me any useful source from where I can read b+ tree insertion and deletion?
2 votes
2 votes
2 answers
3
aditi19 asked Nov 23, 2018
1,600 views
what is the minimum and maximum number of keys for non-leaf nodes and leaf nodes for B+ Tree of order p?