GATE CSE 2023 | Question: 52

Question

Consider a database of fixed-length records, stored as an ordered file. The database has $25,000$ records, with each record being $100$ bytes, of which the primary key occupies $15$ bytes. The data file is block-aligned in that each data record is fully contained within a block. The database is indexed by a primary index file, which is also stored as a block-aligned ordered file. The figure below depicts this indexing scheme.

Suppose the block size of the file system is $1024$ bytes, and a pointer to a block occupies $5$ bytes. The system uses binary search on the index file to search for a record with a given key. You may assume that a binary search on an index file of $b$ blocks takes $\left\lceil\log _{2} b\right\rceil$ block accesses in the worst case.

Given a key, the number of block accesses required to identify the block in the data file that may contain a record with the key, in the worst case, is _____________.

Comments

As far as I understand they asked worst case number of block accesses to do binary search on the index file, so isn’t the answer supposed to be 6?

---

@Deepak Poonia sir isn't the answer is 6?

---

@Kabir5454  @Tmajestical

Yes, the answer will be 6.

Detailed Analysis: Primary Index on Data File, Binary Search

---

I remember the question asked the number of block accesses we need to search for a record in the main database file which should be 7.

For e.g. we have 4 records (not index) in each block; let’s say one block contains (1,4,6,8) and the next block contains (10,12,15,18). We will have index files as (1,10,…..) and so on.

If we need to find if record 9 exists or not we can do a binary search on the sparse index (1,10,….) to get the first block 1 (i.e. 1,4,6,8) but we also need to check inside the block (one access more) to make sure if record 9 exists in the data file or not.

I may be horribly wrong, it is just coming into my head. And as far as I can remember it did not ask for the number of index block access for binary search. Can anyone confirm?

---

Using 6 block access we finally got the index block which has the block pointer for the main database block which has the record. in 6 th block access we fetch that index block. So Now we have search the record as we know in which block the record existing. We don't have to access the record if they say so then we need to fetch the block where the record is but we have to just search the record and that means search the block where record resides.

---

Oh okay then i misread. :(

---

@Deepak Poonia sir, thanks for confirming!

---

2 marks gone because I calculate number of block access required to access the record but question is asking to calculate the number of block access required to access the block in which record is present😭

Answer 1

Given that One block should fully contain within block so here it means that they are saying that you should use unspanned file organization.

Given that ,

$No. of Record$ $(Rn)$ $=25000$

$Record Size$  $(Rs)$ $=100Byte$

$Key Size$ $ (Ks)$ $=15 Byte$

$Block Pointer Size $ $(Ps)$ $=5Byte$

So that $ Index Size$  ($Is$) $=15 + 5 = 20 Byte$

$Disk$ $Block$ $Size(Bs) $ $=1024Byte$

---

 

No. of Record per Block$ =(Bs / Rs)$ $= \left \lfloor1024B/100B\right \rfloor$

                                                                $=\left \lfloor10.24\right \rfloor$

                                                                $=10.$

 

No of Block Required for blocks =$ceilvalue$( no of record / no of record per block)

                                                    = $\left \lceil 25000/10 \right \rceil$ 

                                                     = 2500 Block Required  to store all records

“The database is indexed by a primary index file” it means that here we have to use sparse indexing 

---

NO of Index per Block $= \left \lfloor(Bs/Is)\right \rfloor$ = floorValue($1024$/$20$) = $51$

NO of Block Required for indexes = CeilValue($No.OfIndex$/$No.OfIndexPerBlock$)

                                                      =  CeilValue($2500$/$51$) = 50 Blocks

---

 

Given That Binary Search is used to search the desired block and we know that it takes $log(n)$ Time to search in worst case where n= no of comparision Required = No. of Index Block here.

 

 the number of block accesses required to identify the block in the data file that may contain a record with the key, in the worst case, is.

= $log(50)$ = $6$ $Blocks$

 

Answer 2

Answer is 6 .