Portal de Periódicos da CAPES

The Buffer Tree: A New Technique for Optimal I/O Algorithms

1996; Volume: 3; Issue: 28 Linguagem: Inglês

10.7146/brics.v3i28.20009

1601-5355

Lars Arge,

Advanced Database Systems and Queries

In this paper we develop a technique for transforming an internal-memory tree data structure into an external-memory structure. We show how the technique can be used to develop a search tree like structure, a priority queue, a (one-dimensional) range tree and a segment tree, and give examples of how these structures can be used to develop efficient I/O algorithms. All our algorithms are either extremely simple or straightforward generalizations of known internal-memory algorithms - given the developed external data structures. We believe that algorithms relying on the developed structure will be of practical interest due to relatively small constants in the asymptotic bounds.