The Grid File
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik · ACM Transactions on Database Systems · 1984
Traditional file structures that provide multikey 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 multikey access to highly dynamic files. We study the dynamic aspects of file structures that treat all keys symmetrically, that is, file structures which avoid the distinction between primary 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 notions of a grid partition of the search space and of a grid directory , which are the keys to a dynamic file structure called the grid file . This file system adapts gracefully to its contents under insertions and deletions, and thus achieves an upper bound of two disk accesses for single record retrieval; it also handles range queries and partially specified queries efficiently. We discuss in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.
Cited by 1,144 works. doi:10.1145/348.318586 Open-access PDF
Authors
References
- The Art of Computer Programming
- Multidimensional binary search trees used for associative searching
- Quad trees a data structure for retrieval on composite keys
- The K-D-B-tree
- Extendible hashing—a fast access method for dynamic files
- Multidimensional Binary Search Trees in Database Applications
- Partial-Match Retrieval Algorithms
- Attribute based file organization in a paged memory environment
- The Grid file: A data structure designed to support proximity queries on spatial objects
- Multi-attribute retrieval with combined indexes