As we did in , we make the basic assumption that sequential access to data is far less expensive than nonsequential access. Our model will be to consider whatever memory facility that we use to implement the symbol table as divided up into pages: contiguous blocks of information that can be accessed efficiently by the disk hardware. Each page will hold many items; our task is to organize the items within the pages such that we can access any item by reading only a few pages. We assume that the I/O time required to read a page completely dominates the processing time required to access specific items or to do any other computing involving that page. This model is oversimplified in many ways, but it retains enough of the characteristics of external storage devices to allow us to consider fundamental methods.
Definition 16.1 A page is a contiguous block of data. A probe is the first access to a page.
We are interested in symbol-table implementations that use a small number of probes. We avoid making specific assumptions about the page size and about the ratio of the time required for a probe to the time required, subsequently, to access items within the block. We expect these values to be on the order of 100 or 1000; we do not need to be more precise because the algorithms are not highly sensitive to these values.
This model is directly relevant, for example, in a file system in which files comprise blocks with unique identifiers and in which the purpose is to support efficient access, insertion, and deletion based on that identifier. A certain number of items fit on a block, and the cost of processing items within a block is insignificant compared to the cost of reading the block.
This model is also directly relevant in a virtual-memory system, where we simply refer directly to a huge amount of memory and rely on the system to keep the information that we use most often in fast storage (such as internal memory) and the information that we use infrequently in slow storage (such as a disk). Many computer systems have sophisticated paging mechanisms, which implement virtual memory by keeping recently used pages in a cache that can be accessed quickly. Paging systems are based on the same abstraction that we are considering: They divide the disk into blocks and assume that the cost of accessing a block for the first time far exceeds the cost of accessing data within the block.
Our abstract notion of a page typically will correspond precisely to a block in a file system or to a page in a virtual-memory system. For simplicity, we generally assume this correspondence when considering the algorithms. For specific apps, we might have multiple pages per block or multiple blocks per page for system- or app-dependent reasons; such details do not diminish the effectiveness of the algorithms and thus underscore the utility of working at an abstract level.
We manipulate pages, references to pages, and items with keys. For a huge database, the most important problem to consider now is to maintain an index to the data. That is, as discussed briefly in , we assume that the items constituting our symbol table are stored in some static form somewhere and that our task is to build a data structure with keys and references to items that allows us to produce quickly a reference to a given item. For example, a telephone company might have customer information stored in a huge static database, with several indexes on the database, perhaps using different keys, for monthly billing, daily transaction processing, periodic solicitation, and so forth. For huge data sets, indexes are of critical importance: We generally do not make copies of the basic data, not only because we may not be able to afford the extra space, but also because we want to avoid the problems associated with maintaining the integrity of the data when we have multiple copies.
Accordingly, we generally assume that each item is a reference to the actual data, which may be a page address or some more complex interface to a database. For simplicity, we do not keep copies of items in our data structures, but we may keep copies of keys—an approach that is often practical. Also, for simplicity in describing the algorithms, we do not use an abstract interface for item and page references—instead, we just use references to Item objects. Thus, we can use our implementations directly in a virtual-memory environment but have to convert the references and object accesses into more complex mechanisms to make them true external sorting methods.
We shall consider algorithms that, for a broad range of values of the two main parameters (block size and relative access time), implement search, insert, and other operations in a fully dynamic symbol table using only a few probes per operation. In the typical case where we perform huge numbers of operations, careful tuning might be effective. For example, if we can reduce the typical search cost from three probes to two probes, we might improve system performance by 50 percent! However, we will not consider such tuning here; its effectiveness is strongly system- and app-dependent.
On ancient machines, external storage devices were complex contraptions that not only were big and slow but also did not hold much information. Accordingly, it was important to work to overcome their limitations, and early coding lore is filled with tales of external file access programs that were timed perfectly to grab data off a rotating disk or drum and otherwise to minimize the amount of physical movement required to access data. Early lore is also filled with tales of spectacular failures of such attempts, where slight miscalculations made the process much slower than a naive implementation would have been. By contrast, modern storage devices not only are tiny and extremely fast but also hold huge amounts of information; so we generally do not need to address such problems. Indeed, in modern coding environments, we tend to shy away from dependencies on the properties of specific physical devices—it is generally more important that our programs be effective on a variety of machines (including those to be developed in the future) than that they achieve peak performance for a particular device.
For long-lived databases, there are numerous important implementation issues surrounding the general goals of maintaining the integrity of the data and providing flexible and reliable access. We do not address such issues here. For such apps, we may view the methods that we consider both as the underlying algorithms that will ultimately ensure good performance and as a starting point in the system design.