I/O Model of Computation
The Rule: Dominance of I/O cost
- The time taken to perform a disk access is much larger than the time needed for manipulating data in the main memory
- Thus, the number of block accesses (Disk I/Os) is a good approximation to the time needed for an algorithm
Example
- read a block is ~11 mls (see Secondary Storage#Accessing)
- search for a tuple within a block when it's in the main memory is ~1000 instructions (even with sequential search)
- i.e. search in the main memory is less than %1 of the block access time, can neglect it safely
Sources