A partitioning method for grid file directories

The grid file can be used for the implementation of a database to handle range queries and partially specified queries. Although an upper bound of two disc accesses for a single record retrieval is guaranteed, the number of directory entries is an exponential function of the number of data buckets if the data distribution is heavily non uniform. A new method is presented for partitioning the search space for constructing a grid directory. It improves the ratio of the number of directory entries to the number of data buckets. The directory expansion appears to have a quadratic or cubic rate when the data distribution is non uniform. An implementation of the method is presented. Simulation results are given for both the traditional grid file partitioning method and the new method