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.
buffer tree batched external data structures i/o efficiency internal memory algorithms