Spatial index

On this page 7

A spatial index is a database access structure that organizes geometric or geographic objects by their position in space, so that queries about location, overlap and distance can skip most of the stored data. In the indexing toolbox of Databases, it plays the role that a B-tree index plays for ordered scalar values, but for points, lines, polygons and other multidimensional shapes that have no single natural sort order.

Most spatial indexes work on bounding boxes rather than exact shapes. The index quickly finds a small set of candidate objects whose boxes intersect the search area, and the database then runs an exact geometric test on that short list. This two-step filter and refine strategy is the core idea behind every major implementation, from R-trees in PostGIS to grid-based indexes in SQL Server.

A spatial index answers location questions by grouping nearby objects into nested regions and storing each region with a compact summary of its extent. Because ordinary one-dimensional ordering cannot preserve proximity in two or more dimensions, the index must partition space itself or partition the set of objects in a way that keeps neighbors physically close on disk.

The query then proceeds in two phases. In the primary filter, the engine walks the index and keeps only entries whose minimum bounding rectangle (MBR) intersects the query window. In the secondary filter, it loads the full geometry of each candidate and evaluates the precise predicate, such as containment or intersection. The primary filter is cheap but approximate; the secondary filter is exact but expensive, so index quality is measured by how few false candidates reach the second phase.

The following table summarizes the stages of a typical spatial query and what each stage costs.

StageWork performedTypical cost
Index traversalDescend nodes whose boxes overlap the queryLogarithmic in table size
Candidate collectionGather row identifiers from matching leavesProportional to overlap
Exact refinementRun geometric predicate on full shapesHigh per row, depends on vertex count
Result assemblyReturn rows that pass the exact testLow
Stages of a spatial query using an index

Main types of spatial index structures

Spatial indexes fall into two broad families: data-driven trees that adapt to where objects actually are, and space-driven partitions that divide the coordinate plane into fixed cells regardless of the data. Each family makes different trade-offs between update cost, query speed and sensitivity to skewed data.

The R-tree and its variants (R*-tree, Hilbert R-tree) group objects into overlapping rectangles and are the default in PostGIS through the GiST framework, in Oracle Spatial and in SQLite with the R*Tree module. Quadtrees and k-d trees recursively split space into quadrants or half-planes. Grid and space-filling curve indexes, such as those based on the Z-order or Hilbert curve, map two-dimensional cells onto a one-dimensional key that a standard B-tree can store. Modern geospatial libraries also use hierarchical cell systems such as S2 and H3 for planet-scale data.

The table compares the most common structures and the conditions in which each performs best.

StructurePartitioning approachBest suited forMain weakness
R-treeOverlapping bounding rectanglesMixed shapes, general queriesNode overlap slows searches
QuadtreeRecursive four-way space splitPoints, uneven densityDeep trees on clustered data
k-d treeAlternating axis splitsIn-memory point setsPoor fit for frequent updates
Grid indexFixed multilevel cellsPredictable extentsCell size tuning required
Space-filling curveCells mapped to linear keysReuse of B-tree storageProximity breaks at curve jumps
Common spatial index structures compared

Spatial index compared with other index types

A spatial index differs from a B-tree index because a B-tree relies on a total order of keys, which cannot represent two-dimensional closeness without distortion. It also differs from a hash index, which supports only equality lookups and destroys locality entirely. In PostgreSQL, spatial indexes are usually built on GiST, while a GIN index serves composite values such as arrays and documents rather than geometric extents.

The comparison below shows which predicates each index type can accelerate.

Index typeEqualityRange on one columnOverlap or containmentNearest neighbor
Spatial indexLimitedNot applicableYesYes, with ordered traversal
B-tree indexYesYesNoNo
Hash indexYesNoNoNo
GIN indexElement membershipNoSet overlap onlyNo
Supported query patterns by index type

The query planner decides whether to use a spatial index based on estimated selectivity. A query whose search window covers most of the dataset gains little from the index, and the planner may correctly choose a sequential scan instead, just as it would for a low-selectivity predicate on any other index.

Designing and tuning a spatial index

Effective spatial indexing starts with storing geometries in a consistent coordinate reference system and writing predicates that the engine can map to the index. Functions such as ST_Intersects, ST_DWithin and ST_Contains in PostGIS are index-aware, whereas wrapping the column in a transformation such as ST_Transform(geom, 3857) usually prevents index use unless a matching expression index exists.

Several practical settings influence performance. Large, complex polygons produce oversized bounding boxes, so subdividing big geometries into smaller pieces often reduces false candidates dramatically. Physically clustering the table on the spatial index improves cache locality for area queries. For nearest-neighbor searches, the distance operator <-> lets PostgreSQL return results in index order without sorting the whole table.

The decision table lists common situations and a suitable indexing choice for each.

SituationRecommended approachReason
Store locations with radius searchesR-tree via GiST on pointsFast distance filtering
Very large country or coastline polygonsSubdivide, then index piecesTighter bounding boxes
Read-heavy static datasetBulk-load and cluster the tableBetter packing and locality
Global data at many resolutionsHierarchical cell keysUniform cells across scales
Frequent small insertsR*-tree or GiST with periodic reindexControls node overlap growth
Choosing a spatial indexing strategy

Limitations and common mistakes

Spatial indexes carry real maintenance costs and failure modes that practitioners must anticipate. They are larger than comparable B-tree indexes, slower to build, and their effectiveness degrades as overlapping inserts accumulate.

  • Bounding box approximation means long diagonal lines and L-shaped polygons generate many false candidates.
  • Mixed coordinate systems in one column make distances meaningless and can silently defeat the index.
  • Measuring distance in degrees on geographic data gives distorted results away from the equator; use a geography type or a projected system.
  • Function-wrapped predicates in the WHERE clause often force a sequential scan.
  • Stale statistics lead the planner to misjudge selectivity, so routine analysis matters as much as for any index.
  • Higher dimensions reduce effectiveness, because bounding boxes overlap more as dimensions are added.

The simple explanation

Imagine a city map divided into neighborhoods, then streets, then individual blocks. If someone asks which cafes lie within two blocks of a station, nobody reads the address of every cafe in the city. They look at the right neighborhood first, then the right streets, and only then check exact distances.

A spatial index gives a database that same habit. It keeps a map-like summary of where everything is, so a location question touches only a small corner of the data. The key takeaway is that it turns a slow search through millions of shapes into a quick look at a handful of nearby ones.

How it is used in practice

A regional food delivery service stores about 4 million customer addresses and 12,000 restaurant locations as points in a PostgreSQL database with PostGIS. When a customer opens the app, the system must list every restaurant that delivers within 5 kilometers, sorted by distance, in well under a second.

Without an index, each request compared the customer location with all restaurants and took roughly 300 milliseconds under load. The engineering team created a GiST spatial index on the restaurant geometry column, rewrote the filter with ST_DWithin on a geography type, and used the <-> operator for ordering. The query time dropped to a few milliseconds, and the database handled several times more concurrent users on the same hardware, because each search now inspected only a few dozen candidate restaurants instead of the entire table.