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

shouldn't it be 19? 18 for binary search + 1 for accessing the record?

---

yes it should be 19

---

Sir,Why accessing the record is taken into account?

---

@Bikram Binary search stops by accessing the record we need right ? why the extra 1 read again for record ?  

http://www.cs.montana.edu/~halla/csci440/n18/n18.html

I see in this , they calculate average block needs to be read not by adding the last record access as you said. Please clarify.

---

@Junk_mayavi

we need to consider

see this

https://gateoverflow.in/83186/indexing

---

@ Bikram Sir

but why 1 more access?

that link is not telling 1 more access is required

---

at last we are doing binary search technique.

So, 18 should be ans.

why 19?

---

@Arjun Sir

is it here need to add 1?

---

I think 1 should be added.

We do indexing to search some record otherwise what do we need to search an index for!!

Ultimately our objective is to retrieve a record using indexing.

---

@srestha

To search for a record using the index, we need one additional block access to the data file for a total of 18 +1 = 19 block accesses neeeded.

To access actual data record , we need extra block .

Click here to read about it 

---

https://gateoverflow.in/116193/made-easy-test-series

Here in 2nd level indexing we are taking from 1st level of indexing.

But  here u r taking indexing from 30000, which is taken from not from primary indexing(which is now 3000 index)

Moreover it is sparse indexing. So, both cases should be same ,na?

---

Could you please tell more clearly. Not able to understand.

---

@ Gaurab  See both question and their corresponding answer.

Why they are getting different answer.

But both almost same question

---

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