Searching the QuadTree

In one line: the search algorithm is short, but the neighbour-traversal problem it exposes is where the structure earns its complexity.

Descending to the leaf

We start at the root node and continue visiting nodes to find the desired segment. We check every node to see if it has more child nodes. If a node has no more children, then we stop our search because that node is the required one.

The descent is cheap, and it is worth saying why

Each step is a comparison of the query point against the node's boundaries, choosing one of four children. No search, no index lookup — a constant amount of work per level.

Depth is roughly logarithmic in the local place density. Even Manhattan's deepest cells are perhaps twenty levels down, so a descent is about twenty comparisons and twenty pointer dereferences on an in-memory structure.

Put that against Lesson 7's alternative — scanning a latitude band containing millions of rows — and the improvement is not incremental. The index turned a data-proportional scan into a depth-proportional walk, and depth grows with the logarithm of density rather than with the number of places.

That is the payoff for everything in Lesson 9. And it is why the whole 12 GB tree is kept in memory on a server: a descent that touches disk twenty times would give most of it back.

When one leaf is not enough

We also connect each child node to its neighbors using a doubly linked list. All child nodes of all parent nodes are connected via a doubly linked list. This list allows us to find the neighboring segments when we need to move forward or backward, as per our requirements. After identifying the segments, we have the required PlaceID values, and we can search our database to find more details on them.

The design's worked scenarios:

Neighbour traversal is necessary because two different things can run short

It is worth being precise about why a leaf can fail to satisfy a query, because there are two independent reasons and they behave differently.

The radius exceeds the cell. In a sparse area a leaf might cover 50 square miles, but in Manhattan a leaf might be a single block. A 5-mile radius there spans hundreds of leaves. This is a geometric necessity, not a shortfall — you must visit every leaf the circle touches.

The category filter thins the results. Recall from Lesson 4 that the quadtree stores only PlaceID, latitude, and longitude — no category. So a leaf holding 500 places might hold only 6 cafes. The design's second scenario is exactly this case.

The second is more interesting because it is a consequence of the index design, not of geometry. The tree is partitioned by location alone, so any additional predicate reduces the yield unpredictably. A search for "restaurants" might be satisfied by one leaf; a search for "vegan Ethiopian restaurants" might walk through fifty.

That is a real cost, and it is the price of a single tree serving all categories. The alternatives are both worse in this design's context:

• One quadtree per category — bounded yield per leaf, but multiplies memory and insert cost by the number of categories, and rare categories produce absurdly sparse trees.
• Store category in the tree — lets you filter during the scan rather than after, avoiding a database round trip for non-matches, but does not change how many leaves you must visit.

The second is a cheap improvement the design does not make, and worth suggesting.

A doubly linked list over leaves is a one-dimensional structure over a two-dimensional space

Here is a genuine weakness the design does not flag.

Leaves are linked "just like in a doubly-linked list", so each leaf has a previous and a next. But a cell in a plane has neighbours in eight directions — four edges and four corners.

A linked list can only give you an ordering, and any ordering of a two-dimensional space fails to preserve some adjacencies. Two cells that are neighbours on the map can be far apart in the list.

On the map:            In the list:
  +---+---+---+
  | A | B | C |          A - B - C - D - E - F - ...
  +---+---+---+
  | D | E | F |          A and D are neighbours on the map
  +---+---+---+          but three hops apart in the list

This is Lesson 7's problem returning in a new place: one-dimensional ordering cannot preserve two-dimensional proximity.

The list is not useless — traversal orders like the Z-order or Hilbert curve preserve locality reasonably well, and a Hilbert ordering keeps most map-neighbours close in sequence. Production systems use exactly this: S2 cell IDs are a Hilbert-curve ordering of the sphere, which is what lets a range scan over IDs approximate a spatial region.

But the design describes a plain doubly linked list with no ordering specified, and "move forward or backward" suggests a simple sequence. For a radius search you need all neighbours, not the previous and next one.

So the honest reading is that the linked list is a simplification. A real implementation stores explicit neighbour pointers per direction, or uses a locality-preserving ordering, or does what the next callout describes.

Two passes, and the order of the filters

A geospatial index returns candidates from cells, not a circle — so the raw result includes places inside the covering cells but outside the requested radius.

Second-pass filtering is the step that makes the answer correct: compute the true distance with the haversine formula for each candidate and discard the ones outside the radius. The index narrows; arithmetic finalizes.

The order matters, and the rule is to apply the most restrictive filter first. Distance almost always eliminates the most, so it goes first and every later filter runs over a much smaller set. Filtering by category first would mean computing distances for every coffee shop on the continent.

The alternative: parent pointers

Is there an alternative approach to find the neighboring segments?

We can use the pointers of parent nodes. In each node, we can keep a pointer that points towards the parent node. Every parent node has pointers to its children, so we can use those to find the adjacent leaf nodes. We can extend our search by going up through the parent pointers.

Node F can find its neighboring node G by first going to the parent node B, and then to G.

        B
      / | \ \
     F  G  H  I        F -> up to B -> down to G

Stored adjacency versus computed adjacency — the classic trade

The two approaches are a clean instance of a trade that appears everywhere.

The last row is the decisive one and the design does not mention it.

When a leaf splits into four (Lesson 13), a stored neighbour list must be repaired: the old leaf's neighbours must now point at whichever of the four children borders them, which requires knowing the geometry of each neighbour. With parent pointers, splitting changes nothing — adjacency is derived from the tree's structure, and the structure updates itself.

Stored adjacency is faster to read and harder to maintain. Computed adjacency is slower to read and free to maintain. Given that this system does five inserts a day against 60 million searches, the read-optimized choice is defensible — but it should be chosen knowingly, and the design presents parent pointers merely as "an alternative."

There is a wrinkle worth noting: parent-pointer traversal is only straightforward when the neighbour shares a parent. Node F finding G is easy because both are children of B. Finding a neighbour across a parent boundary means walking further up and back down, and if the neighbouring region is at a different depth, you may arrive at an internal node and have to descend to several leaves — because one large leaf can border many small ones.

The tree returns IDs — the database returns everything else

After identifying the segments, we have the required PlaceID values, and we can search our database to find more details on them.

Worth making explicit as a two-stage retrieval:

QUADTREE:  (X, Y, radius) -> a set of PlaceIDs        <- in memory, microseconds
DATABASE:  PlaceIDs       -> names, ratings, photos   <- one batched lookup

The tree is an index, not a store. It holds the minimum needed to answer "which" — ID, latitude, longitude, and (from Lesson 13) rating — and nothing needed to answer "what."

That is why it fits in 12 GB and can live in memory. Storing names and descriptions in it would take it to hundreds of gigabytes and defeat the purpose.

It also means the second stage should be one batched query for all candidate IDs rather than one query per place. With 20 results that is the difference between one round trip and twenty — and per Lesson 6, this all happens under a scatter-gather across several quadtree servers, so the round trips multiply if you are careless.

Next: what the tree costs to store.