Efficient Methods for Database Storage and Retrieval Using Space-Filling Curves

Abstract

Efficient storage and retrieval of records involving multiple keys is a difficult and well-studied problem. A popular solution employed is to visualize the records as points in multidimensional space and use a mapping from this multidimensional space to the one-dimensional space of block addresses in secondary storage. There is significant interest in performing such a mapping using space-filling curves. Unfortunately, space-filling curves are defined for points that lie on a uniform grid of a particular resolution. As a result, both storage and retrieval algorithms based on space-filling curves depend upon the size of the grid. This makes the run time of such algorithms dependent on the distribution of the points and in fact, unbounded for arbitrary distributions. There are two main contributions in this paper: First, we present a distribution-independent algorithm for storing records with multiple keys using space-filling curves. Our algorithm runs in O(knlog n) time for storing n records containing k key fields. We then present an algorithm for answering range queries with a bounded running time independent of the distribution.