Gridfile

A Grid File (English Grid = Grid ) is a least two-dimensional index structure that significantly accelerates the search for data with two or more criteria. In traditional one-dimensional data structures (eg, hash table ) a search for a criterion is usually very simple, the search for a second criterion very time consuming. Grid files are a special kind of hashing, in which the classical hash function is replaced by a grid directory.

General grid files have the dimension k, which means that they store k-dimensional data with the keys S1 ... Sk. Grid files are among the symmetric data structures, since none of the key values ​​is preferred, but always received all the keys equally.

In Gridfile the affected data set can be found for example in the search for three criteria as in a three-dimensional cube directly. The grid file itself not the data are usually stored (which would take at a moderately filled cube to much space ), but only a reference to what bucket the desired data is stored. A bucket stores multiple adjacent in the grid file records.

In a grid file that applies so-called two- disk -access principle. This means that a wanted record after two inquiries present on a secondary storage. The index structure, and the actual data is to ensure this stored in two separate data structures. Since the index structure is relatively small in comparison to the data to be addressed, it can be maintained in the optimum case in the main memory.

The addressing of the bucket is done by the use of this so-called scale, which make up the index tree. For each dimension, a scale k is created, which define sorted in the corresponding dimension, and the boundaries of the buckets contain an index for this dimension. The corresponding bucket, by the combination of the entries in the various scales thus be determined which contains the data for the coordinates of this.

A grid file is insensitive to data clustering, since it reacts as an adaptive data structure by splitting or dimensional refinement ( at Bucketüberlauf ) and fusion ( at Bucketunterlauf ) on the properties of the content.