What Is a Spatial Index?

A spatial index speeds up retrieval of spatial data.

In database design, an index is a data structure that takes the value of one or more columns, or fields, as input and returns the corresponding records quickly. A spatial index is an index on a column containing spatial data or, in other words, data representing the length, area and volume of lines, surfaces and other objects. Spatial data is often used in computer-aided design, map making and geographic information systems.

Purpose

Spatial datasets are typically large and irregularly distributed. If a query is performed on a spatial dataset without spatial indexes, every record in the dataset needs to be examined to determine if it matches the search criteria. This type of scan, known as a full table scan or sequential scan, is the slowest method of scanning and is typically impractical for most applications. Spatial indexes, on the other hand, allow spatial data to be retrieved without examining each record and minimize the time a query takes to return results.

Grid

Spatial indexes allow users to treat three-dimensional data within a database as if it exists in two dimensions. A grid index consists of a specific area, which is divided in a series of contiguous, or adjacent, cells. The cells can be triangular, square, rectangular or hexagonal, but all of them have the same width and height. Each cell is uniquely identified by its horizontal and vertical coordinates, so that it can be used as a spatial index.

R-Tree

The most common structure for indexing spatial data is known as an R-tree. Geometric shapes, lines and points are arranged into a logical tree structure in which each leaf node corresponds to a row in the database table. Each leaf node stores what is known as a minimum bounding rectangle, to which objects are added with an index to minimize the distance between them.

Quadtree

A quadtree is a hierarchical data structure that is typically used to divide two-dimensional space into smaller parts, otherwise known as recursive decomposition of space. The two-dimensional space can be divided in equal parts, such as regular squares or rectangles, or unequal parts, depending on the incoming data. Similarly, the number of times the space is divided can be determined in advance or by the properties of the incoming data. Several types of quadtree exist and are classified by the type of data -- points, lines, surfaces -- they represent and the dependence or independence of the shape of the tree on the order in which the data is processed.

References

• MSDN: Spatial Indexing Overview
• GDMC: Spatial Access Methods
• Informatica Economica: Optimizing Spatial Databases