Dynamic Segments and the Quadtree

In one line: one rule — split when a cell holds more than 500 places — resolves both failure modes of the previous lesson. The structure that results is the chapter's answer.

The rule

We solve the problem of uneven distribution of places in a segment by dynamically sizing the segments. We do this by focusing on the number of places. We split a segment into four more segments if the number of places reaches a certain limit. We assume 500 places as our limit.

We use a QuadTree to manage our segments. Each node contains the information of a segment. If the number of places exceeds 500, we split the segment into four additional child nodes and divide the places among them. The leaf nodes will be those segments that can't be broken down any further. Each leaf node will have a list of places in it.

The rule inverts what is fixed and what varies — and that is the whole idea

Compare the two schemes on one axis:

That inversion is the entire contribution. Lesson 8 failed because query cost depends on places examined, and places examined was the uncontrolled quantity. The quadtree controls exactly that quantity and lets geography absorb the variation.

Both failure modes disappear at once, from the same rule:

Dense areas subdivide until each leaf holds at most 500. Manhattan becomes many small leaves rather than one enormous cell, so a query still examines at most 500 places per leaf.

Sparse areas never split, so a rural leaf stays large — perhaps hundreds of square miles — and a search there covers enough ground to find something without expanding across many cells.

Note that the second benefit is not a separate mechanism. It is the same rule read from the other end: not splitting is what makes sparse cells big.

Fix the quantity that drives cost, and let the quantity you do not care about vary. That is the transferable form, and it recurs throughout the course — consistent hashing's virtual nodes sized by machine capability, Kafka partitions sized by throughput rather than topic count, that building block's suggestion of segments sized by graph size rather than area.

The tree's shape is a map of population density

A quadtree built this way encodes something interesting: depth is a proxy for density.

Rural Nevada    -> a leaf at depth 4       -> huge cell, few places
Suburban        -> a leaf at depth 10
Manhattan       -> a leaf at depth 20+     -> tiny cell, still 500 places

Every level of depth quarters the area. So a leaf twenty levels down covers roughly a trillionth of its parent region — a city block — and still holds up to 500 places.

Two practical consequences.

The tree is wildly unbalanced, and that is correct. Unlike a B-tree, where imbalance is a defect to be corrected by rebalancing, imbalance here is information. Forcing it into balance would destroy exactly the adaptation that makes it work.

Traversal depth varies by location. A rural search descends four levels; an urban one descends twenty. Both are cheap — twenty pointer hops is nothing — but it means query cost is not uniform, and the deepest paths are in the busiest places. Worth knowing, not worth fixing.

Why four children rather than two or sixteen

The choice is not arbitrary, and an interviewer may probe it.

Four is the natural subdivision of two dimensions. Each split halves both latitude and longitude, giving four quadrants — NW, NE, SW, SE. It is the two-dimensional analogue of a binary tree's two children, and the reason the structure is called a quadtree.

Two children would mean splitting on one axis at a time, alternating — which is a k-d tree, a real and useful structure. It produces deeper trees with simpler nodes, and the cells are rectangles of varying aspect ratio rather than squares.

Sixteen children would mean quartering both axes at once, giving a shallower tree with fatter nodes. That is essentially what production systems like S2 and geohashes do at coarser granularity, and it trades pointer-chasing for larger nodes.

The relevant trade for this design: fewer children means deeper trees and more traversal; more children means shallower trees but coarser splits, so a cell that barely exceeds the limit is fragmented into sixteen mostly-empty children.

Four is a reasonable middle, and — more importantly — it preserves the square aspect ratio, which keeps cells compact. Compactness matters for proximity search, because a long thin cell has a large perimeter relative to its area, meaning more queries straddle its boundary and touch neighbours.

500 as the limit, and what actually sets it

It is worth reconstructing what would set it, because the number is a real tuning parameter with pressure from both sides.

Too high and you are back to Lesson 8's problem — a leaf scan is expensive, and the value stored per leaf grows.

Too low and the tree becomes deep and pointer-heavy: more internal nodes, more traversal, more nodes to update on insert, and more searches straddling boundaries because cells are small relative to a typical radius.

Two anchors are visible in the chapter itself. Lesson 8's key-value sizing noted 500 × 1,296 bytes = 0.648 MB, comfortably inside the "few MBs" a value should hold. And Lesson 4's API returns 20 places per search — so a leaf holding 500 has a good chance of satisfying a query without touching neighbours, while still being scannable in microseconds.

That second one is the better justification: the leaf capacity should comfortably exceed the typical result size, so the common query terminates in one leaf. Lesson 10's illustrations turn on exactly this — 20 cafes found in one leaf versus 6 found and a walk to neighbours.

Two questions the design now owes answers to

1. How will we map the segments?
2. How will we connect to other segments?

They are not incidental. The move to dynamic cells broke something the static scheme had for free.

With fixed 5×5 squares, both were arithmetic. A coordinate's cell was a division; a cell's neighbour was an index offset. No structure needed.

With a quadtree, neither works. Cells are of different sizes at different depths, so you cannot compute which one contains a point without descending the tree, and the cell adjacent to a leaf may be at a completely different depth — a tiny Manhattan leaf may border a large one across the river.

So the design must supply:

• Mapping — descend from the root, comparing against boundaries, until a leaf. That is Lesson 10's search.
• Connection — an explicit structure linking neighbouring leaves, since adjacency is no longer computable. That is Lesson 10's doubly linked list.

Adaptive structures buy you balance and cost you arithmetic. Anything that was computable from a regular grid now has to be stored and maintained. That is the price of the quadtree, and it is worth naming as a trade rather than presenting the structure as free.

Next: searching the tree, and the linked list that makes neighbours reachable.