Geospatial indexing

Why a B-tree on (lat, lng) cannot find nearest neighbors

A B-tree is a one-dimensional ordered structure. A composite index on (lat, lng) sorts rows by latitude first, and by longitude only within a single fixed latitude. A "within 2 km" query becomes a range on both columns at once:

WHERE lat BETWEEN a AND b
  AND lng BETWEEN c AND d

The engine seeks the latitude band with the leading column, but inside that band the matching longitudes are scattered across the whole map, so it scans the band and filters on longitude, a wide partial scan rather than a tight seek. Nearest-neighbor is worse: B-tree order encodes no two-dimensional closeness, so two points next to each other on the map can sit far apart in the index. The fix is an index that preserves 2D locality, a space-filling-curve key (geohash, S2, H3) or an R-tree.

How geohash turns two coordinates into one sortable string

Geohash bisects the longitude range and the latitude range repeatedly, emitting one bit per split (upper half or lower half), and interleaves the two streams: even-position bits carry longitude, odd-position bits carry latitude. That interleaving traces a Z-order (Morton) curve. Every 5 bits map to one character of the alphabet 0123456789bcdefghjkmnpqrstuvwxyz, where a, i, l, o are left out to avoid visual confusion.

Nearby points usually share a common prefix, and a longer shared prefix means a smaller cell and closer points. A 5-character hash pins a location to about plus or minus 2.4 km, a 6-character hash to about plus or minus 0.6 km. Because the result is a sortable string, you can store and query it in an ordinary B-tree, a sorted set, or a prefix scan, which is why geohash is common.

The geohash boundary trap and the nine-cell fix

Wrong "Two points are close, so they share a long geohash prefix." The implication only runs one way. Close points usually share a prefix, but two points on opposite sides of a cell boundary can be a few metres apart and still diverge early in their bits. The extreme case is either side of the equator or prime meridian, which share almost nothing.

Right a single prefix scan misses neighbors that land in the adjacent cell. To answer "near this point" correctly, compute the query cell plus its 8 surrounding neighbor cells, scan all 9, then compute exact distance and drop anything outside the real radius. Cells are rectangles, so the distance step is what answers a circular query.

How a quadtree adapts to point density

A quadtree splits a region into exactly four quadrants (NW, NE, SW, SE), and each of those splits again only when it holds more than a set number of points. Dense areas subdivide deeply while empty areas stay shallow, so the tree follows the data instead of imposing a uniform grid. It answers range and point queries by descending to the covering cell and checking neighboring nodes. Geohash is essentially a quadtree flattened onto a Z-order curve.

S2 quadrilaterals versus H3 hexagons

Both map the sphere and number cells along a space-filling curve, but the cell shapes diverge.

S2 (Google) projects the six faces of a cube onto the sphere and subdivides each face into four children per level, so cells are quadrilaterals bounded by four geodesics, not hexagons. It links six Hilbert curves into one loop, which gives better locality than geohash's Z-order. The hierarchy runs 31 levels (0 to 30) down to leaf cells about 1 cm across, each cell id a sortable 64-bit integer.

H3 (Uber) projects onto an icosahedron and tiles it with hexagons. A hexagon has six edge-neighbors at roughly equal center-to-center distance, which suits movement and flow modeling; a square grid has four edge-neighbors plus four diagonal ones farther out. You cannot tile a sphere with hexagons alone, so H3 carries exactly 12 pentagons at every resolution, one per icosahedron vertex. Resolution 0 holds 122 base cells (110 hexagons and 12 pentagons), across 16 resolutions.

Wrong "A fine H3 cell nests perfectly inside its coarse parent." H3 subdivides by aperture 7, so each hexagon has about seven children near one-seventh the area, a ratio that does not tile exactly. H3 gives exact logical containment but only approximate geometric containment, so a child's boundary can spill slightly across the parent's. Geohash, quadtree, and S2 cells are exactly nested.

How a proximity or k-nearest query runs

Every cell-based radius query is filter then refine: compute the cells covering the query point, gather the neighboring cells so boundary points survive, fetch candidates by id or prefix range, then compute exact great-circle distance and drop whatever falls outside the radius.

k-nearest expands outward. Start at the query cell, grow in rings of neighbor cells, and stop once you hold k candidates and the k-th distance is smaller than the distance to the nearest unexplored ring, then sort by exact distance.

PostGIS exposes true index-assisted KNN through the <-> operator, but only inside an ORDER BY and only when one operand is a constant literal:

SELECT id FROM places
ORDER BY geom <-> 'POINT(-73.98 40.75)'
LIMIT 5;                       -- walks the R-tree toward the nearest geometries

It needs PostGIS 2.2 and PostgreSQL 9.5 or newer. <-> is 2D distance while <#> compares bounding boxes. Move the operator into a subquery or a WHERE clause and the index assist drops.

What PostGIS and Redis store in the index

A PostGIS GiST index does not store your exact geometry; it stores bounding boxes. A query runs in two passes: a fast index test of which boxes intersect the search box (which may return false positives), then an exact check with ST_DWithin or ST_Distance. The R-tree rides on top of the GiST framework, built with CREATE INDEX ... USING GIST (geom).

Redis GEO is geohash-backed; there is no R-tree involved. Points live in a sorted set whose score is a 52-bit geohash integer of interleaved lat/lng bits, which a double's 52-bit mantissa stores exactly. GEOSEARCH ... BYRADIUS derives the geohash ranges covering the search area and its neighbors, scans them, then filters by exact distance, at cost O(N + log(M)) for N elements in the search bounding box and M items in the index. GEORADIUS did the same job but was deprecated in Redis 6.2 in favor of GEOSEARCH.

Where each choice bites

Geohash cells are defined in degrees, so their ground area shrinks toward the poles; equal-area coverage is a reason teams reach for S2 or H3. No cell scheme removes the exact-distance step, since a rectangle or hexagon only approximates a circle. And the neighbor-cell query stays mandatory at finer precision, because smaller cells put a query point near a boundary more often.