Database is divided into logical blocks and each block contains data. CPU works along with RAM. One by one Block loads into the RAM and CPU reads the block if the record is not found then another block will load into the memory. If we need to store 10000 records and 1 block can store 100 records. No. of blocks required = 10000/100->100 blocks. Indexing basically reduces the I/O cost means it reduces the number of blocks that get loaded in the RAM. Block Size -> 1000 Bytes Record Size -> 250 Bytes Total No of records -> 10000 Records in a block -> 1000/250-> 4 records Total No of blocks required -> 10000/4 -> 2500 Suppose it is taking 1 ms to read 1 block. In best case it will take -> 1 ms In worst case, it will be the last record -> 2500 ms Average Case -> 2500/2 = 1250 (N/2) If the data is sorted then we can implement binary search. Time Complexi...
