+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  ??

| 39 views
0

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

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