PLOP-Hashing: A Grid File without Directory

In this paper we consider the case of nonuniform weakly correlated or independent multidimensional record distributions. After demonstrating the advantages of multidimensional hashing schemes without directory, we suggest piecewise linear expansions in order to distribute the load more evenly over the pages of the file. The re-suiting piecewise linear order preserving hashing scheme (PLOP-Hashing) is then compared to the 2-level grid file which turned out to be the most popular scheme in practical applications. Let us consider a file of d-attribute composite keys K = (K1,..,Kd), d> 1. Our goal is to maintain a file efficiently supporting the following operations