The interpolation-based grid file
Mohamed Ouksel · 1985
A new organization for on-line maintenance of large external f&s is developed.This method is inspired from the ideas incorporated in two recently proposed structures: the interpolation-based index maintenance and the grid file , from which it inherits all the benefits.Like these previous schemes, the new one is also based on the partitioning of the whole search space and is well-suited for dynamic databases since it handles insertion, update, delete, and range queries efficiently.However, unlike the interpolation-based index maintenance, it does not utilize overflow buckets; but, it takes advantage of the direct addressing mechanism.Like the grid Ale, it obeys the principle of two disk-accesses: one to the directory and one to the data file, except that now the directory remains always a linear function of the number of data pages.