Static Segments

In one line: this is the design that almost works. Understanding precisely where it breaks is what makes the quadtree feel inevitable rather than arbitrary.

The scheme

Each segment will be of the size 5 × 5 miles and will contain a list of places that exist within it. We only search a few segments to find nearby destinations. We can use a given location and a defined radius to find all nearby segments and identify nearby sites.

Each segment is defined by four corner coordinates, and holds the list of places within it.

Why this converts the hard query into an easy one

Recall Lesson 7's problem: two-dimensional proximity cannot be served by one-dimensional indexes.

Segments solve it by discretizing space. A coordinate maps to a segment ID by simple comparison against boundaries — pure arithmetic, no index lookup at all. And once you have segment IDs, the query becomes:

BEFORE:  WHERE lat BETWEEN ... AND long BETWEEN ...   <- 2-D range, no good index
AFTER:   WHERE segment_ID IN (12, 13, 18, 19)         <- 1-D equality, trivially indexed

The two-dimensional problem has been moved out of the database and into arithmetic. The database now does what databases are good at: exact-match lookups on a discrete key.

That is the general technique behind every spatial index, and it is worth stating in this compact form: make space discrete, then index the discrete labels. Quadtrees, geohashes, and S2 cells differ only in how they choose the labels — the essential move is identical.

The key-value index

We use a key-value store for quick access to places in the segments. The key is the segment_ID, while the value contains the list of places in that segment.

We can usually store a few MBs in the value of the key-value store. If we assume each segment has 500 places, it will take 500 × 1,296 bytes = 0.648 MB, and we can easily store it as a value.

Segment IDs:  6,000,000  x 8 bytes =   0.048 GB
Place IDs:  500,000,000  x 8 bytes =   4.000 GB
                                     ----------
                                       4.048 GB

That reproduces exactly.

A radius is being used as an area — the segment count does not follow

The derivation of 6 million segments does not work.

The stated inputs are 60 million square miles of land and a radius of 10 miles. To get 6 million you must divide:

60,000,000 sq mi / 6,000,000 segments = 10 sq mi per segment

So the calculation treats "radius = 10 miles" as "segment area = 10 square miles." A radius is a length; you cannot divide an area by a length and get a count.

Worse, it contradicts the lesson's own opening, which defines segments as 5 × 5 miles = 25 square miles:

60,000,000 / 25 = 2,400,000 segments     <- consistent with 5x5 miles
60,000,000 / 10 = 6,000,000 segments     <- the published figure

So the published number is 2.5x the one the stated segment size implies.

The good news is that it barely matters, and knowing why is the useful part. Look at the storage breakdown: segment IDs are 0.048 GB of a 4.048 GB total. The index is 99% place IDs, and the place count does not depend on the segmentation at all.

2.4M segments:  0.019 + 4.000 = 4.019 GB
6.0M segments:  0.048 + 4.000 = 4.048 GB

A 150% error in the segment count moves the total by 0.7%.

That is worth internalizing as an estimation habit: find which term dominates before worrying about the others. Here the dominant term is fixed by the number of places, so the segmentation error is immaterial to the conclusion — even though it is a genuine dimensional confusion and should be corrected if raised.

Searching across segments

A user may select a radius to search for places that aren't in a single segment. So, we need to combine multiple segments to find locations within the specified radius — say, 5 miles.

First, we constrain the number of segments. This reduces the graph size and enables the search process to be optimized. Then, we identify all relevant locations, compute the distance to the search point, and display it to the user.

        +----+----+----+
        |  1 |  2 |  3 |
        +----+----+----+
        |  4 |  M |  6 |     M = the user's segment, (X,Y) = search point
        +----+----+----+     radius 5 miles reaches into neighbours
        |  7 |  8 |  9 |
        +----+----+----+

The two-phase pattern again, now over cells instead of coordinates

Notice the shape of the procedure: constrain the segments, then compute exact distances within them.

That is Lesson 7's coarse-then-fine filter, one level up. There it was a bounding box over coordinates refined by exact distance. Here it is a set of cells refined by exact distance.

COARSE:  which cells does the radius touch?   -> arithmetic on boundaries
FINE:    exact distance for places in them    -> haversine per candidate

The coarse phase is cheap because it works on cell boundaries rather than points, and it is conservative — it may include cells whose corner is inside the radius but which hold no qualifying places. That over-inclusion is fine; missing a cell would not be.

Every efficient spatial search in production has this shape. The index narrows to a candidate set that is orders of magnitude smaller than the corpus but still a superset of the answer, and exact geometry finishes the job. The index never has to be exact — only cheap and never under-inclusive.

Where it breaks

Can you identify a problem with the current approach?

Our locations are not evenly distributed across segments, and this approach may still take a long time to run on segments with a lot of places. For example, in a city like New York, we can have lots of places even within a small radius because it is a densely-populated area. And for less populated areas, the same radius might not have enough places, and we might need to expand our radius to find more.

Fixed geometry fails at both ends of the density distribution simultaneously

This is the pivot of the chapter, and it is worth stating more sharply than the design does.

The scheme fixes the area of a cell and lets the number of places vary. Since place density varies by orders of magnitude across the planet, the thing that determines query cost — how many places you must examine — is the thing left uncontrolled.

Dense cells are slow. A 5×5-mile square in Manhattan may hold tens of thousands of places. The index narrowed 500 million to tens of thousands, which is progress, but a query still scans a large list, and the estimate's assumption of 500 places per segment is off by two orders of magnitude there. The 0.648 MB value becomes tens of megabytes — beyond the "few MBs" the key-value store was sized for.

Sparse cells are empty. A cell in rural Nevada may hold three places. The user's radius covers it and finds nothing, so the search must expand into neighbours, and again, and again. A query that should touch one cell touches dozens.

So the same fixed geometry produces slow queries in cities and expensive expansion in the countryside. There is no cell size that fixes both — shrink them and rural searches expand further, grow them and urban cells get worse.

The insight is the one Lesson 1 anticipated: the scheme partitions space when the cost is driven by data. Query cost depends on places examined, so the partition should be sized in places.

Compare how the same tension resolved differently in that building block. There, non-uniform segments were noted as a refinement — uniform squares mostly worked because a road graph fits in memory even in a city. Here uneven density is fatal, because places cluster far more extremely than roads and the whole point of the index is to bound the candidate count.

When the quantity that drives cost is not the quantity you partitioned on, the partition will fail at the extremes of the distribution. That is the general lesson, and the fix is to partition on the cost-driving quantity — which is exactly what a quadtree does.

The choice turns on write frequency and clustering. Businesses cluster hard into cities and change rarely, which favours the quadtree — it adapts cell size to density, and the rebalancing cost it carries barely matters when inserts are infrequent. Geohash wins when you want prefix range scans in an ordinary key-value store without maintaining a tree.

Next: sizing cells by data instead of by geography.