Gridfile

from Wikipedia, the free encyclopedia

A Gridfile (engl. = Grid grating) is an at least two-dimensional index structure , the searching for data having 2 or more criteria greatly accelerated. With traditional one-dimensional data structures (e.g. hash table ), searching for one criterion is usually very simple, while searching for a second criterion is very time-consuming . Grid files represent a special type of hashing in which the classic 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 one of the symmetrical data structures , since none of the key values ​​is preferred, but all keys are always entered equally.

In the grid file, for example, when searching for three criteria, like a three-dimensional cube, the relevant data record can be found directly. In most cases, the data is not stored in the grid file itself (which would take up too much space if the cube is only moderately full), but only a reference to the bucket in which the desired data is stored. A bucket stores several data records that are next to each other in the grid file .

The so-called two-disk-access principle applies to a grid file. This means that a requested data record is available after no more than two requests to a secondary memory. To ensure this, the index structure and the actual data are stored in two separate data structures. Since the index structure is relatively small compared to the data to be addressed, it can ideally also be kept in the main memory.

The buckets are addressed by using so-called scales, which form the index structure. A scale is created for each dimension k, which sorts the boundaries of the buckets in the corresponding dimension and contains an index for this dimension. By combining the entries in the individual scales, the corresponding bucket can be determined which contains the data for the coordinates sought.

A grid file is insensitive to data clusters, as it reacts to the properties of the content as an adaptive data structure through splitting or dimension refinement (in the case of a bucket overflow) and merging (in the case of a bucket underflow).

See also

Database index , quadtree , Kd tree , UB tree , R tree , area tree as alternatives

Web links