computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

, a grid file or bucket grid is a

point access method A spatial database is a general-purpose database (usually a relational database) that has been enhanced to include spatial data that represents objects defined in a geometric space, along with tools for querying and analyzing such data. Most sp ...

which splits a space into a non-periodic

grid Grid, The Grid, or GRID may refer to: Common usage * Cattle grid or stock grid, a type of obstacle is used to prevent livestock from crossing the road * Grid reference, used to define a location on a map Arts, entertainment, and media * News g ...

where one or more cells of the grid refer to a small set of points. Grid files (a

symmetric Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...

data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...

) provide an efficient method of storing these indexes on disk to perform complex data lookups. It provides a grid of ''n''-dimensions where ''n'' represents how many keys can be used to reference a single point. Grid files do not contain any data themselves but instead contain references to the correct

bucket A bucket is typically a watertight, vertical Cylinder (geometry), cylinder or Truncation (geometry), truncated Cone (geometry), cone or square, with an open top and a flat bottom, attached to a semicircular carrying handle (grip), handle called ...

Uses

A grid file is usually used in cases where a single value can be referenced by multiple keys. A grid file began being used because "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."J. Nievergelt, H. Hinterberger ''The Grid File: An Adaptable, Symmetric Multikey File Structure''. Institut fur Informatik, ETH and K. C. Sevcik, 1984. Abstract, pp.1. In a traditional single dimensional data structure (e.g. hash), a search on a single criterion is usually very simple but searching for a second criterion can be much more complex. Grid files represent a special kind of hashing, where the traditional hash is replaced by a grid directory.

Examples

Census DatabaseElmasri & Navathe ''Fundamentals of Database Systems'', Third Edition. Addison-Wesley, 2000. . Section 6.4.3: Grid Files, pp.185.

Consider a database containing data from a census. A single record represents a single household, and all records are grouped into buckets. All records in a bucket can be indexed by either their city (which is the same for all records in the bucket), and the streets in that city whose names begin with the same letter. A grid file can be used to provide an efficient index for this structure, where records come in groupings of 26, each of them relating to street names in a city starting with one of the letters of the alphabet. This structure can be thought of as an

array An array is a systematic arrangement of similar objects, usually in rows and columns. Things called an array include: {{TOC right Music * In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...

table Table may refer to: * Table (furniture), a piece of furniture with a flat surface and one or more legs * Table (landform), a flat area of land * Table (information), a data arrangement with rows and columns * Table (database), how the table data ...

, or

with two dimensions which we will call the x and y axes. One may consider the x-axis to be the city and the y-axis to be each of the letters in the alphabet, or alternatively, the first letter of each street. Each record in this structure is known as a cell. Each cell will contain a pointer to the appropriate bucket in the database where the actual data is stored. An extra cell, or record header, may be required to store the name of the city. Other cells grouped with it will only need to contain the pointer to their respective bucket, since the first cell corresponds to street names beginning with "A", the second to "B", and so on. The database can be further extended to contain a continent field to expand the census to other continents. This would cause records in the same bucket to correspond to households on a street beginning with the same letter, in the same city, in the same continent. The cells in the grid file would then consist of a city header, and six (one for each continent, not including

Antarctica Antarctica () is Earth's southernmost and least-populated continent. Situated almost entirely south of the Antarctic Circle and surrounded by the Southern Ocean, it contains the geographic South Pole. Antarctica is the fifth-largest contine ...

) groupings of 26 cells relating to the streets with the same starting letter, in the same city, on the same continent and could now be thought of as a three-dimensional array.

Advantages

Since a single entry in the grid file contains pointers to all records indexed by the specified keys: * No special computations are required * Only the right records are retrieved * Can also be used for single search key queries * Easy to extend to queries on ''n'' search keys * Significant improvement in processing time for multiple-key queries * Has a two-disk-access upper bound for accessing data.

Disadvantages

However, because of the nature of the grid file, which gives it its advantages, there are also some disadvantages: * Imposes space overhead * Performance overhead on insertion and deletion

Related Data Structures

multilayer grid file In the physical sciences, a multilayer or stratified medium is a stack of different thin films. Typically, a multilayer is man made for a specific purpose. Since layers are thin with respect to some relevant length scale, interface effects are mu ...

twin grid files Twins are two offspring produced by the same pregnancy.MedicineNet > Definition of TwinLast Editorial Review: 19 June 2000 Twins can be either ''monozygotic'' ('identical'), meaning that they develop from one zygote, which splits and forms two em ...

BANG file A BANG file balanced and nested grid file) is a point access method which divides space into a nonperiodic grid. Each spatial dimension is divided by a linear hash. Cells may intersect, and points may be distributed between them. Another meaning ...

References

{{reflist Computer files Arrays