The Gateway to Computer Science Excellence
0 votes

in Databases by Junior (513 points) | 688 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


by Boss (12.2k points)
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 ?
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,388 answers
105,414 users