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

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 .