9 Introducing the External-Memory Model

This chapter reframes algorithm analysis for data that lives beyond RAM by introducing the external-memory (Disk-Access) model. The central idea is that data transfer between disk and main memory dominates cost, while computation on data already in RAM is comparatively negligible. Data moves in blocks of size B, main memory has capacity M, and datasets of size N far exceed M. Because I/O operations are expensive and sequential access is far faster than random access (with reads often cheaper than writes), the chapter advocates measuring efficiency in number of block transfers, using Big-Oh bounds parameterized by N, M, and B. It also emphasizes that storage can mean HDDs, SSDs, or cloud systems—collectively termed “disk”—and that optimal on-disk data structures often look very different from their in-RAM counterparts.

Through concrete examples, the chapter builds intuition for I/O-efficient algorithm design. A linear scan to find a minimum costs Θ(N/B) I/Os, illustrating how a single pass over contiguous blocks is “linear time” in this model. Adapting binary search to disk yields roughly log2(N) comparisons but only about log2(N/B) block reads, since the last log2 B comparisons occur within the same block. The chapter then shows how reorganizing data to exploit each block fully leads to optimal searching via high-branching nodes (a B-tree view), reducing search to Θ(log_B N) I/Os—a dramatic improvement when B is large. It also presents K-way merging of sorted files: with one input block per list and an output buffer, a heap drives selection while the I/O cost remains Θ(N/B), revealing that external memory can merge many lists in a single linear pass when memory can buffer them.

Finally, the chapter discusses model fidelity and practicalities. Although the two-level RAM–disk abstraction hides real hierarchies (caches, multiple disks) and ignores important effects like sequential prefetching and random-access penalties, it remains a powerful guide; parameters M and B can be tuned to the level where data overflows. The model also allows parallelism across multiple disks and treats record sizes uniformly to keep analysis tractable. With this foundation—counting I/Os instead of CPU steps—the book proceeds to data structures and techniques optimized for external memory, notably B-trees (and their variants) for querying, and later write-optimized structures such as buffer trees and LSM trees.

: The external-memory model. This model is suitable for analyzing massive-data applications, where the cost of computation in RAM is subsumed by a much larger cost of transferring data from disk to main memory and back. Computation is not exactly free ---- but it is so much cheaper than that cost of transferring data that in many applications, it is effectively free.

: Finding a minimum in external memory. There is a total of 11 elements that occupy 4 blocks of size 3. The last block is not full. In this example, the beginning of the file is block-aligned.

: The difference in the way bounds look for in-RAM algorithm (left), and an equivalent on-disk algorithm (right.) It is important not to directly compare them as they represent different units. The comparison in the way the bounds look is there to understand how algorithms change as the consequence of different design.

: Binary search in external memory. The algorithm accesses a separate block for each pivot accessed, except from the last few pivots that all reside in the same block.

: How to transform a sorted array into a structure that enables optimal searching in external memory (a B-tree.) An optimal searching data structure in RAM look something like 9.5(d), where each node has one pivot based on which it is decided how to continue down the tree. The optimal searching data structure in external memory has large nodes (size of a block) that have many elements, because we pull data into memory block by block.

: Another difference in the way bounds can look in the RAM model and the external-memory model. Often, the runtime with a logarithm base 2 can turn into logarithm base B, as we can examine B different elements simultaneously with the help of block. Base 2 does not always turn into base B, as we will see later.

: K-way merging of sorted files. Each file has one block of data allotted in main memory, and through that block, each file sends its remaining minimum elements into the heap. Minima is repeatedly extracted from the heap and sent to the output. This scheme works independently on the total accumulated file size, as long as .

: Difference in the bounds between merging many sorted lists in main memory and in external memory. In external memory, we can merge many sorted lists with just one sweep over the input data. In internal memory, merging more than a constant number of lists results in more than linear cost in number of comparisons. This same internal-memory cost remains in our external-memory -way merging algorithm, it is just not the most important cost.

• Many data-intensive applications maintain large amounts of data on disk. Large files and large databases residing on disk need a different set of data structural and algorithmic tricks to function efficiently
• The external-memory model is a useful tool in analyzing algorithms for large datasets that can not fit into main memory. This model assumes that all data initially resides on disk of infinite size, and in order to perform computation, chunks of data are brought to and from the main memory of a limited size.
• The external-memory model foregoes the computation cost of an algorithm in order to emphasize the cost of data transfers that tend to be up to 1000x more expensive than computation operations in RAM.
• When scanning sequential data, external-memory algorithm will tend to have an “” part, suggesting that we packed items into consecutive blocks
• Unlike in internal memory, binary search is not the optimal searching algorithm in external memory, as it does not make a very good use of block inputs and outputs. A better runtime can be achieved by repackaging blocks and building a data structure called -tree.
• One major advantage of having a large main memory is that we can simultaneously merge a large number of sorted list/files, in just one linear sweep, independently of how large the total file sizes are. This process is also a base for the optimal external-memory sorting algorithm we study later.

FAQ