The Gateway to Computer Science Excellence
+1 vote
39 views

Database file consist 50000 records with record size 100 bytes, block size 512 bytes. If sparse B+ tree index build over given database file with search key size 20 bytes both block pointer and record pointer sizes 12 bytes each. How many maximum index blocks required if node order P is defined as between ⎡P/2⎤ to P pointers per node?

what should be answer 1631 or 1426  ??

in Databases by Active (3.6k points) | 39 views
0

Answer will be 1431.

Total blocks = 10000

Order of leaf node =

p(12+20) + 12 <= 512, hence p = 15

Order of non leaf = 

p'(12) + (p'-1)20 <= 512, hence p' = 16

Now to maximize the nodes we would take min elements in each node

i.e leaf node will get ceil(15/2) = 8 and non leaf will get ceil(16/2) = 8

Hence total nodes at bottom level = 10000/8 = 1250

at one level above 1250/8 = 157

then 157/8 = 20

then 20/8 = 3

then 1 node

Hence total nodes required = 1250 + 157 + 20 + 3 + 1 = 1431

0
yes this is right 1431 is correct

 

but in made easy test  answer given is 1631

firstly they have written index for 10000 key  10000/7=1428  then for 1428 node 1428/8=178  178/8=22 and so on

in more cases they are taking this approach

 

but for 10000 blocks we should divide by min Block pointer not by key RIGHT??
0
for 10000 blocks we need to index using leaf nodes.so order of leaf nodes = 15 And min will be ceil(15/2) = 8.

But they took it 7.

And hence there difference is occured.
0

@Ashwin Kulkarni in your answer you have used ceil(1250 / 8) =157

but I think this approach is not correct.

see 156*8=1248 and now only 2 pointer needed to point to below level. But now with your approach only 2 pointers will be present in 157th node means only 1 key. but minimum 8 pointers are required in a internal node.

so we would have to take floor function. And now those two pointers will be distributed in any of our 156 nodes. As each node can have 8 to 16 pointers.

now ans will be

floor(10000/8)=1250

floor(1250/8)=156

floor(156/8)=19

floor(19/8)=2

now at root node we can have 1 key and 2 pointers hence 1 node for root.

so total index blocks=1250+156+19+2+1= 1428

 

Please log in or register to answer this question.

No related questions found

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,654 questions
56,169 answers
193,878 comments
94,301 users