Quadtrees

Geohash gave us something lovely: a location becomes a string, "near" becomes "shares a prefix," and a plain B-tree indexes the world. But we left it with one real flaw, and it's the same flaw that sank the uniform grid two lessons ago: the grid is fixed. Every cell is the same size everywhere. So a 6-character geohash cell over Times Square and a 6-character cell over the open Pacific get the exact same resolution — even though one holds tens of thousands of points and the other holds none. We measured that skew: on realistic data, a single fixed cell can hold 31,879 points while the average holds 8. Fixed precision can't win, because real data is never spread out evenly.

So here's the fix, and it's the obvious one once you say it out loud: stop using the same resolution everywhere. Split a cell into smaller cells only where it actually gets crowded. Leave the empty ocean as one big cell; carve downtown into tiny ones. Let the grid adapt to the data instead of forcing the data into a fixed grid.

That single idea is the quadtree, and it does exactly this: it starts as one big square and, wherever a square fills up with too many points, it splits that square into four smaller ones — over and over, but only where needed. The result is a grid that's fine-grained exactly where the points pile up and coarse where they don't. Here's the same lumpy data under a fixed grid and under a quadtree, side by side — watch where each one spends its resolution.

A quadtree is a tree where every node is a square region of the map. It has one tuning knob, the capacity — the most points a single square is allowed to hold before it must split (say, 4). From there, the whole structure follows from a single rule for inserting a point:

1. Descend from the root to the leaf square that contains the point, and drop it in.
2. If that leaf now holds more than capacity points, split it into four equal quadrants — northwest, northeast, southwest, southeast (NW, NE, SW, SE) — and hand each of its points down into whichever quadrant contains it. (A quadrant that's still over capacity just splits again — the rule recurses.)

There's one honest catch in that recursion: if a pile of points sit at nearly the same spot, splitting can't separate them — they all fall into the same child, which overflows and splits again, forever. So real implementations add a maximum depth: past some level, a leaf is simply allowed to hold a few extra points rather than split into oblivion. It's a small guard, but forgetting it is a classic way to blow up a quadtree on clustered data.

That's the entire structure. A leaf holds up to capacity points; an internal node holds nothing but four children. When you split at the square's geometric center like this — subdividing space rather than pivoting on a data point — it's called a point-region or PR quadtree, and it's the standard for indexing points. (You'll also hear of point quadtrees, which split at a data point, and region quadtrees, which carve up images pixel by pixel; the PR quadtree is the one you want for location data.)

Notice what this rule buys you: a cell can never end up holding thousands of points, because the instant it exceeds capacity it splits. The overcrowded-cell problem is impossible by construction. Watch one split happen — a full cell takes one more point and cleaves into four.

Play that split rule forward over a whole city's worth of points and a beautiful property emerges: the depth of the tree at any spot tracks how dense the data is there. Dense neighborhoods trigger split after split, so the tree runs deep and the cells get tiny; empty stretches never overflow, so they stay a single shallow cell. The tree literally molds itself to the shape of the data.

The numbers make it concrete. Take the same 200,000 points we used for the density-skew demo — most of them piled into a handful of cities — and build a PR quadtree with capacity 8. Over a city center the tree is 11 levels deep; over an empty corner it's only 7. And the headline: where the fixed grid had one hot cell crammed with 31,879 points, the quadtree's deepest, busiest leaf holds at most 8 — because that's the capacity, and anything more would have split. The whole structure came to about 75,000 nodes, spent overwhelmingly on the dense regions where the resolution actually matters. No cell is ever overwhelmed; no empty space is ever paid for.

This is the payoff geohash couldn't give you: resolution that follows the data. The best way to feel it is to build one yourself — drop points, cluster them, and watch the grid carve itself deep under your clusters while the emptiness stays a single lazy square.

An adaptive grid would be useless if you still had to scan it all — so here's the other half of why the quadtree is fast. To answer "what's in this box?" (a range query) or "what's within 2 km?" (a radius query), you walk the tree from the root with one question at each node: does this square even touch my query region? If it doesn't, you prune the entire subtree — skip it and everything beneath it, instantly. If it does, you recurse into its four children and repeat. Only at the leaves you actually reach do you test individual points.

Because most of the tree is nowhere near your query, most of it gets pruned in a single comparison. On that 200,000-point tree, a range query over a busy city block examined just 9,285 points — 4.64% of the data — and skipped 110 whole subtrees with one "doesn't intersect" check each. Even aimed at the densest part of the map, it touched under 5% of the points; a naive scan would have measured all 200,000. Nearest-neighbor works the same way, walking the closest squares first (a best-first search) so it can stop as soon as no unopened square could possibly hold anything nearer.

The capacity knob from earlier quietly tunes all of this. Set it too low and you get a bloated tree of near-empty nodes — capacity 1 blew the same data up to 578,000 nodes, versus about 8,400 at capacity 64 — a 69× difference in memory and pointer-chasing, while the number of points actually examined per query barely moved. Set it too high and each leaf becomes a mini brute-force scan. The sweet spot for point data is small — usually around 4 to 16 — balancing a tree that's cheap to store against leaves that are cheap to search.

So the quadtree beats geohash on the one thing geohash was bad at — density — and it handles range and nearest-neighbor queries with clean pruning. Does that make it strictly better? No. It buys adaptivity with a very real cost, and the honest comparison is the thing worth carrying out of this lesson:

• Geohash is a string. That sounds trivial and it's actually its superpower. A string drops into any database as an indexed column, into Redis as a sorted-set score, into Elasticsearch as a bucket key. It shards across machines by prefix without a second thought. It's stateless and dead simple. Its weakness is the fixed grid.
• A quadtree is a tree of pointers. That's what lets it adapt to density and prune queries — but a tree of pointers lives in memory, on one machine. Distributing it across a cluster is real work. And when points move — which, for drivers and players, is constantly — every move can force a leaf to split or a nearly-empty one to want to merge, so a high-churn workload keeps re-shaping the tree.

That trade decides which you reach for. Geohash when you want simplicity, a stateless string, and effortless distribution — caching, sharding, "good enough" proximity. Quadtree when your data is wildly uneven and your queries are rich (range, nearest-neighbor, region analytics) and it all fits on a machine or a shard. And the largest systems refuse to choose: they run several indexes at once — Uber, for instance, uses a hexagonal grid for city-wide analytics and surge pricing and a separate real-time structure for dispatch. Quadtrees also live far outside maps: game engines use them for broad-phase collision detection and view culling (in 3-D they reach for the quadtree's cousin, the octree, which splits a cube into eight children instead of a square into four), image codecs use region quadtrees to compress flat areas coarsely, and map tilers address tiles with quadtree paths (Bing's quadkey is literally a base-4 quadtree address — a close cousin of the geohash string).

One thing the quadtree still assumes, though: that everything is a point. Ask it to index a highway, a lake, or a delivery zone — objects with real extent that don't sit at a single coordinate — and its "which quadrant is this in?" question stumbles, because the thing straddles quadrant boundaries. Fixing that is the next structure.

• ⭐ A quadtree is an adaptive grid: a square splits into four quadrants only when it overflows its capacity. So the tree grows deep where points are dense and stays shallow where they're sparse — depth tracks density. It's the direct fix for geohash's fixed grid.
• ⭐ No cell is ever overwhelmed. Every leaf holds at most capacity points by construction — where a fixed grid had a hot cell of 31,879, the quadtree's busiest leaf held 8. Empty space stays one cheap node.
• ⭐ Queries prune. Range and nearest-neighbor searches skip any square that doesn't intersect the query — one measured range query examined just 4.64% of the points. The capacity knob trades tree size against per-leaf scan (too small → a 578,000-node tree; sweet spot ≈ 4–16).
• ⭐⭐ The trade vs geohash is the lesson. Geohash = a simple string that runs anywhere and shards trivially, but fixed precision. Quadtree = an adaptive tree of pointers, great for skewed data and rich queries, but it lives in memory and re-shapes itself as points move. Simplicity vs adaptivity — the biggest systems run both.
• Quadtrees are everywhere: games (collision, culling), GIS and map tiling, image compression.

The quadtree adapts beautifully to where the points are — but it still thinks in points. The moment you need to index things with actual size and shape — roads, rivers, rectangles, regions that overlap and straddle boundaries — the neat quadrant split breaks down. The next structure keeps the adaptive-tree idea but rebuilds it around bounding boxes instead of points, so it can index anything with extent. That's the R-tree.