Made Easy

Question

Amy and Bob are working on a project vehicle rental system, they have a file consisting of 10000 records, having block size 1024 bytes, record size 100 bytes. Search key size 9 bytes, pointer 7 bytes. They want to implement single level indexing. Bob suggested to implement 1st level index using dense index, however Amy suggested to implement sparse index. How many blocks are saved by Amy considering only 1st level index ________?

Comments

Correct answer: 141

Answer 1

Blocking factor of Data Blocks  =    No of records per block

                                               =   $\left \lfloor \frac{Data block size}{record size} \right \rfloor$

                                     = $\left \lfloor \frac{1024}{100} \right \rfloor$ = 10

Total no of Data Blocks              =    Total no of Records / Blocking factor

                                    =   $\left \lceil \frac{10000}{10} \right \rceil$ = 1000      

   

---

Amy’s implementation using Sparse Index :-   

                                           

Index entry size   =  Search key size + Pointer to the Data block in which the particular record is located                                              

                                =>  9 + 7 = 16 Bytes

 

Considering  Index Block size = Data Block size;

 

Blocking factor of Index Block =   No of index entries per block 

                                             =     $\left \lfloor \frac{Data block size}{index entry size} \right \rfloor$        

                                   =    $\left \lfloor \frac{1024}{16} \right \rfloor$ = 64

                                                  

                                       Sparse index ensures an index entry in index block for each Data block 

                                                         Total no of Index entries =  Total no of Data Blocks 

 

No of Index blocks required using Sparse implementation  =   Total no of index entries / Blocking factor of Index block

                                                                     =   $\left \lceil \frac{1000}{64} \right \rceil$ = 16  

---

Bob’s implementation using Dense Index :-   

 

                                 Dense index ensures an index entry in index block for each Record of all Data Blocks 

                                                         Total no of Index entries =  Total no of Records 

 

No of Index blocks required using Dense implementation  =   Total no of index entries / Blocking factor of Index block

                                                                     =   $\left \lceil \frac{10000}{64} \right \rceil$ = 157

---

 

No of blocks  saved by Amy considering only 1st level index  =  157 – 16

                                                                                                             =  141