One of the defining characteristics of a spatial database is the ability to create and use "spatial" indexes to speed up geometry-based searches. These indexes are used to perform spatial operations, such as identifying all the features that lie within a given bounding box, identifying all the features within a certain distance of a given point, or identifying all the features that intersect with a given polygon.

Spatial indexes are one of the most powerful features of spatial databases, and it is worth spending a moment becoming familiar with how they work. Spatial indexes don't store the geometry directly; instead, they calculate the bounding box for each geometry and then index the geometries based on their bounding boxes. This allows the database to quickly search through the geometries based on their position in space:

The bounding boxes are grouped into a nested hierarchy based on how close together they are, as shown in the following illustration:

The hierarchy of nested bounding boxes is then represented using a tree-like data structure, as follows:

The computer can quickly scan through this tree to find a particular geometry or compare the positions or sizes of the various geometries. For example, the geometry containing the point represented by the X in the preceding diagram can be quickly found by traversing the tree and comparing the bounding boxes at each level. The spatial index will be searched in the following manner:

Using the spatial index, it only took three comparisons to find the desired polygon.

Because of their hierarchical nature, spatial indexes scale extremely well and can search through many tens of thousands of features using only a handful of bounding-box comparisons. And, because every geometry is reduced to a simple bounding box, spatial indexes can support any type of geometry, not just polygons.

Spatial indexes are not limited to only searching for enclosed coordinates; they can be used for all sorts of spatial comparisons and for spatial joins. We will be working with spatial indexes extensively throughout this book.