The notion of external memory includes a large number of possible different devices, each of which has its own block size and is accessed with its own collection of system calls. To simplify the exposition of this chapter so that we can focus on the common ideas, we encapsulate external memory devices with an object called a . A stores a collection of memory blocks, each of size . Each block is uniquely identified by its integer index. A supports these operations:
The easiest way to imagine a is to imagine it as storing a file on disk that is partitioned into blocks, each containing bytes. In this way, and simply read and write bytes of this file. In addition, a simple could keep a free list of blocks that are available for use. Blocks freed with are added to the free list. In this way, can use a block from the free list or, if none is available, append a new block to the end of the file.