External memory model

In theoretical computer science, the external memory model (also called the I/O model or disk access model) is a model of computation that captures the behavior of computers that use magnetic storage. It captures the fact that read and write operations are much faster in a cache than in main memory, and that reads long contiguous blocks is faster than reading randomly using a disk read-and-write head. The running time of an algorithm in the external memory model is defined the number of reads and writes to memory required. The model was introduced by Alok Aggarwal and David Vitter in 1988. The external memory model is related to the cache-oblivious model, but algorithms in the external memory model may know the block size.

Model

The model consists of a processor with an internal memory or cache of size $M$, connected to an unbounded external memory. Both the internal and external memory are divided into blocks of size $B$. One input/output operation consists of moving a block of $B$ contiguous elements from external to internal memory, and the running time of an algorithm is determined by the number of these input/output operations.

Mathematical properties

Searching

See also: B-tree

Searching in the external memory model is possible using a B-tree with branching factor $B$. Using a B-tree, searching, insertion, and deletion can be achieved in $O(\log _{B}N)$ time (in Big O notation), which is asymptotically optimal.

Sorting

See also: External sorting

Using external sorting, such as a ${\frac {M}{B}}$-way merge sort, sorting in the external memory model is possible in $O({\dfrac {N}{B}}\log _{\frac {M}{B}}{\dfrac {N}{B}})$ time, which is asymptotically optimal.

See also

• Cache-oblivious algorithm