The Gateway to Computer Science Excellence

0 votes

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.

.

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(10^{6}/128) and min. no. of leaves=3922 :ceil(10^{6}/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 .

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

and they have asked gaiven us records not key .

0

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

i mean pointer should be 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 : 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?

+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 min ^{m} ht) : **

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

b^{h-1 }=1000000/255

h-1 = log _{256 }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

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

+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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,388 answers

198,576 comments

105,414 users