Proximity Search

A quadtree recursively divides a region into four quadrants. Dense quadrants split further, so a busy city receives finer cells than empty countryside. A radius query traverses every node whose bounding region intersects the search circle; it cannot simply visit the rider’s leaf and assume a fixed number of adjacent leaves is enough. At the leaves, exact distance checks discard the points that lie in an intersecting rectangle but outside the circle.

Follow the left map first. Sparse NW, NE, and SW stay coarse. The dense SE keeps splitting until every leaf holds at most k = 5 points. The right side is the same story as a tree: only overloaded cells grow children.

That density adaptation is the gift. The cost at database scale is uneven depth (busy downtowns go deepest) and pointer chasing that turns into random disk reads once the tree no longer fits in RAM. Quadtrees stay common in memory for map tiles and games. They are a weak default for a mutable on-disk primary index.

A k-d tree partitions points by alternating coordinate axes. Balanced median splits keep the tree shallow for a reasonably static dataset, while bounding regions help prune subtrees that cannot intersect the query. Frequent updates can disturb the balance and require maintenance or rebuilding. The key question is how many tree regions a real query touches, because logarithmic depth alone does not imply logarithmic work for every radius search.

Classic k-d trees share the disk problem: pointers. The modern packaging is the BKD tree: pack points into page-sized blocks, often rebuild from batches. That is the lineage behind Elasticsearch geo fields. Great for chunked/immutable-ish data; less natural for millions of single-point rewrites per second.

Wrap every object in a minimum bounding rectangle. Nest nearby rectangles inside larger ones up to the root. Leaves share depth; nodes fit pages; inserts/deletes split and merge like a B-tree.

Rectangles may overlap, so a query can descend multiple branches. R*-tree heuristics keep overlap low in real systems. PostGIS (GiST), SQLite, and Oracle Spatial lean on this family when you need "does this zone contain this address" or "does this road cross this county."

Hierarchical grid: each character (5 bits) zooms into one of 32 subcells. Shared prefixes usually mean shared cells. A five-character geohash is roughly kilometers across; nine characters lands near meters. Redis GEOADD stores a 52-bit geohash integer as a sorted-set score.

Walk left to right. Layer 1 picks a coarse cell. Layer 2 zooms inside it. Layer 3 is fine enough to mark a city. Pune’s real hash looks like te7x2, but the idea is the same: longer shared prefixes mean a smaller shared box on the map.

Cell boundaries are the main correctness trap. Two points a meter apart may have unrelated prefixes because one lies across an edge. Enumerate every cell that intersects the requested radius, fetch candidates from those cells, and apply the final distance predicate. A fixed 3×3 neighborhood is sufficient only when the chosen cell dimensions and query radius make it cover the whole circle. Larger radii, high latitudes, and changing resolution can require more cells.

-- candidates from a prefix (still over-approximate)
SELECT id FROM drivers
WHERE geohash LIKE 'dr5ru%'   -- plus neighbor prefixes in app code
-- then: filter by ST_Distance / haversine < 2000m and rank

S2 maps the sphere onto cube faces and recursively subdivides them into hierarchical cells with 64-bit identifiers. Its region-covering operations can approximate a spherical query with a bounded set of cells, which is useful around the antimeridian and at global scale. The cells are not perfectly equal-area, and a cover can include extra ground area. Query the cover, then evaluate the actual spherical geometry to remove those extra candidates.

H3 provides a hierarchical grid made mostly of hexagons, with pentagons required by the spherical layout. A cell identifier is useful for aggregation and neighbor traversal, but graph distance in cells is not the same as a fixed distance in meters. Use the library’s supported traversal and covering behavior, handle distortion near exceptional cells, and choose enough cells for the requested geographic radius before exact filtering.