Log In
0 votes

in Databases 1.6k views
maxm=4 min=3 . root at level 1.
how can i find that
see what i did first was i found degre of node means for leaf node and internal node as both were different.


now i used maximum degree for finding minm height when each node was full.

and i used minimum degree for finding maxm height when root node has 1 element and other nodes has ceil(p/2)-1 elements.

arvin Can you tell me the no. of leaf nodes you got in each case and also the degrees..?

I am getting max block pointers in internal node: 256, min:128

For leaf nodes, max no. of key values :255 and min 128.

And do you start this type of problems from leaf nodes?

I am getting max no. of leaf nodes=7813 : ceil(106/128) and min. no. of leaves=3922 :ceil(106/255)

Where am i going wrong..

minimum is 38 i am getting. can u recheck its for internal node :

(p-1)key + p (bp) <=4k (4000)

and they have asked gaiven us records not key .

(p-1)*8 + p*8 <= 212





Please help arvin 

@minipanda : aargh :/ yes u correct :) i saw record pointer as block pointer.

i mean pointer should be block pointer.
I took block pointer and record pointer of same size as they haven't mentioned anything explicitly :/
@minipanda : wuhuu bingo :p no i think the record size is for record pointer.

arvin Oohh...!! 100 B for pointer! :O that is too much! :P :P

@minipanda : yes i think so . its for that only. because if u are considering the bp and rp as equal than oder of leaf node or internal node will be same... i am not sure why they gave 100B for record pointer or just a dead code or to find thr total size of records or what?

arvin I have seen some problems where the order of leaf and non leaf nodes are same..and the record size is usually around 64B 100B etc.. but record pointer size 100B is sounding weird..

Vishnathan Do you know the answer?

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.

1 Answer

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


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 formula


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

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

 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 ?

Related questions

0 votes
1 answer
Maximum height of a B+ tree of order m with n key values is (With Derivation), the answer is known Logceil(m/2) N I tried deriving but had some trouble, could someone assist with the derivation or derivation process ?
asked Jan 29, 2018 in Databases Salazar 1.4k views
0 votes
0 answers
Can anyone suggest me any useful source from where I can read b+ tree insertion and deletion?
asked Jan 9, 2019 in Databases bts1jimin 113 views
1 vote
2 answers
what is the minimum and maximum number of keys for non-leaf nodes and leaf nodes for B+ Tree of order p?
asked Nov 23, 2018 in Databases aditi19 328 views
1 vote
1 answer
Which of the following statement true about B tree and B+ tree index? Assume order of B tree node same as order of B+ tree node. A. B tree index has more levels than B+ tree index for large number of keys. B. B+ tree index has more levels than B tree ... + tree best for sequential access of records. D. B+ tree index nodes more than B+ tree for large number of keys. Please Explain every Point.
asked May 12, 2018 in Databases Na462 503 views