In a find-nearby-places service covering dense cities and empty oceans, how does a quadtree adapt its cells compared with a fixed-size grid?
answer
- no single cell size fits all
- four children per node
- split when a leaf overflows
- depth follows density
- whole tree fits one server
basics
~20 sA quadtree splits a region into four quadrants whenever it holds more than a set number of points, so dense areas get many small cells and sparse areas keep a few large ones, bounding the points per cell.
solid answer
~50 sA fixed grid uses one cell size everywhere, so downtown cells hold thousands of places while ocean cells hold none, and no single size suits both. A quadtree starts with one node for the whole map and **splits a node into four children when it exceeds a capacity**, say 100 places, redistributing its points. Dense areas end up deep with small leaves, sparse areas stay shallow with huge leaves, so every leaf holds a bounded number of points and query cost follows the result size rather than the map. To answer a nearby query I descend to the leaf containing the user, then collect neighbouring leaves until the radius is covered or enough results are found, and filter by exact distance. For mostly static places I typically build it in memory at startup from the database and refresh it periodically, since the tree for a few hundred million places fits comfortably on one machine.
go deeper
Recall that a quadtree divides a region into four whenever it gets too full, so busy areas end up with smaller cells.
Explain the split rule, why the tree is unbalanced by design, and how a query descends to a leaf and then gathers neighbouring leaves before filtering by distance.
Show operational judgment: estimate memory, decide rebuild versus incremental updates, cap depth for duplicate coordinates and keep servers out of rotation until the tree is built.
Weigh an in-memory tree replicated per server against cell keys in a shared sorted store, considering staleness tolerance, rebuild cost and how the choice constrains future scaling.
## The problem with one cell size A **fixed grid**, whether a plain lat/lng grid or a geohash at one precision, uses the same cell size everywhere. Real place data is extremely uneven: - A city centre can hold thousands of restaurants in a single square kilometre. - Oceans, deserts and farmland hold almost nothing. A cell size that returns a sensible number of results downtown returns nothing in the countryside, forcing many extra scans. A cell size that works in the countryside returns an enormous candidate list downtown. Any fixed size is wrong somewhere. ## How a quadtree adapts A **quadtree** is a tree in which every internal node has exactly **four children**, one per quadrant (north-west, north-east, south-west, south-east) of the node's rectangle. 1. Start with a single root node covering the whole map. 2. Insert points into the leaf whose rectangle contains them. 3. When a leaf exceeds its **capacity**, say 100 points, split it into four children and move each point into the child that contains it. 4. Repeat recursively; a child that is still over capacity splits again. The result is **density-adaptive**: dense areas become deep branches with small leaves, and sparse areas remain shallow, large leaves. Unlike a B-tree, a quadtree is **not balanced**; leaf depth varies with the data, and that is the point. ## Answering a nearby query - **Locate:** descend from the root, choosing the quadrant that contains the user, until reaching a leaf. - **Expand:** collect points from that leaf and from neighbouring leaves, found by walking up to a common ancestor and back down, until the collected area covers the requested radius or enough candidates exist. - **Filter:** compute exact distances, drop points outside the radius and sort. Because each leaf holds at most about 100 points, the work grows with the number of results needed rather than with the density of the area. ## Sizing an in-memory quadtree For a catalogue of mostly static places, a common design keeps the tree **in memory on each query server**. A rough estimate, assuming 100 million places, a capacity of 100 per leaf and 24 bytes per stored place (an 8-byte ID plus two 8-byte coordinates): | Item | Estimate | |---|---| | Leaves | at least 1 million (100 million / 100) | | Internal nodes | about a third of the leaf count, roughly 333,000 | | Point data | about 2.4 GB | | Tree structure overhead | tens of megabytes at typical node sizes | The internal-node figure follows from the tree's shape: a tree where every internal node has four children has (leaves - 1) / 3 internal nodes. Leaves are often only partly full, so the real leaf count is somewhat higher than the minimum. Either way the whole index fits in the memory of one ordinary server, so it can be **replicated** to every query server for read scaling rather than sharded. ## Keeping it current Places change slowly: openings and closures, not continuous movement. Common approaches: - **Periodic rebuild.** Rebuild the tree offline from the source of truth and swap it in; a few minutes of staleness is acceptable for place listings. - **Incremental updates.** Insert and remove points in place, guarding the tree against concurrent readers, and split or merge nodes as counts change. - **Rolling rollout.** Replace trees server by server so the fleet never rebuilds at once and capacity is not lost during startup. ## Pitfalls - **Duplicate coordinates.** Many points at the exact same position (units in one building) cannot be separated by splitting; without a **maximum depth** or minimum cell size, splitting never ends. - **Neighbour discovery.** Adjacent leaves can be at very different depths, so finding neighbours is more work than on a grid. - **Startup time.** Building from hundreds of millions of rows takes time; servers should not take traffic until the tree is ready. ## Quadtrees and sorted indexes A quadtree cell can also be named by its path from the root, two bits per level. Those path keys sort in the same Z-order as geohashes, so the same adaptive cells can be stored in an ordinary sorted index, with a prefix covering a whole subtree. That is the bridge between tree-shaped thinking and the range-scan model the rest of this topic uses.
- Why might a quadtree need a maximum depth even though splitting is driven by point count?If more points than the capacity share the exact same coordinates, such as many listings in one building, every split puts them all in the same child. Splitting would never reduce the count, so without a maximum depth or minimum cell size the tree recurses indefinitely. The fix is to cap depth and let those leaves exceed capacity.
- Can quadtree cells be served from an ordinary sorted index instead of an in-memory tree?Yes. Encode each cell as its root-to-leaf path, two bits per level, which yields a Z-order key like a geohash. Every point is stored under its cell key, a subtree becomes a key prefix, and a query becomes a set of prefix range scans. Adaptivity then lives in which prefix lengths the query chooses per region.
A quadtree is like a filing cabinet where a drawer is split into four smaller drawers only once it overflows, so busy topics get many small drawers and quiet ones keep one big drawer.
saying these in an interview costs you the question
- A quadtree keeps every leaf at the same depth like a B-tree
- A split copies all of a node's points into every child
- A fixed grid handles dense downtowns and empty oceans equally well
- One leaf always holds the complete answer to a nearby query
- A quadtree for a large catalogue cannot fit in memory