The Buffer Tree: A Technique for Designing Batched External Data Structures

摘要

We present a technique for designing external memory data structures that support batched operations I/O efficiently. We show how the technique can be used to develop external versions of a search tree, a priority queue, and a segment tree, and give examples of how these structures can be used to develop I/O-efficient algorithms. The developed algorithms are either extremely simple or straightforward generalizations of known internal memory algorithms―given the developed external data structures.