Skip to content

Geospatial indexing

A way to turn a location on the sphere into a cell id that an ordinary sorted index can range-scan, so "what is near this point" becomes a few lookups instead of a scan of all rows.

On this page

What it is

A geospatial index makes location searchable by a store that sorts on one key. Latitude and longitude are two numbers, and a search such as "drivers within two kilometers" constrains both at once, which a single sorted index handles badly. The common fix is to split the surface of the Earth into a hierarchy of cells, give each cell an id, and store that id with each point. A point becomes the smallest cell that holds it; a region, such as a search circle, becomes a set of cells at whatever levels fit it. S2, for instance, describes its cell hierarchy as useful for indexing and for approximating regions, with points held as leaf cells and regions as collections of cells.

S2 shows the idea most clearly. It projects a cube's six faces onto the sphere and splits each cell into four children, again and again, through levels 0 to 30; a level-30 leaf cell is about 1 cm across. Each cell gets a 64-bit id built from the face and the sequence of child choices, so the level can be read off the id itself. The ids follow a Hilbert space-filling curve across the whole sphere, which gives the property that two ids close in value belong to cells close on the ground. A cell's descendants occupy one inclusive id range, from its lowest to its highest leaf id, so "all points inside this cell" is a range scan on a sorted index of cell ids.

Geohash does the same with characters instead of bits: it encodes a location as a string that defines a hierarchical square grid, in effect a quadtree, so a longer string names a smaller square inside the shorter one's square. H3 uses hexagons rather than squares. Its hierarchy is logically exact but geometrically approximate: a child hexagon is not fully inside its parent, so points inside sibling children can map to different parents. H3 was built around Uber's data science needs, such as joining disparate data sets, and offers functions to find the cell for a coordinate, a cell's center, its boundary and its neighbors.

The edge problem. A point a few meters across a cell border sits in a different cell, and with a space-filling curve that neighbor's id can be far away in the ordering. The property runs one way: close ids mean close cells, but close cells need not have close ids. So a nearby search is two steps. First, cover the query region with a set of cells, the way S2 approximates Hawaii with 22 cells, and run one range scan per cell. Second, compute the true distance to each candidate and drop the ones outside the radius. The covering is a superset of the answer; the distance filter makes it exact.

ProductWhat it gives youWhat to remember

Redis, GEOSEARCH

Queries a geospatial index for the members inside a circle or a box

Our pick for a live set of moving points, such as drivers, when the store is Redis anyway

MongoDB 2dsphere (manual covering 8.2)

Queries that treat geometry as lying on a sphere, using the WGS84 reference system for GeoJSON

Store GeoJSON with longitude first, then latitude

MongoDB 2d (same manual)

Queries on a flat surface for legacy coordinate pairs

Spherical queries on a 2d index can return wrong results or an error; queries that wrap the poles are not supported

When to use it

Reach for a geospatial index when the design has a "near me" query over a set too large to scan: restaurants around a user, drivers around a rider, listings inside the visible map. In MongoDB, $near and $nearSphere require a geospatial index, which is a hint that proximity queries are the case these indexes exist for.

Use the cell id for more than the index. A coarse cell id works as a partition key when the partitioner keeps whole cells together, by range or by an explicit cell-to-shard map rather than a hash of fine cells: points in one area then tend to share a shard, and a nearby search touches fewer shards (see Sharding and partition keys). The cost is uneven density: a cell over a downtown holds far more points than one over the ocean, which is the hot-partition problem in a new form. A hierarchy helps here: because S2 ids encode the level and each descendant falls in the parent's id range, you can store points at a fine level and still answer coarse queries with one range scan per coarse cell.

Pick hexagons when the goal is analysis by area rather than point lookup: H3 came out of Uber's data science needs, and its documentation points to joining disparate data sets and modeling flow between neighboring cells.

When not to

Skip it when the set is small enough to scan. A plain index on latitude, a bounding-box filter on both coordinates and a distance check in code answers in one query and adds no new component; measure that path before adding a spatial index. The same goes for a fixed set of regions: if the question is "which store serves this zip code", store the region id on the row and the spatial problem disappears.

Don't build your own grid when the store already has a spatial index. MongoDB's own query operators work against its 2dsphere and 2d indexes, and Redis answers a circle or box search with one command. Hand-rolled geohash prefixes are worth it when the store has no spatial support, or when you need the cell id as a partition key as well.

Don't use a flat index for data that spans the globe. MongoDB warns that spherical queries against its flat 2d index can return incorrect results, with queries that wrap the poles as the example. Pick the spherical index unless the data sits in one small area where a flat approximation holds.

Compared

ApproachHow it maps 2D to 1DStrong atWhen the other option is right

Geohash

A string over a hierarchical square grid, a quadtree; longer prefix, smaller square

Readable ids; prefix search in a store that keeps keys in order

Pick S2 when you need to cover an odd-shaped region with cells of mixed levels and scan each as an id range

S2 cells

64-bit ids along a Hilbert curve over six cube faces, levels 0 to 30

Range scans per cell; coverings of arbitrary regions

Heavier library; a geohash string is enough for a simple nearby list

H3 cells

Hexagons in a hierarchy where children are not fully inside their parent

Joining data sets by cell; modeling flow between neighbors

Containment is approximate, so pick a quadtree (geohash, S2) when a child must sit inside its parent exactly

Database spatial index (MongoDB 2dsphere)

Built into the store; you write a query, not a grid

Spherical geometry, intersects and within, no code of your own

You need the cell id as a partition key or for cross-store joins

Two plain indexes on lat and lon

None; filter both columns, then compute distance

Small tables, no new component

A set too large to scan per query, or proximity queries hot enough that the scan shows up in latency

In a picture

Query + radiusCover with cellsScan each cellCell id indexCandidatesDistance filterSorted results
A nearby search covers the circle with cells, range-scans each, then filters the superset by true distance.

How to say it in an interview

The common mistake

Quiz

A nearby search computes the geohash of the user and returns each point sharing that prefix. What is wrong?
Why can an S2 index answer "all points in this cell" with one range scan?
You roll points up from fine H3 cells to their parent cells for a heat map. What should you expect?
A city has 400 clinics and a page lists the nearest five. Which design fits?

Questions that use this

Related

Sources

  1. S2 Geometry developer guide: S2 Cells
  2. H3 documentation (4.x): Introduction
  3. MongoDB Database Manual: Geospatial Queries
  4. Redis documentation: GEOSEARCH
Sign in to report a mistake