The Naive Search and Why It Fails

In one line: the failure of the obvious approach is what motivates everything that follows. It fails for a reason that is genuinely subtle — and the design's stated reason is not the main one.

The obvious design

We can make a table of places that have Place_ID as a unique ID and store each place in it. The longitude and latitude columns help us specify the exact location. Indexing both of these columns can help us fetch data efficiently. We can specify each location as a pair of latitude (M) and longitude (N). We can also search for a place within a given radius of R by finding all the places between the latitude M-R and M+R and the longitude N-R and N+R.

SELECT * FROM Place
WHERE  Latitude  BETWEEN M-R AND M+R
  AND  Longitude BETWEEN N-R AND N+R

This is where everyone starts, and it is worth understanding properly before discarding it.

The query is a square, not a circle — and that part is fine

A range on latitude and a range on longitude describes a bounding box, not a disc. Places in the corners are farther than R away.

That is not a real problem. The standard resolution is a two-phase filter:

1. COARSE:  the box query — cheap, index-supported, slightly over-inclusive
2. FINE:    compute true distance for the survivors, discard the corners

The box is a conservative superset of the circle, so nothing correct is lost. It is the same admissible-approximation move as that building block's aerial-distance bounding: prune with something cheap that can only over-include, then refine.

So the bounding box is not why this design fails. Something else is.

Two one-dimensional indexes cannot serve one two-dimensional query

Here is the real reason, and the design does not state it.

A B-tree index sorts on one dimension. An index on Latitude orders places from south to north; an index on Longitude orders them west to east. Neither knows anything about the other.

So when the database evaluates the query, it can:

Use the latitude index to find everything in a horizontal band circling the globe, then check longitude on each row, or
Use the longitude index to find everything in a vertical band pole to pole, then check latitude on each row.

Either way it retrieves an enormous intermediate set and discards nearly all of it. For a 5-mile radius near Seattle, the latitude band alone contains every place on Earth at Seattle's latitude — a strip through Canada, the North Atlantic, Britain, Northern Europe, Russia.

Places in the 10-mile latitude band:   millions
Places in the 10-mile longitude band:  millions
Places in the intersection:            a few hundred

The answer is tiny and both paths to it are huge. A composite index on (Latitude, Longitude) does not rescue you either — it sorts by latitude first, so a range on latitude still leaves longitude unsorted within it.

This is the fundamental limitation: one-dimensional ordering cannot preserve two-dimensional proximity. Points close on a map are not close in either coordinate's sort order.

That single sentence is the justification for every spatial index ever built — quadtrees, geohashes, R-trees, and S2 cells all exist to answer it. Their common trick is to map two dimensions into one in a way that mostly preserves locality, so that nearby points land near each other in the ordering. Quadtrees, which the rest of this chapter uses, do it by recursive subdivision.

"We can apply Dijkstra's algorithm to find the distance between two points" — no

This sentence is carried over from that building block and does not belong here.

Dijkstra's algorithm finds shortest paths in a graph. It needs vertices and weighted edges, and it answers "what is the cheapest route from A to B through this network."

There is no graph in this design. Yelp stores a set of points with coordinates. The distance between two coordinates is a closed-form calculation — one formula, no traversal:

Haversine for great-circle distance on a sphere, which is what you want for real geography.
Euclidean as an approximation, acceptable over short distances near the equator and increasingly wrong toward the poles.

The difference in cost is total. Haversine is a handful of floating-point operations per point. Dijkstra over 500 million vertices is the very problem that building block spent a chapter escaping.

The confusion is understandable — both chapters partition the globe and both diagrams look alike. But it is exactly the conflation Lesson 1 warned about: Maps is a graph problem, Yelp is a point-set problem. Proximity needs a distance formula; routing needs a path algorithm.

If you meet this in an interview, correct it plainly and briefly. Being able to say "there's no graph here, so it's haversine, not Dijkstra" demonstrates you understand why the two chapters differ rather than pattern-matching on the pictures.

The objection worth taking seriously

How efficient will our searching be when based on the table?

We can have multiple lists of places within (M-R, M+R) and (N-R, N+R). It'll be a challenge to handle concurrent requests. When queries used to fetch the places come at a high rate for different segments, the response time and performance will be affected.

Concurrency is a symptom, not the cause

The design's objection is that the design cannot handle concurrent load. That is true, but it is downstream of the real problem.

The query is slow because it scans a huge intermediate set. Concurrency makes a slow query fatal rather than merely bad — a hundred concurrent scans of millions of rows saturate any database.

Naming the cause rather than the symptom matters, because it points at a different fix. If the problem is concurrency, you reach for replicas and connection pools. If the problem is that the query touches millions of rows to return hundreds, you reach for a better index — and only the second one actually works.

The design does arrive at the right answer:

We can store all the places in a table and uniquely identify a segment by having a segment_ID. We can index each segment in the database. Now, we have limited the number of segments we need to search, so the query will be optimized and return results quickly.

That is the correct move, and note precisely what changed: instead of two range predicates over continuous coordinates, there is now one equality predicate over a discrete key. segment_ID IN (...) is exactly what a B-tree is good at.

The fix is not a faster query — it is converting a two-dimensional range query into a one-dimensional lookup. That conversion is what every technique in the rest of the chapter performs.

Key takeaway

The bounding-box approximation is fine — a cheap superset refined by exact distance, the same move as that building block's aerial bounding. What fails is that two one-dimensional indexes cannot serve one two-dimensional query: a latitude band circles the globe, a longitude band runs pole to pole, and the answer is the tiny intersection of two enormous sets. One-dimensional ordering cannot preserve two-dimensional proximity — the sentence behind every spatial index ever built. The design blames concurrency, which is a symptom; and its mention of Dijkstra is a carryover error, since there is no graph here and distance is haversine. The real fix is converting a 2-D range query into a 1-D lookup on a discrete segment key.

Before building an index, say what you would actually use

This chapter builds a quadtree from first principles, which is the right way to understand geospatial indexing. In an interview you should say out loud that production systems usually do not hand-roll one.

Postgres with PostGIS is often the strongest answer when the dataset is small, because it adds an index type rather than a system — no second store, no synchronization, no consistency lag. Elasticsearch is the answer when you also need real full-text search over names and categories, and it costs you a replication pipeline and eventual consistency between the two stores.

Naming the trade-off matters more than the choice: "I'd reach for PostGIS first since our data fits comfortably in one instance and it avoids a second source of truth; I'd move to Elasticsearch when text relevance becomes a real requirement."

Building the index yourself, as the rest of this chapter does, is what you do when you need to explain how these systems work — which is exactly what an interviewer probing on geospatial indexing is asking for.

Interview signal by level

Level	What a strong answer sounds like
L4	"We'd index latitude and longitude and query a range on both — but that gets slow at 500 million places."
L5	Names the box and the fix: "the range query gives a bounding box, which is fine as a coarse filter, but B-trees are one-dimensional so the database has to scan a whole latitude or longitude band. We need a spatial index."
Staff+	States the general principle: "one-dimensional ordering can't preserve two-dimensional proximity — the latitude band circles the globe, the longitude band runs pole to pole, and the answer is the small intersection of two huge sets. A composite index doesn't help either, since it sorts by latitude first. That's the reason quadtrees, geohashes, and S2 cells all exist: they map two dimensions to one while mostly preserving locality. The move is to turn a 2-D range predicate into a 1-D equality lookup on a discrete cell key — and I'd note distance here is haversine, not Dijkstra, because there's no graph in this problem."

Next: the first real fix — static segments.