Our notation is summarized in Fig. 1. The parameters M, w and B describe

This chapter is a tutorial on basic data structures that perform well in mem-ory hierarchies. These data structures have a large number of applications and furthermore serve as an introduction to the basic principles of designing data structures for memory hierarchies. We will assume the reader to have a background in computer science that includes a course in basic (internal memory) algorithms and data structures. In particular, we assume that the reader knows about queues, stacks, and linked lists, and is familiar with the basics of hashing, balanced search trees, and priority queues. Knowledge of amortized and expected case analysis will also be assumed. For readers with no such background we refer to one of the many textbooks covering basic data structures in internal memory, e.g., [CLRS01]. The model we use is a simple one that focuses on just two levels of the memory hierarchy, assuming the movement of data between these levels to be the main performance bottleneck. (More precise models and a model that considers all memory levels at the same time are discussed in Chapter?? and Chapter??.) Speci cally, we consider the external memory model described in Chapter??