Geospatial indexes: geohash, quadtrees, S2 and H3

A geospatial index answers “what is near this point?” without scanning every row. Every practical scheme uses the same trick: cut the map into cells, number the cells so that nearby places get nearby numbers, and turn a two-dimensional search into a few one-dimensional lookups plus an exact distance check. Geohash, quadtrees, R-trees, S2 and H3 differ in how they cut the map and number the pieces.

Picture it first: PIN codes

An Indian PIN code is a six-digit address for a patch of land. The first digit names a postal zone, the first three a sorting district, and all six a delivery post office. Three of its habits matter here:

• Prefixes nest. Every post office sits inside one district, inside one zone, so you sort mail by reading more digits.
• Borders cut through streets. Two houses facing each other across a district boundary can have different prefixes, and a clerk who checks only one district misses the house across the road.
• Busy areas get finer codes. A state gets more sorting districts when it handles more mail, and an overloaded post office is split and given a new PIN.

Map it back: the PIN is a cell ID, shared prefixes are the cell hierarchy, the clerk’s blind spot is the boundary problem, and splitting busy offices is how a quadtree adapts to density.

Why latitude and longitude B-trees fail

Take 10 million restaurants and the query “within 2 km of me”. The obvious design indexes lat and lng and asks for both ranges:

SELECT id, name FROM restaurants
WHERE lat BETWEEN 12.910 AND 12.946      -- about ±2 km of latitude
  AND lng BETWEEN 77.592 AND 77.629;     -- about ±2 km of longitude

A B-tree sorts on one value, so each index hands back a strip: every restaurant in a 4 km band of latitude across the whole map, or in a 4 km band of longitude down the whole map. You want the small square where the strips cross.

Spread the restaurants evenly over a country 3,000 km on a side. Each strip holds 10M × 4 / 3,000 ≈ 13,300 rows; the square holds 13,300 × 4 / 3,000 ≈ 18. The database touches about 26,600 index entries to return 18 rows, roughly 1,500× more work than the answer. A composite index on (lat, lng) doesn’t help: once the first column is a range, the second is only a filter, so you still walk the whole latitude strip.

The trick: give space a one-dimensional address

Every geospatial index divides the map into cells and numbers them so that cells close in space get close IDs. A proximity query then runs in three steps:

1. Cover: find the few cells that together contain the search circle.
2. Fetch: look up each cell (a key prefix, an ID range or an exact key). This returns a superset of the answer.
3. Refine: compute the true distance for each candidate and drop the rest.

The cover may include extra area, which step 3 removes, but must never miss any. CockroachDB’s documentation draws the main dividing line well: R-trees divide the objects, building a tree shaped by the data, while geohash, S2 and H3 divide the space into fixed cells. Quadtrees sit in between: fixed split rules, applied only where the data is dense.

Geohash: interleave the bits, keep the prefix

Geohash, released by Gustavo Niemeyer in 2008, is a Z-order (Morton) curve with a text encoding. To encode a point, play twenty questions with the map: is the longitude in the east half (1) or the west half (0)? Halve the box. Is the latitude in the north half (1) or south (0)? Halve again. Alternate, longitude first, then cut the bits into groups of five and write each as one base32 character from 0123456789bcdefghjkmnpqrstuvwxyz (no a, i, l or o).

Because each character only narrows the previous box, a geohash’s prefix is its parent cell. “Everything in this cell” is a range scan on any sorted store, geohash >= 'te7u3' AND geohash < 'te7u4', and zooming out is dropping characters.

Precision: how big is a cell?

Each character adds 5 bits, and longitude takes the extra bit when the count is odd. With b longitude bits a cell is 360° / 2^b wide; with b latitude bits it is 180° / 2^b tall. A degree is about 111 km, and a degree of longitude shrinks by the cosine of the latitude. Five characters give 13 + 12 bits, so 360 / 8,192 = 180 / 4,096 ≈ 0.044°: about 4.9 km × 4.9 km at the equator.

Redis skips the text and stores a 52-bit integer, 26 bits each of longitude and latitude, which fits exactly in a sorted set’s double-precision score. 360° / 2^26 is about 0.6 m at the equator.

The boundary problem and the 3×3 query

The prefix property works one way only: a shared prefix means near, but near does not mean a shared prefix. Two points 110 m apart in Goregaon, Mumbai, encode to te7ucxz and te7v18p. They share only te7, a cell 156 km wide, because a 4-character border runs between them.

The fix is mechanical: query the searcher’s cell plus its 8 neighbours (found by adding or subtracting one from the longitude or latitude bits), then filter by distance. If each cell is at least as wide and as tall as the radius, the circle can never reach past that 3×3 block. Redis does exactly this: it computes the 1 + 8 areas around the centre, turns each into a score range on the sorted set, and discards members outside the shape.

Geohash also cuts degrees, not kilometres. A 5-character cell is 4.9 km wide at the equator, 4.3 km in Delhi and 4.9 × cos 60° ≈ 2.4 km in Helsinki, while its height stays near 4.9 km. Near the poles cells become slivers, and across the 180° meridian neighbours share nothing, so neighbour arithmetic must wrap. Redis refuses latitudes beyond ±85.05°.

Quadtrees: split only where it’s crowded

A fixed grid has one cell size, and it is always wrong somewhere. A quadtree lets the data decide. Start with one square; give each node a capacity; when a node overflows, split it into four equal quadrants and push its points down. Raphael Finkel and Jon Bentley named the structure in 1974 (their version split at a data point); system designs use this bucket variant, which always splits at the midpoint.

At production scale, take a 40 km × 40 km city and 100 drivers per leaf. In a core with 200 drivers per km², a leaf may cover at most 0.5 km² (0.71 km a side), reached at depth 6 with 0.625 km leaves. In outskirts at 2 per km², a leaf may cover 50 km², reached at depth 3 with 5 km leaves. A uniform grid of 0.625 km cells would need 64 × 64 = 4,096 cells, most nearly empty.

k-nearest-neighbour search is where quadtrees shine. Keep a priority queue ordered by the minimum possible distance from the query point to each node’s square; pop the closest entry, expand it if it is a node, emit it if it is a point. When a point comes off the queue nothing still waiting can be closer, so the first k points popped are the k nearest. You never choose a radius: the search reaches farther in sparse areas on its own.

The price is updates. A moving driver is deleted from one leaf and inserted into another, which can split a leaf or empty four siblings that should merge, all under locks in a shared in-memory tree. Common fixes: one small tree per city; rebuild a fresh tree from a snapshot every few seconds and swap it in; or keep the tree for static places and handle drivers with a fixed grid. You meet quadtrees in custom matching services, in PostgreSQL’s SP-GiST operator class quad_point_ops, and as the skeleton of S2.

R-trees and PostGIS: boxes around the data

An R-tree, introduced by Antonin Guttman in 1984, groups objects instead of cutting space. Each leaf holds a few objects, each internal node stores the bounding rectangle of everything beneath it, and the tree stays balanced like a B-tree. A search enters every child whose rectangle overlaps the query; sibling rectangles may overlap, so it sometimes follows several branches.

R-trees shine when the data is shapes: delivery zones, geofences, store catchments. PostGIS builds an R-tree on PostgreSQL’s GiST framework, indexing each geometry’s bounding box and evaluating predicates in two passes: a fast box test in the index, then an exact test on the survivors. MySQL’s SPATIAL INDEX is an R-tree too.

CREATE TABLE restaurants (
  id    bigint PRIMARY KEY,
  name  text NOT NULL,
  geog  geography(Point, 4326) NOT NULL
);
CREATE INDEX restaurants_geog_gist ON restaurants USING GIST (geog);

-- Within 2 km: geography distances are in metres
SELECT id, name FROM restaurants
WHERE  ST_DWithin(geog, 'SRID=4326;POINT(77.6101 12.9279)'::geography, 2000);

-- The 20 nearest, whatever the distance (index-assisted k-NN)
SELECT id, name FROM restaurants
ORDER  BY geog <-> 'SRID=4326;POINT(77.6101 12.9279)'::geography
LIMIT  20;

On geography, ST_DWithin measures metres on the WGS84 spheroid and uses the index automatically. The <-> operator uses it only inside ORDER BY with a constant on one side.

If your data already lives in PostgreSQL, PostGIS is usually the first answer. Its limits are one database’s write rate and an R-tree that can’t simply be range-split across machines, which is why CockroachDB chose S2 cells instead.

S2: squares on a sphere

Google’s S2 library makes the quadtree global and fixed. Put a cube around the Earth and project its 6 faces onto the sphere, with a non-linear stretch so cells come out roughly equal in size. Each face is a quadtree: every cell splits into 4, from level 0 (the face) to level 30, so 31 levels, and the leaf cells are about 1 cm across (0.74 cm² on average).

Every cell has a 64-bit ID: 3 bits for the face, 2 bits per level for the child taken, then a single 1 bit and zeros. A cell’s level is the position of its lowest set bit, its parent is a couple of bit operations away, and, crucially, all descendants of a cell fall in one contiguous ID range. “Points in this cell” becomes cell_id BETWEEN range_min AND range_max on any sorted key-value store. Within a level, cells are numbered along a Hilbert curve, six of them joined into one loop over the sphere.

Why a Hilbert curve

Geohash’s Z-order curve interleaves bits and reads the result as a number. At every block boundary it jumps to a cell that is not a neighbour. A Hilbert curve visits the same cells so that every step moves to an adjacent one, and a region therefore costs fewer, longer ranges.

Region coverings: mixed levels for one query

To search a circle, S2RegionCoverer approximates it with a few cells of mixed levels: big cells inside, small ones along the edge. You set max_cells (default 8) and optional minimum and maximum levels. The covering always contains the whole circle, and each cell becomes one ID range to scan.

For scale, S2’s statistics put an average level-12 cell at 5.07 km² (edges about 2 km), level 13 at 1.27 km², and level 16 at 0.02 km² (edges of 100–150 m). Areas vary only about 2× within a level, far less than geohash at high latitudes. Beyond Google’s own products, CockroachDB stores S2 coverings in an inverted index and goes down to level 30 for GEOGRAPHY columns.

H3: hexagons for counting and comparing

Uber built H3 for a different job. Surge pricing and dispatch analytics are mostly about bucketing events into areas and comparing neighbouring areas: ride requests versus free drivers in each patch of a city, and how each patch compares with those around it.

H3 projects the Earth onto an icosahedron and lays a hexagon grid on its 20 faces. Resolution 0 has 122 base cells: 110 hexagons and 12 pentagons, one at each icosahedron vertex, because a sphere can’t be tiled with hexagons alone; the orientation puts all 12 in the ocean. Each finer resolution has cells one-seventh the area (aperture 7), across 16 resolutions, 0 to 15. Resolution r has 2 + 120 × 7^r cells: about 4.84 billion at resolution 9.

The reason for hexagons is the neighbours. A square has 8 neighbours at two distances: 4 share an edge, 4 touch only at a corner and are √2 ≈ 1.41 times farther away. A hexagon has 6 neighbours, all at the same distance, all sharing an edge.

That uniformity makes smoothing simple: the “k-ring” of cells within k steps approximates a circle, with 1 + 3k(k + 1) cells (7, 19, 37). IDs are 64-bit integers, and a set of cells can be compacted into coarser parents: Uber’s example shrinks California from 10,633 resolution-6 cells to 901.

H3 suits keys in a key-value store or warehouse: store each event’s cell, aggregate with GROUP BY cell, and answer “near me” with cell IN (the 7 or 19 cells of a k-ring). It suits range scans less, since nearby cells only tend to get nearby IDs.

Choosing a scheme

A sensible interview default: PostGIS for relational data and modest write rates, Redis GEO for live positions, H3 for pricing and analytics by area, S2 for a global cell ID in a distributed store, and a quadtree when the question is really in-memory k-NN over uneven density.

Live locations: Redis GEO and moving drivers

Drivers move every few seconds, which makes the index write-heavy. The usual pattern keeps only the latest position in memory. The driver app pings a stateless location service every 4 seconds; the service writes the position to a Redis geo set for the city and appends the ping to a log such as Kafka for trip history; the matcher runs GEOSEARCH when a rider asks for a car.

A Redis geo set is just a sorted set scored by the 52-bit geohash, so GEOADD costs O(log N) and ZREM deletes. What a sorted set cannot do is expire one member, so track freshness in a second set scored by last-seen time:

GEOADD    drivers:{blr} 77.6245 12.9352 d:48213
ZADD      drivers:{blr}:seen 1793121936 d:48213
GEOSEARCH drivers:{blr} FROMLONLAT 77.6101 12.9279 BYRADIUS 2 km ASC COUNT 20 WITHDIST
ZRANGE    drivers:{blr}:seen -inf 1793121906 BYSCORE
ZREM      drivers:{blr} d:48213 d:77310
ZREM      drivers:{blr}:seen d:48213 d:77310

The first two run on every ping, pipelined into one round trip. The third is the search. The last three are a sweeper that finds drivers silent for 30 seconds and removes them from both sets, so a phone that died in a tunnel stops being offered rides. The {blr} hash tag keeps both keys in one Redis Cluster slot. Redis computes distance with the Haversine formula on a spherical Earth, documented as up to 0.5% off: fine for matching, not for billing.

Worked example: drivers near a pickup

Assume 500,000 drivers online at peak, each pinging every 4 seconds, and riders searching within 2 km.

Writes. 500,000 / 4 s = 125,000 updates per second, each a GEOADD plus a ZADD: 250,000 Redis commands per second. Memory is small: at a rough 100 bytes per sorted-set entry, 500,000 × 2 × 100 B ≈ 100 MB.

Hot keys. A key lives on one shard. A megacity with 60,000 online drivers sends 60,000 / 4 = 15,000 updates per second to one sorted set on one Redis process. If that is too much, use one key per 4-character geohash cell (39 km × 19 km) and let each search hit the 1 to 4 keys its circle touches: the boundary problem, one level up. See database sharding for the general version.

Cells, if you build the grid yourself in Cassandra or DynamoDB with the cell as the partition key:

• 5 characters. Mumbai cells are 4.6 km × 4.9 km, so 9 cells always cover a 2 km circle. But the block is 13.9 km × 14.6 km ≈ 202 km² against π × 2² ≈ 12.6 km²: 16× over-fetch, about 20,000 candidates at 100 drivers per km².
• 6 characters. Cells (1.16 km × 0.61 km) are smaller than the radius, so you need ⌈4 / 1.16⌉ + 1 = 5 columns by ⌈4 / 0.61⌉ + 1 = 8 rows: 40 lookups covering about 28 km², 2.2× over-fetch, roughly 2,800 candidates.

Ask for fewer drivers. The matcher needs the nearest 20, not all 1,260 inside 2 km. Search 500 m first: in the core that circle holds 0.785 km² × 100 ≈ 79 drivers and you are done; in outskirts at 1 driver per km², widen to 3 km. An expanding radius gives a fixed grid the quadtree’s density sense without its update cost. It matters for Redis too: GEOSEARCH … COUNT 20 without ANY still examines and sorts every member in the scanned area.

Cell changes. At 36 km/h a driver moves 40 m between pings. The chance a random 40 m step crosses a border of a w × h cell is about (2/π) × 40 × (1/w + 1/h); for 6-character cells, 0.64 × 40 × (1/1,156 + 1/607) ≈ 6%. If you maintain “cell → drivers” sets yourself, 94% of pings never touch them.

Going deeper: failure modes

Hot cells. When a cricket match ends at Wankhede, tens of thousands of riders open the app inside a few cells. Start with a small radius, cap candidates per search, cache results per cell for a second, and don’t let one megacity share a Redis process with others; the playbook in hot keys applies.

Ghost drivers and GPS noise. Without a sweeper, drivers whose phones lost signal stay matchable forever; even with one, a 30-second window means occasional stale matches, so dispatch must confirm with the driver before committing. GPS jitter can make a parked car hop between cells; skip updates that moved only a few metres.

Edges of the map. At the 180° meridian, which runs through Fiji, geohash neighbours share no prefix, and near the poles cells degenerate. City apps rarely notice; global shipping or aviation products do. S2 and H3 have no seam there.

Mismatched cells. A client computing 6-character geohashes against a server indexing 7 silently misses matches. Keep the cell scheme in one shared library.

Cheat sheet

How to say it in the interview

“A B-tree can’t do ‘within 2 km’ well, because latitude and longitude ranges each return a strip across the map. So I map 2D to 1D with cells. For live drivers I’d use Redis GEO: a sorted set scored by a 52-bit geohash, where GEOSEARCH scans the centre cell and its 8 neighbours and filters by distance. 500,000 drivers pinging every 4 seconds is 125,000 writes a second, so I shard by city, keep only the latest position with a last-seen sweeper, and stream pings to Kafka. Delivery zones are polygons, so they live in PostGIS with a GiST index, and surge pricing buckets demand into H3 hexagons.”

Why query 9 cells instead of 1? Nearby points can sit on opposite sides of a cell border and share no prefix. If a cell is at least as big as the radius, the circle can’t reach beyond the centre cell’s 8 neighbours, so 9 lookups always suffice.

Geohash or H3 for surge pricing? H3: every neighbour is equidistant, so smoothing demand across neighbours is uniform, and cell areas vary far less across latitudes. Geohash is fine for “drivers near me”, where you filter by exact distance anyway.

How do you find the nearest 5 drivers when density varies 100×? Either a quadtree with best-first k-NN, which searches farther where data is sparse, or a fixed grid with an expanding radius (500 m, then 1 km, then 3 km). The second stays cheap under 125,000 writes a second.

Why not keep driver locations in PostGIS? Every ping becomes a row update, a new index entry and a write-ahead log record, and the R-tree can’t be range-split across machines. Live positions are disposable state; an in-memory store sharded by city fits them, with PostGIS kept for shapes and history.

Where to go next

• Proximity search: the reusable “near me” pattern built on these indexes.
• Design Uber: live locations, matching and surge pricing end to end.
• Design nearby places search: a read-heavy index of mostly static points.
• Design food delivery: delivery zones as polygons plus moving riders.
• Design nearby friends: moving objects on both sides of the query.
• Redis: sorted sets, pipelining and clustering behind Redis GEO.
• Database indexes: the B-tree these indexes work around, and GiST in context.

References and further reading

1. Redis GEOADD commandredis.ioGeo sets are sorted sets scored by a 52-bit interleaved geohash; the 1 + 8 area search; latitude limits of ±85.05°; Haversine distance with up to 0.5% error.
2. Redis GEOSEARCH commandredis.ioBYRADIUS and BYBOX searches, ASC sorting, COUNT with ANY, and the O(N + log M) cost of scanning the grid-aligned area.
3. S2 Geometry: S2 cell hierarchys2geometry.ioCube faces projected onto the sphere, six linked Hilbert curves, levels 0–30, the 64-bit S2CellId layout, and S2RegionCoverer with its default of 8 cells and median area ratios.
4. S2 Geometry: S2 cell statisticss2geometry.ioMinimum, maximum and average cell area and edge length at every level, used for the level sizes quoted here.
5. H3: overview of the core libraryh3geo.orgThe icosahedron projection, 122 base cells, 12 pentagons at every resolution, and aperture-7 subdivision.
6. H3: tables of cell statistics across resolutionsh3geo.orgCell counts (2 + 120 × 7^r), average hexagon areas and edge lengths for resolutions 0–15.
7. H3: Uber’s Hexagonal Hierarchical Spatial Index (Uber Engineering, 2018)uber.comWhy Uber buckets marketplace events into hexagons for surge pricing, equidistant neighbours, approximate parent containment, k-rings and compaction.
8. PostGIS workshop: spatial indexingpostgis.netGiST indexes over bounding boxes, the R-tree structure PostGIS uses, and the two-pass index-then-exact-check evaluation.
9. PostGIS reference: ST_DWithinpostgis.netDistance in metres for geography (spheroid by default) versus SRID units for geometry, and the built-in index-assisted bounding-box test.
10. CockroachDB documentation: spatial indexescockroachlabs.com“Divide the objects” (R-trees, PostGIS) versus “divide the space” (S2 cells), and why a distributed SQL database chose the latter.