Concept 16: Geospatial Indexing & Location-Based Services — Finding the 10 Nearest Drivers in 5 ms

System Design Bible — File 16 Difficulty: ★★★★☆ Prerequisites: File 02 (Caching — Redis and its sorted sets carry half of this file), File 04 (Sharding — you will shard the world itself, and the hot-spot problem returns with a vengeance), File 06 (Consistent Hashing — for contrast: random spread is exactly what geo data must NOT do), File 11 (Databases — B-trees, indexes, and why the unit of I/O shapes everything), File 13 (Search — the "an index is a sorted structure exploited by prefix" idea recurs here), File 14 (Vector Databases — the curse of dimensionality; this file is its happy inverse), plus the fundamentals unpacked in Section 0.

Table of Contents#

0Prerequisites — What You Must Understand First#

"Find restaurants near me" sounds like a WHERE clause. It isn't — it's a query no classic index can answer, over a coordinate system that lies to you, against data that may be moving. Four ideas make the whole field obvious.

0.1Latitude, longitude, and the lies of a spherical coordinate system#

A point on Earth is addressed by two numbers. Latitude measures how far north or south you are: 0° at the equator (the circle around Earth's middle), +90° at the North Pole, −90° at the South Pole. Longitude measures how far east or west you are: 0° at the prime meridian (the arbitrary reference line through Greenwich, London), ranging ±180° until the lines meet at the antimeridian in the Pacific. So San Francisco is (37.77, −122.42) — 37.77° north, 122.42° west. Two floats. Looks like a clean 2-D plane.

It is not a plane, and three specific lies follow from the sphere — each one a real bug in a real system:

Lie 1 — a degree is not a fixed distance. A degree of latitude is always ~111 km. But a degree of longitude is 111 km only at the equator — the longitude lines converge toward the poles, so at 60° north (Oslo), one longitude degree is only ~55 km, and near the pole it approaches zero. Any code that computes "within 0.1 degrees" as a distance filter returns a circle at the equator and an ever-narrower ellipse as you go north. Distance must be computed with spherical math (§2.2), never with degree arithmetic.

Lie 2 — the world wraps. Longitude +179.9° and −179.9° are 22 km apart in reality and 359.8 apart numerically. A range query near the antimeridian (WHERE lon BETWEEN 179 AND -179) is nonsense to a numeric index. Every naive implementation breaks for ships, flights, and Fiji.

Lie 3 — straight lines aren't straight. The shortest path between two points on a sphere is a great-circle arc (the path an airplane flies — the "curved" line on flight maps is the straight one on the globe), not the straight line of plane geometry. For neighborhood-scale queries the error is negligible; for "nearest warehouse to this transatlantic customer" it is hundreds of kilometers.

Hold this: coordinates are two floats, but the space they live in is a wrapping, distorting sphere — every distance must be spherical, and every index must survive the antimeridian and the poles.

0.2Why a B-tree cannot answer "near" (the one-dimensional prison)#

File 11 taught you the B-tree: a structure sorted by one key, brilliant at "find this value" and "walk this range." File 13 showed the first thing it can't do (search inside text); File 14 showed the second (768-dimensional proximity). Geospatial is the third — and understanding precisely why is the foundation of every structure in §4.

Try to index locations the obvious way: a B-tree on latitude and a B-tree on longitude (or one composite index on (lat, lon)). Now ask: "everything within 5 km of me." That's a 2-D constraint — a small box around your position. The latitude index can efficiently find the rows in your latitude band: say 50,000 points in the strip between 37.72° and 37.82°... spanning the entire planet horizontally — that strip contains points in San Francisco, but also Athens, Seoul, and the middle of the Pacific. The index has no idea about longitude; you filter those 50,000 rows one by one. Intersecting two single-column indexes doesn't save you: each index yields a planet-wide strip, and the DB must materialize and intersect two huge row sets to produce the tiny box you wanted. The composite (lat, lon) index is worse than it looks for the same reason File 11 §5.4's leftmost-prefix rule said: it's sorted by latitude first, so all longitudes for one latitude are adjacent, but the longitudes you want are scattered across thousands of distant latitude groups.

The root cause is fundamental, not an implementation detail: a B-tree imposes one total order on the data, and no single ordering of 2-D points keeps all spatially-near points near each other in the order. Sort by latitude and two points on the same street (differing in longitude) can be separated by a million rows. Proximity is a 2-D relationship; the index is a 1-D line.

Note the beautiful contrast with File 14: there, 768 dimensions made proximity indexing provably approximate (the curse of dimensionality — nothing can be pruned). Here we have only 2 dimensions — few enough that the problem is exactly solvable with cleverness. The entire field of geospatial indexing is that cleverness: either fold 2-D into 1-D while approximately preserving locality (§0.4, geohash/S2/H3) or build a natively 2-D tree (quadtree, R-tree). Hold this: "near me" is un-indexable by any one-column sort; every geospatial index is a scheme to escape the 1-D prison — and at 2 dimensions, escape is actually possible.

0.3Two workloads that look alike and are architecturally opposite#

Every location system serves one of two workloads, and conflating them is the classic junior design error:

Static places (POI search). A POI (Point of Interest — a restaurant, ATM, store; industry jargon for "a thing on the map with a fixed location") is written once and read millions of times. Yelp, Google Maps place search, "ATMs near me." Read:write ratio ~10,000:1 (File 12's ratio discipline). The index can be expensive to build, disk-resident, heavily cached (File 02), replicated for reads — all the read-scaling machinery of this bible applies, and freshness barely matters (a restaurant moves... never).

Moving objects (live location). A ride-hail driver's phone emits a location ping (a periodic "here I am" report) every ~4 seconds. One million online drivers = 250,000 location writes per second, forever — and every write invalidates the previous position. Now the ratio inverts: writes dominate, data is obsolete in seconds (so durability is nearly worthless — who cares where a driver was 10 minutes ago?), and the index must absorb a permanent write firehose. Disk-resident, expensively-rebuilt structures are disqualified; you need RAM-resident buckets with O(1)-ish updates (§5), TTLs instead of deletes, and you cheerfully throw the data away.

The same query — "nearest 10 X" — sits on top of both, which is why people conflate them. But the index choice, storage tier, and consistency story differ completely, and §4's decision rule branches on exactly this. Hold this: ask "does the data move?" before anything else — static places want a read-optimized disk index; moving objects want a write-optimized RAM grid with expiry.

0.4The space-filling curve: folding the map into a line#

Here's the escape from §0.2's prison, and it's one of the loveliest ideas in this bible. If the problem is "a B-tree needs one ordering, and no ordering preserves 2-D proximity," then relax the goal: find an ordering that preserves proximity approximately — where points close on the map are usually close in the order. Such an ordering is drawn by a space-filling curve: a single line that snakes through every cell of a grid, visiting each exactly once. Number the cells in visit order, and that number is your 1-D sort key.

The simplest useful curve is the Z-order curve (also called a Morton code, after its 1966 inventor), and its construction is almost embarrassingly cheap: take the binary representations of the x and y cell coordinates and interleave their bits. If x = 3 = 11₂ and y = 5 = 101₂, the Morton code alternates y-bit, x-bit, y-bit, x-bit… giving 100111₂ = 39. Plot the resulting visit order over a grid and it traces endless little "Z" shapes:

  y
  3 |  5    7  | 13   15         Walk order: 0,1,2,3,4,5,... traces Z shapes.
  2 |  4    6  | 12   14         Cells 0,1,2,3 (one Z) are all mutually close. ✔
    |---------+---------         Cells 5 and 7: adjacent numbers, adjacent cells. ✔
  1 |  1    3  |  9   11         BUT cells 3 and 4: consecutive numbers (3→4),
  0 |  0    2  |  8   10         yet the curve JUMPS across the boundary — and
    +--------------------  x     worse, cells 7→8 jump across the whole map.
       0    1    2    3          Locality holds USUALLY, not ALWAYS.

Why interleaving works: the high-order bits of the Morton code encode which large quadrant of the map you're in, the next bits which sub-quadrant, and so on — so two points sharing a long prefix of their Morton code are guaranteed to be in the same small square. A prefix is a region! And prefixes are exactly what B-trees (File 11) and sorted structures (File 13's FST) exploit natively. Suddenly "everything in this map square" becomes "everything with this key prefix" — a plain range scan on an ordinary index. The whole geohash family (§4.2) is this trick plus an encoding; S2 (§4.5) is this trick on a better curve.

The imperfection matters too, so stare at it: consecutive-numbered cells are usually adjacent, but the converse fails at boundaries — cells 3 and 4 above touch numerically but the curve teleports; and two cells physically touching across a major boundary (say cells 5 and 10 across the vertical midline) have wildly different numbers. This is the boundary problem, it is the central flaw of every curve-based index, and §3/§4 will show the standard fix (search your cell plus its 8 neighbors). There is also a strictly better curve — the Hilbert curve, which replaces Z's jumps with U-shaped turns so that every consecutive pair of cells is physically adjacent (no teleports), at the cost of a more complex rotation-based bit computation. S2 pays that cost; geohash doesn't. Hold this: interleave the bits and the map becomes a line where prefix = region — imperfect at boundaries (check the neighbors), and Hilbert beats Z where the imperfection is worth money.

1Architectural Definition & "The Why"#

1.1The Plain Definition#

Geospatial indexing is the family of data structures and encodings that make location queries — "what's within this radius?", "the k nearest?", "inside this region?" — answerable in milliseconds over millions or billions of points, by organizing 2-D positions so that spatial proximity maps onto something a computer can exploit: a shared key prefix, a shared bucket, or a shared tree branch. A location-based service (LBS) is any product built on those queries: ride-hailing dispatch, food delivery, "restaurants near me," dating-app discovery, geofenced notifications, fleet tracking.

The analogy that actually holds: postal codes. Nobody finds your house by scanning Earth's coordinates; the world pre-agreed on a hierarchical bucketing — country → region code → district → street. Two addresses sharing the prefix "94103" are guaranteed to be in the same San Francisco district; sharing "9410" puts you in the same city area. Proximity became prefix matching on a string — which is precisely what a geohash is, with mathematically regular buckets instead of historically grown ones. And the postal analogy carries the flaw too: two houses can sit across the street from each other yet fall in different postal districts — the boundary problem, in your mailbox.

1.2"The Why" — The Limits That Forced This to Exist#

Limit 1 — the 1-D index wall. §0.2 in one line: B-trees sort by one key, proximity is two-dimensional, so every classic database answers "near me" with a full scan or a planet-wide strip filter. At 100M POIs and 10,000 QPS (a modest maps workload), scans are off by four orders of magnitude. The index had to be reinvented — this is the same "the existing index is structurally wrong for this access pattern" story as Files 13 and 14, third verse.

Limit 2 — the write firehose of moving objects. §0.3's arithmetic: 1M drivers × one ping per 4 s = 250k writes/s, 24/7 — comparable to the biggest ingestion workloads in File 07, except each write also moves a point through the index. A disk-based tree that rebalances on every update (R-tree, §4.4) dies here; the physics of RAM vs disk (File 02's hierarchy) forces bucket-grid designs where an update is "remove ID from cell A's set, add to cell B's set" — two O(log n) RAM operations.

Limit 3 — one region's traffic is not like another's. Geospatial load is the most skewed workload in this bible: Manhattan at Friday 6 pm vs Wyoming at any time differ by ~10,000× in both data density and query rate, and the skew moves (concerts, airports at 6 am, stadium letouts). Uniform grids waste memory on oceans while melting on cities; this forced adaptive structures (quadtrees that split only where dense, §4.3) and geo-sharding with dynamic balancing (§6) — File 04's hot-shard problem, but the hot key is a place and it commutes.

Limit 4 — the sphere itself. §0.1's lies (converging meridians, the antimeridian wrap, great-circle paths) break naive flat-Earth math in ways that ship as production bugs. S2's entire reason for existing (§4.5) is doing the geometry on the sphere correctly, once, in a library, so ten thousand teams don't each rediscover why their Alaska queries return garbage.

1.3What It Solves — And the Price It Charges#

Every row charges something — Rule 5. The headline trade: you buy millisecond proximity queries by accepting approximate, cell-shaped geometry (fix with a verify phase), neighbor-check discipline (the boundary problem never goes away), and — for moving data — an eventually-consistent view of a world that has already changed.

2The Recursive Sub-Concept Tree#

2.1Sub-Concept: The Three Query Shapes — Range, k-NN, and Point-in-Polygon#

Every LBS feature reduces to one of three queries, and they stress the index differently:

2.2Sub-Concept: Great-Circle Distance & the Haversine Formula#

The great-circle distance is the true shortest distance between two points along the sphere's surface (§0.1 Lie 3). The standard way to compute it from two lat/lon pairs is the haversine formula — a few lines of trigonometry (a = sin²(Δlat/2) + cos(lat₁)·cos(lat₂)·sin²(Δlon/2); d = 2R·asin(√a), with R = Earth's radius ≈ 6,371 km) that is numerically stable even for the tiny angles of nearby points, which is exactly the regime LBS lives in (the naive spherical-law-of-cosines formula loses precision below ~1 km — a real footgun). Cost: a handful of trig operations, ~100 ns. That's cheap per point but not cheap × a million points — which restates the whole architecture of this file: the index produces a small candidate set; haversine verifies it. Never haversine the world; never trust cells without haversine. (Two refinements to name, not implement: for sub-meter accuracy over long distances, Vincenty's formula accounts for Earth being slightly squashed — an ellipsoid, not a sphere; and real products often re-rank the top candidates by road-network travel time — the river between you and that "800 m away" driver makes straight-line distance a lie of its own. Straight-line for candidate retrieval, routing engine for final ranking.)

2.3Sub-Concept: Cell, Precision Level, and the Resolution Ladder#

Every grid system in §4 shares one vocabulary: the world is divided into cells at multiple precision levels, each level subdividing the last — a resolution ladder. Geohash: each added base-32 character splits the cell 32 ways (level 6 ≈ 1.2 km × 0.6 km; level 9 ≈ 5 m — human scale). S2: 31 levels of 4-way splits (level 13 ≈ 1 km²; level 30 ≈ 1 cm²). H3: 16 levels of ~7-way hex splits. The level you index at is a tuning decision with a real trade-off: coarse cells (big) mean few cells per query but huge candidate sets to haversine-filter in dense cities; fine cells (small) mean tight candidate sets but many cells per query (more index lookups, more neighbor checks) and, for moving objects, more frequent cell-crossings (more index writes as drivers move). Decision rule: pick the level where a typical query's radius spans ~1–20 cells; for mixed urban/rural, index at multiple levels or use an adaptive structure (§4.3). This is File 11's "match the layout to the workload," reborn as map resolution.

2.4Sub-Concept: MBR — the Minimum Bounding Rectangle#

Real geographic objects aren't points — roads, rivers, delivery zones, building footprints are lines and polygons. The universal cheap summary of any shape is its MBR (Minimum Bounding Rectangle): the smallest axis-aligned rectangle that fully contains it (for a shape spanning lat 37.1–37.4, lon −122.3 to −122.0, the MBR is just those four numbers). MBRs make an invaluable pre-filter: if two MBRs don't overlap, the shapes inside them cannot intersect — a four-comparison rejection that skips expensive exact geometry. If MBRs do overlap, the shapes still might not ("possibly intersecting" — the same no-false-negatives-but-false-positives shape as File 02's Bloom filter, and the same two-phase discipline: cheap filter, exact verify). The R-tree (§4.4) is an entire index built of nothing but nested MBRs.

2.5Sub-Concept: Cell Covering — Turning Shapes into Sets of Cells#

A covering is the representation of an arbitrary region (a circle, a delivery polygon) as a set of grid cells that together contain it — typically mixing levels: a few big cells for the region's interior, smaller cells tracing its edge. S2's covering algorithm is the canonical one: give it any shape plus a budget ("≤ 20 cells"), and it returns near-optimal cells. Coverings are the workhorse trick of the whole field, because they convert geometry problems into set problems: a radius query becomes "fetch these ~9 cell buckets" (§3); geofencing becomes *precompute each zone's covering into a hash map of cell → zone-IDs, then a ping's zone-test is: look up the ping's cell ID (and its ancestors up the level ladder) in the map* — O(levels) hash lookups instead of ray-casting against every polygon. Trade-off: a covering is approximate — cells at the edge stick out past the true boundary (over-cover: false candidates to verify) or, if you under-cover to save cells, miss slivers of the region entirely (false negatives — usually unacceptable). More cells = tighter fit = bigger index. Precision is a line item.

2.6Sub-Concept: Redis Sorted Sets & GEO (the implementation you'll actually deploy)#

File 02 introduced Redis; the structure carrying this file is the sorted set (ZSET): a collection where every member has a numeric score, kept permanently sorted by score, with O(log n) insert/remove and O(log n + m) range-by-score scans. Now connect it to §0.4: Redis's GEO commands (GEOADD, GEOSEARCH) are nothing but a sorted set whose score is the 52-bit interleaved Morton code of the position. GEOADD drivers -122.42 37.77 driver:42 computes the geohash-style integer and does a ZADD; GEOSEARCH ... BYRADIUS 5 km computes the ~9 cell prefix-ranges covering the circle, walks each as a score-range scan, and haversine-filters the survivors — the entire architecture of this file, shipped as two commands. Knowing that GEO is a ZSET tells you its limits without reading the docs: updates are O(log n) (fine), everything lives in RAM (File 02's cost), one key = one shard slot (a single global drivers key concentrates on one Redis Cluster node — File 04's hot shard; fix by keying per city/region, §6), and members need TTL discipline you must build yourself (§5.2).

3Deep-Dive Mechanics — The Life of a "Find Nearby Drivers" Query#

The canonical flow, end to end. A rider in San Francisco opens the app; the system must return the 10 nearest available drivers in under ~100 ms.

 DRIVERS (write path, continuous)                 RIDER (read path, on demand)
 ────────────────────────────────                 ───────────────────────────
 every ~4s: ping (driver_id, lat, lon)            "find 10 nearest drivers to (37.77,-122.42)"
      │                                                │
      ▼                                                ▼
 ┌─ INGEST ─────────────────────────┐   ┌─ QUERY PLANNER ──────────────────────────┐
 │ 1. gateway → geo-shard router    │   │ A. compute rider's cell at level L        │
 │    (city/region shard, §6)       │   │    e.g. geohash6 = "9q8yyk"               │
 │ 2. compute cell at level L       │   │ B. cover the 5km circle: rider's cell     │
 │    geohash6("9q8yyk")            │   │    + 8 NEIGHBORS (boundary problem, §0.4!)│
 │ 3. cell changed since last ping? │   │    ┌────┬────┬────┐                       │
 │    NO → update coords + ts only  │   │    │ NW │ N  │ NE │  rider may sit 10m    │
 │    YES→ ZREM old cell's set,     │   │    ├────┼────┼────┤  from a cell edge —   │
 │         ZADD new cell's set      │   │    │ W  │ ●  │ E  │  nearest driver can   │
 │ 4. stamp ts; TTL sweeper evicts  │   │    ├────┼────┼────┤  be in ANY neighbor   │
 │    pings older than ~15s (§5.2)  │   │    │ SW │ S  │ SE │                       │
 └──────────────────────────────────┘   │    └────┴────┴────┘                       │
                                        │ C. fetch 9 cell buckets (RAM, ~µs each)   │
   CELL BUCKETS (RAM, per geo-shard)    │    → ~200 candidate drivers               │
   "9q8yyk" → {drv17, drv42, drv88...}  │ D. HAVERSINE each candidate → true meters │
   "9q8yym" → {drv23, drv51...}         │    (§2.2) — kill the square's corners     │
   ...                                  │ E. filter availability/status; sort; top10│
                                        │ F. <k results? EXPANDING RING (§2.1):     │
                                        │    add next ring of 16 cells, repeat      │
                                        └───────────────────────────────────────────┘
                                                       │
                                        G. (real dispatch) re-rank top candidates by
                                           ROAD ETA via routing engine (§2.2) → offer

Four load-bearing details, each an interview point:

The 9-cell fetch is not an optimization — it's correctness. Query only the rider's own cell and you miss the driver 50 meters away across the cell edge (§0.4's boundary problem, cashing out). Every curve-based geo query, in every system, is "cell + neighbors." Geohash neighbor-finding is slightly fiddly (the Z-curve's bit-interleaving makes neighbor codes non-obvious — libraries handle it); H3's hexagons make it trivial (§4.6).

The candidate set is a square-ish blob; haversine makes it a circle. Nine cells cover the 5 km circle plus corner areas up to ~7 km out. Step D isn't paranoia — without it you return drivers outside the promised radius, and (Lie 1, §0.1) your "radius" would silently vary with latitude.

The write path optimizes for the common case: the cell didn't change. A driver moving at 30 km/h crosses a 1.2 km cell every ~2.5 minutes — so ~97% of 4-second pings stay in-cell, needing only a coordinate/timestamp refresh, not an index move. The expensive two-set operation happens only on cell crossings. Pick cells too small (§2.3) and you forfeit this.

Everything the rider sees is already stale. Pings are 4 s apart, the query took 50 ms, the driver kept driving. The returned positions are seconds old by design — which is why step G exists (verify/re-rank at offer time) and why dispatch (§6.3) treats the geo-query as candidate generation, never as truth. This is File 08's eventual consistency, made physical: the real world is the primary, and it doesn't send you a commit log.

4Geospatial Index Structures — Exhaustive Breakdown#

Six structures. Full Rule-4 treatment each. They divide into curve/grid encodings (geohash, S2, H3 — fold 2-D into keyed cells) and spatial trees (quadtree, R-tree — natively 2-D structures), with the naive baseline first because respecting the baseline is a senior tell.

4.1The Baseline: Composite B-tree + Bounding Box (know why it sometimes wins)#

What it is. No spatial structure at all: WHERE lat BETWEEN a AND b AND lon BETWEEN c AND d over ordinary B-tree indexes, then haversine the survivors.

How it works. Compute the bounding box of your radius (lat ± r/111 km; lon ± r/(111·cos lat) — note the cosine, correcting Lie 1). The lat index yields the latitude strip; the DB filters longitude within it.

Why it (barely) works. For small datasets or low traffic, the strip just isn't that big. 100k POIs, city-scale: a latitude strip might hold 2,000 rows; filtering 2,000 rows is microseconds. The full 1-D-prison pain (§0.2) only bites at scale.

Pros. Zero new infrastructure — one SQL query on the DB you already run; trivially correct (easy to reason about the two lies you've patched); transactional with your business data. Cons. The strip problem grows linearly with global data (a planet-wide latitude band, §0.2); no k-NN support (you guess radii); antimeridian wrap needs special-case ugliness. Complexity. O(rows in latitude strip) per query — degenerating toward O(N) as data globalizes. When to use it. Under ~100k points and modest QPS — the "50,000 documents = brute force" answer of File 14 §4.1, geospatial edition. Also the right first version of any product. Interviewers respect "I'd start with a bounding-box query on Postgres and measure" far more than reflexive infrastructure.

4.2Geohash — the Z-order Curve with a Public Face#

What it is. The Morton code of §0.4, encoded as a short base-32 string (a 32-character alphabet of digits and letters — chosen so codes are compact, URL-safe, and human-shareable), where each additional character = one more level of precision, and a shared prefix = a shared region. 9q8yyk is a ~1.2 km × 0.6 km cell in San Francisco; every point inside it geohashes to 9q8yyk….

How it works, step by step. (1) Binary-search each coordinate against its range, emitting one bit per halving: is lon in the upper half of [−180, 180]? For −122.42, no → 0; recurse into [−180, 0], upper half? yes → 1; … (2) Interleave the streams (lon bit, lat bit, lon, lat, …) — this is exactly Morton interleaving, so all of §0.4's properties apply. (3) Chop the bit-string into 5-bit groups; map each to a base-32 character. Worked: (37.77, −122.42) → lon bits 01001…, lat bits 10110… → interleaved 0110011010… → 9q8yy….

Why it works. Prefix = region (§0.4), so a plain B-tree or sorted set over geohash strings answers spatial queries via prefix/range scans — you've smuggled 2-D search into every ordinary database and into Redis (§2.6) with zero new index machinery. That is geohash's entire, considerable value proposition.

Pros. Dead simple; universally supported (Redis GEO, Elasticsearch — File 13's geo_point fields use exactly this — MySQL, DynamoDB patterns); human-legible and shareable (a geohash is a link to a place); hierarchical for free (truncate = zoom out). Cons — each traceable to a §0 lie or the Z-curve. (a) Boundary problem at its worst: Z-jumps mean neighbor cells can have utterly dissimilar codes — the 8-neighbor computation is mandatory and non-obvious. (b) Cells are rectangles that distort with latitude (Lie 1): a level-6 cell is 1.2 × 0.6 km at the equator but squashes narrower toward the poles, so "one cell ≈ one neighborhood" quietly stops being true in Helsinki. (c) Degenerate behavior at the equator/prime-meridian crossings, where near-touching points share no prefix at all (e.g., points straddling the Greenwich line differ in the very first bit — prefix similarity is sufficient for proximity, never necessary). (d) Rectangles tile a flattened projection, inheriting distortion everywhere. Complexity. Encode O(bits); query = ~9 prefix range-scans + haversine filter; storage one short string per point. When to use it. The default when you want geo inside infrastructure you already run — Redis, Elasticsearch, a plain RDBMS — and your product is human-scale local search where centimeter-fair cells don't matter. It's the 80% answer at 20% of the complexity.

4.3Quadtree — the Adaptive Splitter#

What it is. A tree that recursively splits space into four quadrants (NW, NE, SW, SE), but only where the data is dense: each node holds points until it exceeds a capacity (say 50), then splits into four children and pushes its points down.

How it works. Root = the whole map. Insert points; on overflow, split and redistribute; repeat recursively. Manhattan ends up 12 levels deep (tiny leaves, ~50 points each); Wyoming stays 3 levels deep (huge leaves, still ~50 points each). A range query descends from the root, pruning every branch whose quadrant doesn't intersect the circle — the tree version of MBR rejection (§2.4) — and scans only intersecting leaves. k-NN uses a best-first descent with a priority queue: always expand the node nearest the query, stop when the k-th found point is nearer than the nearest unexplored node (the exact-in-2-D cousin of File 14's beam search).

        world                       Every leaf holds ≤ 50 points,
       /  |  \  \                   whether it covers 4 blocks of
     NW  NE  SW  SE ← Wyoming:      Manhattan or half of Wyoming.
    /||\            shallow leaf    THE TREE'S SHAPE *IS* THE
  (dense city: splits again         DATA'S DENSITY MAP.
   and again — deep, tiny leaves)

Why it works. The tree adapts its resolution to density automatically — solving §1.2's Limit 3 (10,000× skew) structurally, with no level-tuning decision (§2.3) at all: every query, urban or rural, touches O(log N) nodes and a bounded number of points.

Pros. Density-adaptive (its defining win); exact k-NN with clean termination; conceptually simple; fully in-memory versions are easy to build and blazing fast — which is why real dispatch systems (Yelp's search, early Uber) ran in-RAM quadtrees. Cons. It's a pointer structure, not an encoding — there's no "quadtree key" to store in Redis or shard by; it lives in one process's memory, so you must solve persistence, replication (File 08), and sharding (File 04) around it. Deep trees from pathological clustering; rebalancing under heavy movement (moving objects churn the tree — splits and merges under a write firehose need careful engineering); a crash loses the structure (rebuild from a durable point store — acceptable for ephemeral driver data, §0.3). Complexity. Insert/query O(log N) expected; memory O(N + internal nodes). When to use it. When you're building an in-memory spatial service and density skew is severe — a dispatch/matching service that owns its data in RAM and rebuilds on restart. Choose grid-encodings instead when you need the index distributed across existing storage; choose R-trees when data must live on disk with shapes.

4.4R-tree — the Disk-Native Shape Index#

What it is. The B-tree's spatial sibling and the engine inside PostGIS (Postgres's geospatial extension — the industry-standard way databases do geo, exposed via its GiST index type, a Generalized Search Tree: Postgres's pluggable framework that lets an index organize by any "containment" logic instead of by sort order). An R-tree is a balanced tree of nested MBRs (§2.4): leaves hold objects' MBRs; each internal node holds the MBR enclosing all its children.

How it works. Descend for a query by recursing into every child whose MBR intersects the query region (several may — MBRs of siblings can overlap, which is the R-tree's central engineering headache); prune the rest. Insert by choosing the child needing least MBR enlargement, splitting full nodes with heuristics that minimize overlap (the R\*-tree variant's smarter splits are the production standard). Like the B-tree, every node is one disk page (File 11 §0.3) and the tree stays balanced — hence, disk-friendly: a lookup is ~3–4 page reads.

Why it works. It generalizes "sorted + balanced + page-sized nodes" (the B-tree recipe) from one dimension to rectangles: the MBR-intersection test plays the role that key comparison plays in a B-tree.

Pros. Indexes shapes, not just points — polygons, roads, footprints, natively (nothing else in this list does); disk-resident and crash-safe with the database's own WAL (File 11); transactional with your business rows; supports the full computational-geometry query zoo (intersects, contains, within-distance) via PostGIS. Cons. Write-expensive — inserts cascade MBR adjustments and occasional node splits up the tree, so it's disqualified from the moving-object firehose (§0.3); overlapping sibling MBRs mean queries descend multiple branches (performance degrades as overlap accumulates under churn); no natural key to shard on (it's one database's index — scale-out means File 04 sharding above it, by region). Complexity. Query O(log N) page reads expected; insert O(log N) with split amplification; storage ~MBR per object. When to use it. **Static or slow-changing shape data with rich query needs inside a relational DB** — delivery-zone management, city datasets, mapping backends, anything where "does this polygon intersect that one?" matters. It is the POI-workload champion (§0.3) and the wrong tool for live drivers.

4.5Google S2 — the Sphere Done Right#

What it is. Google's cell system (open-sourced; born inside Google Maps): project the sphere onto the 6 faces of an enclosing cube (eliminating Lies 1–2 at the projection level — no poles-singularity, no antimeridian seam, near-uniform cells worldwide), then subdivide each face quadtree-style 30 times, and order all cells along a Hilbert curve (§0.4's better curve — no Z-jumps, so consecutive cell IDs are always physically adjacent). Every cell gets a 64-bit integer ID whose bit structure encodes face + Hilbert position + level.

How it works. A point → which cube face → recursively which quadrant × 30 → Hilbert-order the path → one uint64. Level 30 cells are ~1 cm²; level 13 ~1 km². The killer feature is the region covering algorithm (§2.5): hand S2 any shape on the sphere — circle, polygon, route corridor — plus a cell budget, and it returns a near-optimal multi-level covering. Parent/child relationships are bit-prefix operations on the ID (a cell's children share its prefix — the geohash trick, but on integers, on a Hilbert curve, on a sphere).

Why it works. Every flaw of geohash is addressed by construction: cube projection ≈ uniform cells everywhere (vs latitude-squashed rectangles); Hilbert ≈ strictly better locality (vs Z-jumps); 64-bit ints ≈ compact, fast, sortable keys (vs strings); sphere-native geometry ≈ correct everywhere including poles and the Pacific.

Pros. The most geometrically correct and uniform system available; industrial-strength covering algorithm (the geofencing workhorse); integer IDs slot perfectly into any KV store, Bigtable-style range scans, or shard keys (§6's geosharding is built on exactly this — Tinder, §9.2). Cons. Real library complexity (the C++ implementation is famously subtle; bindings vary in quality) — you adopt a dependency, not a technique; cells are still quadrilaterals, so neighbor distances are unequal (edge vs corner neighbors — a subtle bias for k-ring analytics, H3's opening); harder to eyeball/debug than a geohash string. Complexity. Point→cell O(level); coverings O(cells returned); all IDs 8 bytes. When to use it. When correctness-at-planet-scale or high-quality coverings matter — global products, geofencing engines, geo-sharding keys. The default choice for serious infrastructure, the moment geohash's distortions or string keys start costing you.

4.6Uber H3 — Hexagons for Analytics and Movement#

What it is. Uber's open-source cell system: tile the sphere with hexagons (via an icosahedron projection — a 20-triangle-faced solid unfolded around the globe; the geometric fine print: a perfect hexagon tiling of a sphere is mathematically impossible, so exactly 12 pentagons hide among the hexagons at the icosahedron's vertices, deliberately placed over oceans — and your code must still not crash on them). 16 resolution levels; 64-bit integer IDs.

How it works. Same shape as S2 operationally — point → cell ID at a resolution, parent/child via ID manipulation, neighbor and k-ring (all cells within k steps) functions — but the hexagon changes the geometry of neighborhood: a hexagon has 6 neighbors, all sharing an edge, all at the same center-to-center distance. Squares have 8 neighbors at two different distances (edge-touching vs corner-touching, differing by √2×).

Why hexagons matter — the actual insight. For anything that spreads or averages over space — demand heatmaps, surge pricing zones, ETA modeling, "smooth this metric over the neighborhood" — equidistant neighbors mean unbiased spatial aggregation: a k-ring around a cell is a honest approximation of a circle, and gradients between adjacent cells compare like with like. With squares, every diagonal neighbor is 41% farther, systematically distorting any neighborhood computation. Hexes are also the closest-to-circular cell shape, minimizing the over-fetch corners of §3 step D.

Pros. Best-in-class for movement analytics and spatial aggregation (its design goal — Uber built it for marketplace pricing/dispatch analytics); uniform neighbor semantics simplify ring queries; great tooling/visualization ecosystem. Cons. Hexagons don't nest — a child hex is not contained in its parent (the ~7-child "aperture-7" subdivision only approximates containment), so exact hierarchical rollups and prefix-containment tricks (geohash/S2's superpower) don't hold — aggregating up the ladder introduces boundary slop; the 12 pentagons are perpetual special-case code; coverings of arbitrary polygons are weaker than S2's. Complexity. Same order as S2; IDs 8 bytes. When to use it. Analytics, pricing, heatmaps, k-ring neighborhood logic — anywhere aggregation fairness beats exact containment. Use S2/geohash when hierarchical containment or coverings dominate. (Uber runs H3 for marketplace analytics and cell-based dispatch logic — §9.1.)

4.7Comparison Table & Decision Rule#

The decision rule, in one breath: "Under 100k points, bounding-box on Postgres and stop. Static places and polygons at scale → PostGIS R-tree. Live moving objects → cell buckets in RAM: geohash-in-Redis if you want zero new dependencies, S2 if you're building serious global infrastructure. Severe density skew inside one owned service → in-memory quadtree. Spatial analytics, surge, heatmaps → H3. Geofencing at scale → S2 coverings in a hash map. And every one of them ends with a haversine verify and a neighbor-cell check — those two are not optional anywhere."

5The Moving-Object Problem — Write-Heavy Location at Scale#

§0.3 split the workloads; this section builds the moving side properly, because it's what "design Uber" actually tests.

5.1The Write Path as a Funnel of Cheapness#

250k pings/s cannot each be precious. The design principle: make the common case nearly free and the data disposable.

5.2Expiry: TTLs as Presence#

How do you know a driver went offline? You don't — phones die mid-tunnel without sending goodbye. Presence must be inferred from silence: every ping stamps a timestamp, and a sweeper evicts entries older than a threshold (~3–4 missed pings ≈ 15 s). Two implementation notes with teeth: Redis's per-key TTL doesn't work inside a sorted set (members of a ZSET can't individually expire — a real Redis modeling gotcha), so expiry is done either by encoding the timestamp into a parallel ZSET scored by last-seen time and periodically ZREMRANGEBYSCORE-ing the stale range (cheap: one ranged delete per sweep), or by lazily filtering timestamps at query time and cleaning opportunistically. And the threshold is a product trade-off: too short → flapping drivers (one dropped packet = vanished from dispatch); too long → riders matched to ghosts. This is File 01's health-check unhealthy-threshold tuning, re-materialized as human beings in tunnels.

5.3Freshness, Consistency, and What "Correct" Even Means#

The moving-object store is eventually consistent with reality itself, and no engineering fixes that — the driver moved after the ping left the phone. So correctness gets redefined: not "the returned positions are true" but "the match made from them survives verification." Hence the two-phase dispatch shape: geo-query generates candidates from seconds-old data (cheap, approximate); the offer to a specific driver re-verifies (is the driver still there-ish, still available, still reachable?) at send time, with the driver's acceptance as the final commit. Failures fall through to the next candidate. It's File 14's funnel (cheap-approximate retrieve → expensive-exact verify) with the twist that here the ground truth is a person in traffic. The interview sentence: "location data is a stale hint by physics; design the matching protocol so staleness costs a retry, never a wrong bill."

6Geo-Sharding, Hot Cells & Matching#

6.1Sharding the World#

One Redis/one quadtree eventually can't hold a planet of drivers or POIs, so you shard (File 04) — but geospatial sharding inverts File 06's instinct. Consistent hashing spreads keys randomly to balance load; geo data must do the opposite: keys that are spatially close must land on the same shard, or every 9-cell query (§3) becomes a scatter-gather across machines (File 13's tax, self-inflicted). So the shard key is the region: city_id, or a coarse cell (S2 level-6, geohash-3). Queries route to one shard (plus, unavoidably, cross-shard neighbor checks for queries near a shard's own border — the boundary problem now exists at the shard level too, and the standard fix is the same: shard boundaries get queried on both sides, or shards overlap slightly along their edges).

6.2The Hot-Cell / Hot-Shard Problem#

File 04's whale, wearing a city: Manhattan's shard carries 10,000× Wyoming's load, and the skew moves (stadium letout, airport at 5 am, New Year's midnight everywhere sequentially). Mitigations, in escalating order: size shards by load, not area (one shard = Manhattan; one shard = the entire Mountain West); split hot shards dynamically — this is where adaptive structures shine, and Tinder's production answer (§9.2) is literally "run the S2-cell → shard mapping through a load balancer of geography, re-splitting when a cell's query volume crosses a threshold" (File 04 §5.2's many-logical-partitions-few-nodes pattern, with S2 cells as the logical partitions); replicate hot read cells (a celebrity place is read-hot, not write-hot — File 02's answer, cache it); and degrade the product before the platform — in a melting cell, widen ping intervals, coarsen the search level, cap k. Skew is the permanent weather of geo systems; the design question is never "how do we eliminate it" but "what bends first."

6.3From Query to Match (dispatch, briefly but honestly)#

"Nearest driver" is candidate generation; dispatch is an assignment problem on top: matching sets of riders to sets of drivers, optimizing ETA/fairness/utilization globally rather than greedily (greedy nearest-match strands the second rider when one driver was the best for both — batching requests for a few hundred milliseconds and solving the small assignment problem produces measurably better marketplace outcomes; Uber has published exactly this evolution). The geo index's role in that machine: generate each request's candidate set fast, with road-ETA re-ranking (§2.2) replacing straight-line distance before the optimizer runs, because a driver across the river is straight-line-near and ETA-far. Scope note (Rule 2b): the optimizer itself — bipartite assignment, auction algorithms — is operations research beyond this bible; the system design takeaway is the funnel: cells → haversine → ETA → batched assignment → offer/accept as commit.

7Pros, Cons & Trade-offs#

Benefits (with the WHY for each)#

Milliseconds instead of scans, exactly. Cell/tree indexes cut "near me" from O(N) to O(cells + candidates) — and unlike File 14's high-dimensional cousin, 2-D proximity is exactly solvable: no silent recall loss, no approximation anxiety. Two dimensions is a gift; the entire structure zoo exists to unwrap it.

One primitive, many products. Radius search, k-NN, geofencing, heatmaps, geo-sharding keys — all reduce to cell IDs plus three algorithms (neighbors, coverings, expanding rings). Mastering one cell system (S2 or H3 or geohash) gives you the whole LBS product space.

It runs on infrastructure you already have. The encoding trick's deepest virtue (§4.2): geohash/S2 IDs are ordinary keys, so Redis, Postgres, DynamoDB, Elasticsearch, and Kafka partitioning all become geo-capable without new databases. Compare the vector world (File 14), which needed purpose-built engines.

Ephemerality is a feature. Moving-object stores self-heal (repopulate in one ping interval), tolerate loss, and shed load by downsampling — a rare workload where the CAP anxieties of File 08 mostly dissolve, because the ground truth re-announces itself every 4 seconds.

Costs & Trade-offs (be rigorous)#

The boundary problem is forever. Every curve/grid index requires neighbor-checking at query time and both-sides handling at shard borders; every geofence covering leaks at edges. Mitigation: neighbor queries always (never optional), Hilbert over Z where locality is money, verify-phase haversine as the universal cleanup. The bugs ship when someone "optimizes away" the neighbor fetch.

Cell geometry is approximation. Circles become squarish blobs (over-fetch), hex parents don't contain children (rollup slop), coverings over/under-shoot polygons. Mitigation: two-phase filter-verify everywhere; budgeted coverings sized to the precision the product actually needs — precision is a line item, spend it consciously.

Skew is the workload. Density and demand vary 10,000× and migrate hourly; a design validated on uniform data is unvalidated. Mitigation: adaptive structures or load-based shard splitting (§6.2), plus product-level degradation plans for the melting cell.

Freshness is bounded by physics and battery. Faster pings = fresher matching = dead phones and cellular cost; the interval is a three-way product negotiation (freshness vs battery vs load), not an engineering constant. Mitigation: adaptive ping rates (fast when on-trip or in dense demand, slow when idle) — the mobile fleet is a sensor network you must budget.

Spherical math will humiliate flat-Earth code. Degree arithmetic, antimeridian wraps, pole behavior, unstable trig for tiny distances — each a production incident with a postmortem. Mitigation: use the libraries (S2/H3/PostGIS); never hand-roll the sphere.

The senior rule: Separate the ephemeral location plane (RAM cells, TTLs, eventual, disposable) from the durable business plane (trips, billing, File 15's idempotent ledger), pick the cell system by workload — geohash to piggyback, S2 for correctness and coverings, H3 for aggregation, R-tree for shapes, quadtree for owned-RAM skew — and never skip the two universal steps: query the neighbors, verify with haversine.

8Interview Diagnostic Framework (Symptom → Solution)#

9Real-World Engineering Scenarios#

9.1Uber — H3, Ringpop, and the Dispatch Funnel#

Uber built and open-sourced H3 (§4.6) and has published extensively on its dispatch platform's evolution.

9.2Tinder — Geosharding Recommendations with S2#

Tinder's engineering team published a detailed series on rebuilding their recommendation system around geosharding, because dating discovery is inherently a radius query ("people within X km").

9.3Lyft — S2 Coverings for Geofences at Fleet Scale#

Lyft's engineering blog describes their geofence service — thousands of operational polygons (airport queues, venue pickup zones, pricing regions, regulatory boundaries), tested against every driver location update.

10Interview Gotchas & Failure Modes#

Classic Questions (and the crisp answers)#

"Why can't a regular B-tree index handle 'near me'?" A B-tree imposes one total order; no ordering of 2-D points keeps all spatial neighbors adjacent in it. A lat index gives you a planet-wide strip; intersecting lat and lon indexes materializes two huge strips to find a tiny box. The fix is either folding 2-D into locality-preserving 1-D (space-filling curves → geohash/S2) or natively 2-D trees (quadtree/R-tree). Bonus: contrast File 14 — at 768-D proximity is only approximately indexable; at 2-D it's exactly solvable, which is why this field has correct answers and that one has recall curves.

"What's a geohash, actually?" Bit-interleaved lat/lon (a Z-order/Morton code) chopped into base-32 characters — so a shared prefix guarantees a shared region, and spatial search becomes prefix range-scans on any ordinary sorted index. Flaws by construction: Z-curve boundary jumps (hence the mandatory 8-neighbor query), latitude-distorted rectangle cells, and prefix similarity being sufficient but not necessary for proximity (points straddling the prime meridian share no prefix).

"Geohash vs S2 vs H3 — pick." Geohash: piggyback geo onto Redis/ES/SQL you already run; human-scale products. S2: sphere-correct near-uniform cells, Hilbert locality, 64-bit IDs, the best covering algorithm — serious global infra, geofencing, geoshard keys. H3: equidistant hex neighbors — unbiased k-ring aggregation for analytics/surge/heatmaps; but hexes don't nest, so containment rollups are approximate. All three end with neighbors + haversine.

"Design 'find the 10 nearest drivers.'" Write path: pings → geo-shard router → cell bucket (RAM sorted set); in-cell pings update coords only; cell-crossings move set membership; TTL sweeper infers offline. Read path: rider's cell + 8 neighbors → ~hundreds of candidates → haversine → filter status → top-10; expanding rings if short of k (terminate when ring boundary exceeds k-th distance). Then re-rank by road ETA and treat results as candidates — verify at offer, acceptance commits.

"How does geofencing scale to thousands of zones?" Precompute each zone's cell covering; invert to cell → zones map. Per ping: O(levels) hash lookups + exact point-in-polygon against the shortlist only. Ray-casting against every polygon per ping is the trap answer.

"Why did the nearest-by-distance driver take 15 minutes?" Straight-line isn't road-network reality (rivers, highways, one-ways). Haversine ranks candidates; a routing engine's ETA re-ranks the top few before offering. Distance retrieves; ETA decides.

"Where does consistency matter in this system?" Almost nowhere in the location plane — it's eventually consistent with reality itself and self-heals every ping interval. It matters totally in the business plane (trip, billing): durable, idempotent (File 15), reconciled. Naming that split is the senior answer.

Failure Modes & Mitigations#

The skipped neighbor query. Works in every demo (test points sit mid-cell), silently loses edge-adjacent matches in production — the most classic geo bug in existence. → Mitigation: neighbor fetch is part of the query API, not caller discipline; tests place points 1 m from cell borders.

Flat-Earth arithmetic. "Within 0.05 degrees" filters, unwrapped antimeridian ranges, law-of-cosines on 200 m distances. → Mitigation: ban raw degree math in review; all distance via haversine/library; test fixtures in Fiji, Svalbard, and Greenwich.

Hot cell melts a shard. Stadium empties; one cell's write+query load spikes 100×. → Mitigation: load-based shard splitting (S2 logical partitions), read-replicas for query-hot cells, product degradation ladder (coarsen level, widen ping interval, cap k) that bends before the platform breaks.

Ghost drivers / flapping presence. TTL too long → riders matched to phones dead in tunnels; too short → one dropped packet unlists a real driver. → Mitigation: threshold ≈ 3 missed pings; verify-at-offer catches ghosts; adaptive ping rates reduce both.

ZSET members don't expire. Redis TTLs are per-key; stale drivers accumulate inside GEO sets forever. → Mitigation: parallel last-seen ZSET + periodic ZREMRANGEBYSCORE, or lazy filter-and-clean at query time.

Covering leak at zone edges. Under-budgeted covering misses a sliver; drivers inside the airport zone aren't charged airport rules. → Mitigation: always over-cover then exact-verify (false positives cost CPU; false negatives cost correctness — choose CPU); alert on covering-budget saturation.

Queueing the pings. Backpressure design buffers location updates under load; the system dutifully processes 40-second-old positions. → Mitigation: freshness-critical telemetry sheds (drop-oldest / downsample), never queues — a late position is worse than none.

Cross-shard border blindness. Queries at geoshard edges return only the local side. → Mitigation: overlap shard boundaries or fan out to border-adjacent shards; keep shard granularity ≫ query radius so borders are rare.

11Whiteboard Cheat Sheet#

╔══════════════════════════════════════════════════════════════════════════════╗
║  GEOSPATIAL INDEXING & LBS — BOARD DUMP                                      ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ WHY: B-tree = ONE sort order; proximity is 2-D ⇒ lat-index returns a planet- ║
║   wide strip. Escape (possible at 2-D, unlike File 14's 768-D!):             ║
║   fold 2D→1D (space-filling curve: prefix = region) or native 2-D tree.      ║
║ SPHERE LIES: 1°lon shrinks w/ latitude (×cos lat) | world wraps at ±180 |    ║
║   shortest path = great circle. ⇒ ALL distance = HAVERSINE, never degrees.   ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ CURVES: Z-order/Morton = interleave lat/lon bits. prefix=region! but curve   ║
║   JUMPS at boundaries ⇒ ALWAYS QUERY CELL + 8 NEIGHBORS (not optional).      ║
║   Hilbert = no jumps (S2 uses it). Two workloads (ASK FIRST): static POIs    ║
║   (read-heavy, disk, R-tree) vs MOVING objects (write firehose, RAM, TTL).   ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ STRUCTURES:                                                                  ║
║  bbox+B-tree  <100k pts, v1. do this first.                                  ║
║  GEOHASH      base32 Morton string; geo inside Redis/ES/SQL you already run  ║
║               (Redis GEO = ZSET scored by 52-bit morton). latitude-distorted ║
║  QUADTREE     split-on-density in-RAM tree; ADAPTIVE (skew!); not shardable  ║
║  R-TREE       nested MBRs, disk pages, PostGIS/GiST; SHAPES; write-expensive ║
║  S2           sphere→cube→Hilbert, 64-bit IDs, 30 levels; BEST coverings;    ║
║               planet-correct. geoshard keys (Tinder).                        ║
║  H3           hexagons (+12 pentagons!); 6 EQUIDISTANT neighbors ⇒ unbiased  ║
║               k-ring aggregation (surge/heatmaps); hexes DON'T nest.         ║
║ DECIDE: piggyback→geohash | global infra/geofence→S2 | analytics→H3 |        ║
║         shapes→R-tree | owned-RAM+skew→quadtree | tiny→bbox.                 ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ QUERY: cell+8 ─► candidates ─► HAVERSINE (square→circle) ─► filter ─► top-k  ║
║   k-NN: EXPANDING RINGS; stop when ring boundary > k-th distance.            ║
║   then ROAD-ETA re-rank top few (river problem). distance retrieves,         ║
║   ETA decides, driver ACCEPTANCE commits (geo result = candidate, not truth).║
║ GEOFENCE: polygon → S2 COVERING → invert map cell→zones → ping = O(levels)   ║
║   hash lookups + exact verify shortlist. over-cover, then verify.            ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ MOVING OBJECTS: ping ~4s. 97% pings in-cell ⇒ update coords only; crossings  ║
║   move ZSET membership. NO durability (truth re-pings in 4s; crash recovery  ║
║   = wait). presence = TTL sweeper (~3 missed pings). overload ⇒ DOWNSAMPLE,  ║
║   never queue (late position < no position).                                 ║
║ SHARDING: geo = ANTI-consistent-hashing — co-locate nearby keys! shard by    ║
║   region/coarse cell; borders queried both sides. HOT CELLS move (stadium,   ║
║   rush hour): load-based splits, replicate read-hot, degrade product first.  ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ PLANES: LOCATION plane = RAM, ephemeral, eventual, disposable.               ║
║         BUSINESS plane = trips/billing: durable, IDEMPOTENT (File 15).       ║
║         Never mix them. The funnel glues them.                               ║
╚══════════════════════════════════════════════════════════════════════════════╝

12One-Sentence Summary for an Interviewer#

"Geospatial indexing exists because a B-tree's single sort order cannot express 2-D proximity — a latitude index returns a planet-wide strip — so you either fold the map into a line with a space-filling curve (interleave the coordinate bits: Morton/Z-order for geohash, the jump-free Hilbert curve for S2) so that shared prefix = shared region and any ordinary sorted store becomes spatial, or you build a natively 2-D tree (quadtree for adaptive in-RAM density, R-tree/PostGIS for disk-resident shapes); every curve index pays the boundary problem — so you always query the cell plus its neighbors and always finish with a haversine verify (degree arithmetic lies: longitude shrinks with latitude and the world wraps) — you pick geohash to piggyback on Redis/ES you already run, S2 for sphere-correct global infrastructure and its covering algorithm (which turns geofencing into a cell → zones hash lookup), H3 when equidistant hexagon neighbors make aggregation unbiased (surge, heatmaps), and for moving objects you invert every instinct: RAM cell buckets with TTL-inferred presence, no durability (the truth re-pings in 4 seconds), downsample-don't-queue under load, and geo-shard by co-locating nearby keys (the opposite of consistent hashing) while load-splitting the moving hot cells — because location is a stale hint by physics, the geo query only generates candidates: road-ETA re-ranks, the offer verifies, the driver's acceptance commits, and everything durable about the trip lives in File 15's idempotent business plane, never in the location plane."

End of File 16. Next → File 17: Distributed Unique ID Generation (UUID, Snowflake, ULID — why auto-increment dies at scale, and how 64 bits encode time, machine, and sequence without coordination). Prompt me to continue.