Geospatial indexing

A bike-courier service in Berlin has 12,000 couriers, each phone reporting its position every 5 seconds. When a shop places an order, dispatch needs the available couriers within 1.5 km, closest first. The first attempt stores latitude and longitude in two columns and draws a box around the shop:

A B-tree on lat can find the right latitudes quickly, but that is a band 3 km tall running across the whole city. If the city is about 30 km wide and couriers are spread evenly, the band holds about 12,000 × 3 ÷ 30 = 1,200 couriers, all read and then filtered by longitude, to find the roughly 94 inside the circle (12,000 × π × 1.5² ÷ 900 km²). An index on (lat, lon) doesn't help: once the first column is a range, the second can't narrow the scan (Database indexing).

The box itself has a subtlety: 1.5 km is 0.0135° of latitude anywhere, but 0.0221° of longitude in Berlin, because degrees of longitude get shorter away from the equator (more on that below). The real fix is an index that understands two dimensions. Every approach in this page uses the same two steps:

• Filter with the index to a small set of candidates in cells near the point.
• Refine by computing the exact distance for each candidate and discarding the rest.

A geohash turns a point into a short string. It halves the world east-west and writes a bit (west 0, east 1), then halves it north-south and writes another, alternating, and encodes the bits in base 32. Each extra character narrows the cell; places that share a long prefix are close together, so an ordinary B-tree can find a cell's contents with a prefix search:

The reverse isn't true: two couriers on either side of a cell edge can be 10 meters apart with different prefixes. At the extreme, points on either side of the equator or the prime meridian share no prefix at all. So a radius search never looks in one cell. It takes the cell containing the shop plus its 8 neighbors, which Redis's geo commands do internally:

Geohash's weakness is its coarse steps: each character divides one side of a cell by 4 and the other by 8, a cell 32 times smaller, so a 1.5 km search must either use 4.9 km cells, a 3 × 3 block of about 14.7 km by 14.7 km, or use smaller cells and many more of them. Cells also get narrower east-west toward the poles. Redis stores each point as a 52-bit geohash score in a sorted set, so a geo search is a handful of range scans on an ordinary sorted structure.

Geohash is one way to number cells. A quadtree removes geohash's fixed cell sizes: split a region into four quadrants, and split again any quadrant that holds too many points. Busy Mitte at lunchtime gets small cells; the forest at the city edge stays one big cell. Two widely used global systems fix its other weaknesses:

• S2: projects the sphere onto the six faces of a cube and splits each face into four, repeatedly, down to level 30, where cells are under a square centimeter. Cells are numbered along a Hilbert curve, so nearby cell IDs are nearby cells. A circle can be covered with a small set of cells chosen to fit it, rather than a fixed 3 × 3 block.

• H3: covers the earth with hexagons at 16 resolutions. A hexagon's six neighbors are all the same distance from its center, while a square has two distances (edge and corner) and a triangle three. That makes "everything within k rings" a natural query, and is why it suits analysis of supply and demand by area.

Each system has its own quirk. S2 cells vary in area by about two to one at the same level (level 13 ranges from 0.76 to 1.59 km²). H3 needs exactly 12 pentagons at every resolution to close the sphere, and a hexagon can't be split exactly into seven smaller hexagons, so children only approximately fill their parent. For dispatch, both work; the choice usually follows what the rest of the stack already uses.

Points are only half the data. The courier service also has delivery zones (polygons), a low-emission zone that bikes can cross but cars can't, and shops with irregular footprints. The question "which zone contains this address?" needs an index of shapes. The usual answer is an R-tree: it groups shapes by their bounding boxes, nests the boxes in a tree, and searches the tree for boxes that overlap the query.

PostGIS, the geographic extension for PostgreSQL, builds R-trees on PostgreSQL's GiST indexes, and spatial functions such as ST_DWithin and ST_Intersects use them automatically. The same filter-and-refine pattern applies: the index finds shapes whose boxes overlap, then an exact geometric test removes the false matches:

With the geography type, distances are in meters, measured on the earth's ellipsoid by default. R-trees are the right tool for shapes and for data that changes moderately. Positions that change every few seconds are a different workload, covered in the last section.

Treating latitude and longitude as flat x and y is a common geo bug. A degree of latitude is always about 111 km. A degree of longitude is about 111.32 km × cos(latitude): it shrinks toward the poles.

For exact distances, use the haversine formula, the great-circle distance on a sphere. Treating the earth as a sphere can be off by up to about 0.5%, which is fine for "couriers within 1.5 km" and not for surveying, where ellipsoid formulas are used. Three edge cases catch real systems:

• The antimeridian at 180°: a box around Fiji spans longitudes 179° and −179°, and a naive BETWEEN returns nothing.
• The poles, where longitude stops meaning much. Redis, for example, rejects latitudes beyond ±85.05°.
• Coordinate order: many systems take longitude first (x, y), many people write latitude first.

Couriers move. 12,000 couriers reporting every 5 seconds is 12,000 ÷ 5 = 2,400 location updates a second, each one possibly moving a courier to another cell. A disk-based spatial index can absorb that, but the usual design keeps two copies:

• Live positions in an in-memory geo index, such as a Redis sorted set per city (each update costs O(log N)), queried for dispatch and overwritten constantly.
• History appended to a durable store for billing, analytics and disputes, where it is never queried by distance in real time.

Nearest-N, the real dispatch question, is a loop rather than a single radius: search a small area, and if fewer than 10 available couriers come back, widen the search ring by ring. At 3 a.m. the ring grows; at lunchtime downtown the first ring is enough.

Scaling out follows the cells. Sharding by city works until one city dominates; then shard by a coarse cell ID (an S2 or H3 cell, for example), which keeps nearby couriers on the same shard. Density is wildly uneven: the cell around the main station at lunchtime can hold a hundred times the couriers of a suburb, so fixed cells create hot shards (Hot partitions & skew). Split hot cells into their children and merge quiet ones, the same adaptive idea as a quadtree, applied to the shards.