Searching Quadtrees

To search a linear quadtree index, in order to find stored data inside a search window, the window itself may be described in the form of a list of quadtree cells that cover it. It is not necessary for this search list to correspond exactly with the window, provided it covers it entirely. Once stored data cells are found that overlap the search cells, precise comparison can be performed with an exact (vector format) geometric definition of the search window.

Excursus: Grid files

In a grid file the space, of whatever dimension, is divided in a slightly less regular manner, but like a quadtree, adapts to the spatial variation in data density. The cells of a 2D grid are referenced by a 2D grid array, the elements of which store the address of other data records (called buckets) storing the geometry that is inside or intersects the cell. The geographical dimensions of the grid (in 2D) are defined by a set of vertical and horizontal partition lines. The relationship between real-world grid coordinates of the cells and the grid array elements is maintained by 1D arrays called linear scales. The coordinate values of the x-direction grid lines are stored in one 1D array while those of y-direction are stored in another.
A characteristic of the grid file is that a bucket is assumed to be able to store several items of data (actual geometric data, or references to the storage of relevant geometric data) and that several directory cells may reference the same bucket (Nievergelt 1984).