Maintaining range trees in secondary memory. Part I: partitions

Range trees are used for solving the orthogonal range searching problem, a problem that has applications in e.g. databases and computer graphics. We study the problem of storing range trees in secondary memory. To this end, we partition range trees into parts that are stored in consecutive blocks in secondary memory. This paper gives a number of partition schemes that limit the part-sizes and the number of disk accesses necessary to perform updates and queries. We show e.g., that for each fixed positive integer k, there is a partition of a two-dimensional range tree into parts of size O(n 1/k ), such that each update requires at most k(2k+1) disk accesses, and each query requires at most 8k 2+2k+2t disk accesses, where t is the number of answers to the range query