Geospatial Search: The Problem

Open a ride app and it finds the drivers closest to you. Open a map and search "coffee" and it ranks the nearest cafés. A delivery app watches whether the courier has crossed into your neighborhood; a dating app shows people within five miles; a game shows players near your location. Underneath every one of these is the same request, asked billions of times a day: given a point, find the things near it.

It sounds like the easiest query in the world — just find the close ones. It is, in fact, one of the most deceptively hard queries in all of systems, and When Ordinary Indexes Fail told you the first reason why: a location is two numbers at once — latitude and longitude — and a B-tree can only sort by one. "Find restaurants near me" is the 2-D box query that has no single order to slice.

But that was only the surface. Before you can build a spatial index, you have to see the whole problem clearly, because "near me" is not one hard question — it's three hard questions stacked on top of each other. What does "near" even mean on a round planet? Which shape of "near" are you actually asking for? And how do you answer it at the scale of millions of moving points without looking at all of them? Get all three in view and the next four lessons — geohashes, quadtrees, R-trees, S2 and H3 — stop looking like a grab-bag of tricks and start looking like different answers to the same spec.

Start with the question that sounds too obvious to ask: how far apart are two points on the Earth? Your first instinct — the one every naive implementation reaches for — is to treat latitude and longitude like x and y on graph paper and use the straight-line (Euclidean) distance: √(Δlat² + Δlng²). It's fast, it's simple, and it's wrong — wrong in a way that quietly returns the wrong "nearest" result.

Here's the catch. The Earth is a sphere, and latitude/longitude is not a flat, uniform grid painted on it. A degree of latitude is about 111 km — everywhere. But a degree of longitude is 111 km only at the equator, and it shrinks as you move toward the poles, all the way to zero at the pole itself, where every line of longitude meets at a single point. The lines of longitude are not parallel; they pinch together. Precisely, a degree of longitude spans 111.32 km × cos(latitude). In London (latitude 51.5°), a degree of longitude is only about 69 km — the same one-degree step is worth 111 km north-south but 69 km east-west. Farther north it collapses fast: at 60° a longitude degree is 56 km (half of a latitude degree), and at 75° it's just 29 km — about a quarter.

So Euclidean distance on raw degrees silently treats an east-west degree as if it were as wide as a north-south one. Near the equator that's a small error; in London it's a ~40% distortion; near the poles it's catastrophic. And it doesn't just make the number wrong — it makes the ranking wrong. Here's a real one, computed both ways: stand near Tromsø, in northern Norway (69.65°N). One café sits 1.2° due east of you; another sits 0.5° due north. On the flat-degree metric the northern one looks obviously closer — 0.5 is less than 1.2. But measured correctly on the sphere, the eastern café is 46 km away and the northern one is 56 km. The flat metric hands you the café that's 9 km farther and calls it the nearest. A nearest-neighbor search built on the wrong metric doesn't crash; it just quietly ships users the wrong answer.

The correct measure is the great-circle distance: the length of the shortest path along the surface of the sphere — the path an airplane flies — computed with the haversine formula: a = sin²(Δφ/2) + cos φ₁·cos φ₂·sin²(Δλ/2), then d = 2R·asin(√a), with Earth's mean radius R ≈ 6,371 km. You'll never type this by hand — every language ships it in a library — but notice the cos φ terms: that's the longitude-shrink from a moment ago, baked right into the math. It's accurate to about half a percent (treating the Earth as a perfect sphere; the ellipsoidal Vincenty formula gets to a hundredth of a percent if you ever need it). Every serious geospatial system measures "near" this way. (One honest caveat we'll keep in our back pocket: great-circle distance is the crow-flies distance. "Nearest by road" or "nearest by drive-time" is a different, harder question — that's routing, not indexing. For finding candidates, crow-flies is exactly what we want.)

The lesson underneath the trigonometry: "near" is defined on a curved surface, and the flat-grid shortcut is a bug, not a simplification.

Even once you can measure distance correctly, "near me" still isn't one query. It's three — and they have genuinely different difficulty.

1 · The radius query (a circle). "Everything within 5 km of here." You're handed a center and a radius; you want every point inside that circle. This is geofencing ("is the courier inside the delivery zone?"), "drivers near me," "tweets from this area." The circle is given.

2 · The bounding-box query (a rectangle). "Everything visible on the screen right now." As you pan and zoom a map, it asks for every point inside the current rectangle — a range on latitude and a range on longitude at once. Boxes are the cheap shape: testing whether a point is inside a rectangle is just four comparisons, no trigonometry.

3 · The k-nearest-neighbors query (the k closest). "The 20 nearest available drivers." No radius, no box — just a count. And this one is genuinely nasty, because you don't know how big to make the search. Draw the circle too small and you find only 5 of the 20 you need — and worse, you have no way to know you missed some. Draw it too big and you've scanned half the city to return 20 results. The only radius guaranteed to contain your 20 neighbors is one large enough to contain everything — which is just the full scan again. To answer kNN properly you have to be able to walk outward from the query point in order of distance, stopping the moment you've collected k — and a table sorted by one column simply cannot walk outward in two dimensions. kNN, more than any other query, is what forces a real spatial structure.

One pattern ties all three together and shows up in every spatial index you're about to meet: filter, then refine. A circle is expensive to test (trigonometry per point); a box is cheap. So the index first returns a generous over-approximation — the points in a bounding box or a handful of candidate cells that surely contain the answer — and then a cheap second pass computes the exact great-circle distance on just those candidates and throws away the ones in the box's corners but outside the true circle. The index narrows the world to a few hundred candidates; the refine step finds the real answer among them. Keep that two-step shape in mind; it's the skeleton of everything that follows.

So we have three query shapes and a correct distance metric. What's wrong with just… computing it?

The naive answer: scan everything. For each query, walk all N points, compute the great-circle distance to each, and keep the close ones. It's correct, it's ten lines of code, and it's O(N) per query. How bad is linear, really? Measured on a plain machine, one nearest-point query costs about 740 nanoseconds per point — so 10,000 points takes 8 ms, 100,000 takes 74 ms, and a million takes 739 ms. For a hobby app with a few thousand pins, 8 ms is completely fine — never build a spatial index you don't need. But a ride platform tracking millions of drivers and answering thousands of "nearest" queries a second would spend three quarters of a second, per query, computing trig for points that aren't remotely close — to answer a question that should touch a few dozen. Linear-per-query is the wall. (This isn't hypothetical: Uber cared enough about exactly this to build and open-source its own hexagonal grid system, H3, to bucket the whole world into cells for dispatch and pricing — you'll meet it near the end of this track.)

The B-tree fixes from last lesson don't rescue you. You already saw why: a B-tree on latitude gives you a horizontal stripe across the whole world; intersecting a latitude stripe with a longitude stripe (the two-index trick) still reads two enormous bands to keep a sliver, and it's the slowest plan of the lot. And none of it can do kNN at all — there's no radius to turn into a range.

The tempting fix: a uniform grid. Chop the world into fixed square cells — pick any one size — and file each point into its cell. Now "near me" means look in my cell and its eight neighbors, not scan the planet. This is a real improvement, and it's the right instinct: turn a distance query into a cell lookup. But it breaks on the two facts that define real geospatial data:

• The world is not spread out evenly (density skew). Points cluster insanely. Take 200,000 points distributed like real demand — most of them piled into a handful of cities — and drop them into fixed 1°×1° cells. The result: 39% of cells are empty, and the busiest single cell holds 31,879 points while the average occupied cell holds 8 — the hot cell is 4,054× the average. With fixed cells you get the worst of both worlds: downtown, "look in your cell" is still scanning tens of thousands of points; over the ocean, you've allocated a sea of empty cells and a kNN search has to keep expanding its ring across dozens of empty neighbors before it finds anything. One cell size cannot be right for both Manhattan and Montana.

• The points move. A driver isn't a pin on a wall; they cross a cell boundary every few seconds. Every move is a delete-from-old-cell, insert-into-new-cell — a firehose of index updates that a structure has to absorb without falling over.

This is the real shape of the problem, and it's worth feeling rather than just reading. Drop yourself on a map with realistic, lumpy density, pick a query, and watch the naive scan touch every point — then turn on the grid and watch it help in the suburbs and choke in the city.

Line up everything that just went wrong, and it stops being a list of complaints and becomes a specification — the exact set of things a spatial index has to deliver. Every structure in the next four lessons is a different bet on this same checklist:

1. Measure distance correctly — on the sphere, great-circle, not the flat-grid shortcut.
2. Prune space without scanning it — turn "near" into a lookup that touches a few candidate cells or tree nodes, not N points. This is the whole game: touch little, miss nothing.
3. Adapt to non-uniform density — small buckets where points are dense, large buckets where they're sparse, so no single bucket is ever overwhelmed and empty regions cost almost nothing.
4. Serve all three query shapes — radius, bounding box, and k-nearest-neighbors, ideally with the same structure and the same filter-then-refine pass.
5. Handle the seams — the antimeridian, where longitude wraps from +180° to −180°: two points a kilometer apart can have longitudes that differ by 360, so a bounding box drawn around a cluster sitting on that line naively stretches across the entire planet. And the poles, where every line of longitude collapses to one point. Naive math breaks exactly here.
6. Survive movement — absorb constant inserts and deletes cheaply, because in the real world the points never hold still.

That's the spec. And the field has produced two broad families of answers to it, which are the map of the rest of this spatial track. One family flattens the two dimensions onto one — it threads a single curve through space so that nearby points get nearby labels, and then a plain B-tree can index the label (that's the geohash, and its more careful cousins S2 and H3). The other family builds a tree of nested regions — the quadtree splits space into finer cells where it's crowded, while the R-tree groups the data into nested bounding boxes — so either way the tree is fine-grained where points pile up and coarse where they don't. Same spec; two very different strategies. (And a reassuring note for the road: you'll rarely hand-build any of these — PostGIS, Redis, Elasticsearch, and the S2 and H3 libraries ship them tuned and tested. Knowing the spec is how you pick the right one and reason about it when it misbehaves.) We'll build them one at a time, from scratch, and hold each up against this list.

• ⭐ "Find what's near me" is three stacked problems, not one. What "near" means, which shape of "near" you're asking, and how to answer it at scale.
• ⭐ "Near" is great-circle distance on a sphere, not straight-line distance on a flat lat/lng grid. A degree of longitude shrinks toward the poles (111 km × cos(lat)); the flat shortcut silently returns the wrong "nearest." Measure with haversine.
• ⭐ Three query shapes, rising difficulty: radius (a given circle), bounding box (cheap — four comparisons), and kNN (the hard one — you don't know the radius, so you must walk outward in distance order). Answer them all with filter-then-refine: cheap over-approximation, then exact distance on the survivors.
• ⭐⭐ The naive scan is O(N) per query and dies at scale (measured: ~739 ms for one query over a million points); a uniform grid helps but shatters on density skew (a hot city cell measured at 4,054× the average) and constant movement. Real geospatial data is lumpy and alive — that's the whole difficulty.
• The complaints are the spec. A spatial index must: measure on the sphere, prune without scanning, adapt to density, serve all three query shapes, handle the antimeridian and poles, and survive movement. The next four lessons are competing implementations of exactly this list.

Two families answer the spec: flatten space onto a curve (geohash, S2, H3) or build an adaptive tree (quadtree, R-tree). We'll start with the first idea, and the cleverest, simplest version of it — Geohash — where a location becomes a short string, and "near" becomes "shares a prefix."