User:Ootz0rz/csc300 wiki article draft
In the field of Computer Science, a grid file is a multidimensional array, normally held on disk, and used as an index into a database of information. Consider a census database searchable by location. A data record represents a single household, and records are grouped into 'buckets', where all the records in a bucket relate to the same city, and to streets in that city whose names begin with the same letter. A grid file could be used to index this structure, where records came in 'groups' of 26, each of them relating to street names in a city, starting with one of the letters of the alphabet. Such an arrangement can be thought of as an array, table, or grid, with two dimensions. One might consider 'city' to be the y-axis, and 'first letter of street' to be the 'x-axis'. The records in such a structure are known as 'cells'. The cells will contain pointers to the appropriate bucket in the database where the data records are actually stored. An extra cell, or 'record header' will be necessary to store the city name, but the other cells grouped with it need only contain the pointer to their appropriate bucket, since the first cell is for streets beginning with 'B' the second with 'A' and so on. If our database has ambitions of world domination, we might add another field 'continent'. Records in the same bucket would now relate to house-holds on streets starting with the same letter, in the same city, and on the same continent. The cells in the grid file would now consist of the 'city' header, and five groups of twenty six cells relating to streets starting with A-Z on each of the continents (six if we have friends in Antarctica), and could be thought of as a 3 dimensional array. It might be objected that the same thing can be achieved with a one dimensional list of records, where the key is made by combining the city name and first letter of the street name. However, this is a grid file, the only difference being that the key is now held in each cell, and so space is wasted.
References
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.5: Searching, pp.564–566.
- Elmasri & Navathe Fundamentals of Database Systems, Third Edition. Addison-Wesley, 2000. ISBN 0-201-54263-3. Section 6.4.3: Grid Files, pp.185.