Geospatial indexes

The problem: the nearest store

Snip adds store-locator links: a retail chain uploads its 4,000 store locations, and one short link sends each visitor to the page of the store nearest them (using the location from their IP address or their phone). Every redirect becomes a nearest-neighbour query: given a point, find the closest of thousands of points, in about a millisecond.

Why two indexes don't help

An index on latitude finds every store in a horizontal band; one on longitude, every store in a vertical band. "Near me" is the small square where they cross, but the database has to fetch a whole band from one index and filter it, or intersect two large sets. A B-tree sorts one dimension; location has two.

All the main geospatial indexes do the same thing in different ways: divide the map into cells, give each cell an ID such that nearby cells usually share a prefix or a parent, and index the cell IDs.

Geohash: cells as strings

Geohash splits the world in half by longitude, then by latitude, then longitude again, writing one bit per split, and encodes every 5 bits as a character. Each extra character divides a cell into 32 smaller ones. Points in the same cell share the whole string; nearby points usually share a long prefix.

Central London at precision 6 is gcpvj0. Because geohashes are strings, a plain B-tree index on them supports LIKE 'gcpvj%': every store in that cell, from one index range.

const BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";

export function geohash(lat: number, lon: number, precision = 6): string {
  let latLo = -90, latHi = 90, lonLo = -180, lonHi = 180;
  let hash = "", bits = 0, ch = 0, even = true;
  while (hash.length < precision) {
    if (even) {
      const mid = (lonLo + lonHi) / 2; // even bits split longitude
      if (lon >= mid) { ch = (ch << 1) | 1; lonLo = mid; } else { ch <<= 1; lonHi = mid; }
    } else {
      const mid = (latLo + latHi) / 2; // odd bits split latitude
      if (lat >= mid) { ch = (ch << 1) | 1; latLo = mid; } else { ch <<= 1; latHi = mid; }
    }
    even = !even;
    if (++bits === 5) { hash += BASE32[ch]; bits = 0; ch = 0; }
  }
  return hash;
}

Tested against the standard reference point (57.64911, 10.40744), which encodes to u4pruydqqvj, and London's gcpvj0.

The edge problem. Two points a few metres apart on either side of a cell boundary can have completely different geohashes. So a nearby search never checks just one cell: it checks the cell and its eight neighbours, then measures real distances to the candidates.

Try it

Tested the same way on 4,000 stores across London with 500 random queries: searching the nine 5-character cells around each point checked about 213 stores on average instead of 4,000 and found the true nearest every time. Two caveats the lab shows: if the nine cells are empty, search a wider ring (or shorter geohash); and the nine cells only guarantee the true nearest if it's within one cell's width, so a found store farther than that needs one more ring checked.

Quadtrees: cells that adapt

A quadtree splits a square into four whenever it holds too many points, so dense city centres get small cells and empty countryside stays one big cell. It adapts to data density, which fixed grids don't, at the cost of being a tree structure to maintain rather than a string you can index anywhere.

S2: cells on a sphere

Flat grids distort near the poles and across the date line. Google's S2 library projects the sphere onto the six faces of a cube and orders each face's cells along a Hilbert curve, a path that keeps nearby cells close in the ordering. Cells nest over 31 levels and each has a 64-bit ID, so "cells near X" become a few numeric ranges in an ordinary index.

H3: hexagons

Uber's H3 tiles the world with hexagons at 16 resolutions, each about a seventh the area of the one above. Squares have neighbours at two distances (side and corner); a hexagon's neighbours are all the same distance away, which makes "the ring of cells around this one" uniform. At resolution 9 a hexagon averages about 0.1 km²; at resolution 7, about 5 km². Uber uses them to measure supply and demand per hexagon for surge pricing (12.07 Matching supply and demand).

Recap

Interview questions