Test by Bikram | Mock GATE | Test 1 | Question: 41

Question

A file has $2^{29}$ records each of size 8B. One block of main memory is $128B$.  Sparse indexing is done with one index record per memory block and one index record is of $1$ $Byte$. The blocks stored by the index records are stored in disk. Blocks occupied by index are searched using binary search technique. Maximum number of blocks need to be read is _____.

Answer 1

Total records = 2^29,   One record = 8B,    Number of records/block = l28 B/8 B = 16
 
Number of block =  2^29 / 2^4 = 2^25 ,  One index record per block.  So total number of index records = 2^25

One index record = 1B .  Number of index records / block = 128  .  Index occupies = 2^15 / 2^7 =  2^18 blocks

 Binary search requires as many as, [ log2 2^18] blocks to be read = 18

and  1 more for accessing the record so in total 18+1= 19 blocks are needed to read.

Reference ( why need to add extra block )

Comments

@srestha

did you read that ME question carefully ?

there multilevel index at first level index along with sparse index at first level  used, both are not same.

In this qstn only sparse index is used..

---

In ME question , in 1st level block directly accessed using number of records a block can access.

And

from 2nd level block accessed using key.

It is done similar like primary indexing.rt?

So, where difference.

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

In the given question we use index pointer (in ME question similarly  it is used as key)

---

I THINK "to access data should be added" then only 18+1

or will i do the same when i get such Q???