Spatial indexes (R-tree, GiST, SP-GiST)

A B-tree needs one sort order, which maps, shapes and time ranges don’t have. Antonin Guttman’s R-tree (1984) is a height-balanced tree like a B-tree in which each entry holds the smallest rectangle containing its object or child node, so a search only descends into nodes whose rectangles overlap the query. PostGIS indexes geometries the same way: the index stores bounding boxes, and each candidate it returns is then tested against the exact shape.

PostgreSQL generalises this as GiST (generalized search tree), a balanced tree framework from Hellerstein, Naughton and Pfeffer’s 1995 paper, in which an operator class defines what the keys are; PostgreSQL 8.2 replaced its separate R-tree with one built on GiST. GiST can return nearest neighbours in distance order (ORDER BY location <-> point '(101,456)' LIMIT 10, since 9.1) and backs exclusion constraints such as EXCLUDE USING gist (c WITH &&), which reject overlapping rows.

SP-GiST (space-partitioned GiST, PostgreSQL 9.2) hosts unbalanced structures that keep dividing the space, such as quad-trees, k-d trees and radix trees (tries), and maps their nodes onto disk pages so a search reads few pages. SQLite offers an R*Tree module for the same kind of range query.