656 views

| 656 views
0
maxm=4 min=3 . root at level 1.
0
how can i find that
0
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.
0

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..

0
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 .
+1

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

8*(2p-1)<=212

2p-1<=29

p<=513/2

p=256

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

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

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

0
@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?
0

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?

0
i think i am not getting the clear aspect of what the question is saying. though i will try this once.
0
@Vishnathan min =3 max =4 is this the answer?
0
@minipanda : see the solution i did it .

@prince : yes bro u are right.

#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) :

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) =

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

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

by Boss (12.1k points)
edited by
+1
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
0

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

+1

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.

​​​​​

0
thanks (y)
0
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 ?