B-Trees

External memory overview

An implicit assumption of the $w$-bit word-RAM model is that our computer has a large enough random access memory to store all of the data in the data structure. In some situations, this assumption is not valid. There exist collections of data so large that no computer has enough memory to store them. In such cases, the application must resort to storing the data on some external storage medium such as a hard disk, a solid-state disk, or even a network file server (which has its own external storage).

Accessing an item from external storage is extremely slow. The hard disk attached to the computer on which this module was written has an average access time of $19$ms and the solid-state drive attached to the computer has an average access time of $0.3$ms. In contrast, the random access memory in the computer has an average access time of less than $0.000113$ms. Accessing RAM is more than $2,500$ times faster than accessing the solid-state drive and more than $160,000$ times faster than accessing the hard drive.

These speeds are fairly typical; accessing a random byte from RAM is thousands of times faster than accessing a random byte from a hard disk or solid-state drive. Access time, however, does not tell the whole story. When we access a byte from a hard disk or solid-state disk, an entire block of the disk is read. Each of the drives attached to the computer has a block size of $4,096$; each time we read one byte, the drive gives us a block containing $4,096$ bytes. If we organize our data structure carefully, this means that each disk access could yield $4,096$ bytes that are helpful in completing whatever operation we are doing.

In the external memory model, accessing an individual item, $x$, in the external memory requires reading the entire block containing $x$ into RAM.