Lecture Notes in Computer Science, 1988, Volume 294/1988, 38-51, DOI: 10.1007/BFb0035830

Maintaining range trees in secondary memory
extended abstract

Mark H. Overmars and Michiel H. M. Smid

View Related Documents

Abstract

Range trees can be used for solving a number of problems in databases and other applications. We study the problem of storing range trees in secondary memory. To this end, we have to partition range trees into parts that can be stored in consecutive blocks in secondary memory. A number of partition schemes will be presented that limit the part sizes and the number of disk accesses necessary for performing updates and queries. Matching lower bounds will be proven as well.

Fulltext Preview

Image of the first page of the fulltext document