The grid file: An adaptable, symmetric multi-key file structure

This work starts from a bitmap approach and treats the problem of file design as one of data compression of a large sparse matrix, which leads to the notion of a grid directory, which is the key to a dynamic file structure called the grid file.

Abstract

Traditional file structures that provide multi-key access to records, for example inverted files, are extensions of file structures originally designed for single-key access. They manifest various deficiencies, in particular for multi-key access to highly dynamic files. We study the dynamic aspects of file structures that treat all keys symmetrically, that is, avoid the distinction between primary key and secondary keys. We start from a bitmap approach and treat the problem of file design as one of data compression of a large sparse matrix. This leads to the notion of a grid directory, which is the key to a dynamic file structure called the grid file. The file system described adapts gracefully to its contents under insertions and deletions (remains balanced). It achieves an upper bound of two disk accesses on the average. First results of a simulation of the behavior of one implementation of the grid file are presented.