6,379 views
2 votes
2 votes
Consider a disk with block size B=512 bytes. A block pointer is p=6 bytes long and a record pointer is R=7 bytes long. A file has 30,000 employee records of fixed length. Each record has 100 bytes. Assume that un-spanned organization is used to store records and SSN takes 9 bytes. Suppose that the file is ordered by the key field SSN and we want to construct  a primary index(sparse) on SSN . Find the number of block access required to retrieve a record from the file using single level index and binary search?

Please help me to find the answer...

1 Answer

Best answer
3 votes
3 votes

B = 512 B

#records = 30000

record size = 100 B

Using unspanned organization,

block factor for data ( #records per block) = $\left \lfloor \frac{512}{100} \right \rfloor$ = 5

So, number of blocks for data file = $\frac{30000}{5}$ = 6000

Index size = key field size + block pointer = 9 + 6 = 15B

block factor for index (#index entries per block) = $\left \lfloor \frac{512}{15} \right \rfloor$ = 34

In sparse primary indexing, number of entries in index file is equal to number of data blocks.

$\therefore$ Number of entries in index file = 6000

So, number of blocks for index file = $\left \lceil \frac{6000}{34} \right \rceil$ = 177

Now, average block accesses to retrieve a record from the file using binary search =$\left \lceil log_{2} 177 \right \rceil$ (to perform binary search) + 1 (to access the block where desired record is present) = 8 + 1 = 9

Hence, total 9 block accesses are required.

selected by

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
3
vishnu777 asked Nov 8, 2022
391 views
Can anyone explain in detail about the concepts of sencondary indexing in dbms??
0 votes
0 votes
0 answers
4
Purple _ rain asked Sep 3, 2022
136 views
What is fanout ratio