The idea: search a few cells, not every point
A food app asks: which restaurants are within 8 of me? The simple answer checks the distance to every restaurant. With millions of them, that is far too slow. A spatial index first narrows the search to a few cells of the map, and only then checks real distances. This page shows two such indexes on the same 20 restaurants: a quadtree and a geohash.
The map is a 64 × 64 square: x is the longitude (east), y the latitude (north). Me is at (30, 44), and the search radius is r = 8.
A quadtree: split when full
A quadtree is a tree where every inner node has four children: NW, NE, SW, SE, the four quarters of its cell. The page uses a point-region quadtree with capacity 2: a leaf holds at most 2 points.
- To insert a point, walk down: at each node go to the quarter that holds it, until you reach a leaf.
- Add the point to the leaf. If the leaf now has 3 points, split it at the centre of its cell into 4 children and hand the points down.
- On the map, each split draws a blue "+" in the cell.
The 20 restaurants give 5 inner nodes and 16 leaves, of depth 2 (Demo 1: build the quadtree).
Radius query and pruning
The query walks the tree from the root. If a node's cell does not touch the search circle, no point under it can be close, so the whole subtree is skipped: it is pruned. At a leaf that touches the circle, each point's real distance is checked.
For me at (30, 44) the query visits 7 nodes, prunes 6, checks 7 of the 20 restaurants and finds 4: B, C, D and E (Demo 2: radius query). The two southern quarters are skipped in one step each.
Geohash: interleave the bits
A geohash turns a point into a short string. Take turns between longitude and latitude. Each turn halves the current range and writes one bit: 1 for the upper half, 0 for the lower half. Every 5 bits become one base32 character from 0123456789bcdefghjkmnpqrstuvwxyz (no a, i, l, o).
One character is 3 longitude bits and 2 latitude bits: the map becomes an 8 × 4 grid of cells, 8 wide and 16 tall. Each extra character makes the cell 32 times smaller: cell 'ey' is 2 × 2 (Demo 3: encode me). Points in the same cell share a prefix, so in a sorted list of geohashes they sit next to each other. A normal sorted index (a B+ tree, a sorted set) can then find a cell with one range scan.
On Earth the box is longitude −180 to 180 and latitude −90 to 90. There, 5 characters give a cell about 4.9 km wide, 6 characters about 1.2 km × 0.6 km, and 7 characters about 150 m.
The prefix query and the border problem
To search radius r, pick the longest prefix whose cell is at least r on its short side. Here that is 1 character (8 ≥ 8), and my cell is 'e'. A scan of prefix 'e' finds C and E.
But it misses B, only 3.2 away. B is at (33, 45), just across the middle line of the map, and its geohash is 'sn'. Close points do not always share a prefix: a border can split them, and at the middle line not even the first bit agrees.
The fix: scan the cell and its 8 neighbours. Because each cell is at least r wide, the circle cannot reach past them. That is 9 prefix scans: 7 candidates, and the distance check keeps B, C, D and E, the same answer as the quadtree (Demo 4: the border problem).
Dense areas: adaptive vs fixed cells
Restaurants are not spread evenly. When a food court with 6 restaurants opens near (44, 22), the quadtree splits only there: depth 2 becomes 4, and no leaf holds more than 2. The geohash grid stays the same, so cell 'm' now holds 7 restaurants while most cells are empty (Demo 5: a dense cluster). A search there checks all 7, unless it uses a longer prefix.
Quadtree vs geohash
| Quadtree | Geohash | |
|---|---|---|
| Cells | Split where points are dense | Fixed grid, 32 times smaller per character |
| Stored as | A tree of nodes | A string key in any sorted index |
| Radius query | Walk the tree, prune cells that miss the circle | 9 prefix range scans, then a distance check |
| Near a border | No problem: the walk tests real cell edges | Must add the 8 neighbour cells |
| Dense clusters | Deeper splits, leaves stay small | One cell gets crowded |
| Easy to shard or cache | Harder: the shape depends on the data | Yes: a cell's name is just a string |
Where this is used
Redis GEOADD and GEOSEARCH store a 52-bit interleaved geohash as the score of a sorted set and search the cell plus its 8 neighbours, as on this page. Elasticsearch has geohash grid aggregations, and many apps use geohash prefixes as cache or shard keys. Quadtrees (and their cousins, k-d trees and R-trees) are used in map tiles, game engines and in-memory spatial indexes. Google's S2 and Uber's H3 are newer cell systems that fix some of geohash's distortions.
See also binary search trees, the one-dimensional version of "go left or right"; the B+ tree as a database index, which serves the geohash prefix scan as a range scan; and how a Redis connection runs commands, the server behind GEOSEARCH.
For another geometry problem on points, see the convex hull with Graham scan and gift wrapping, built from cross-product orientation tests.
For the two other classic spatial indexes, see KD-tree vs R-tree: lines that split on x and y, and bounding boxes around groups of points.
The Hilbert curve is another way to put 2-D cells in one line: it visits every cell of a 2ⁿ × 2ⁿ grid once without jumping, which keeps neighbours closer together than Z-order; see Fractal Curves: Koch Snowflake, Dragon Curve, Hilbert Curve.
What the page leaves out
Real geohash works on a sphere: cells near the poles get thin, longitude wraps around at ±180°, and distances use the haversine formula, not a flat x and y. Redis uses 52 bits instead of whole characters, and real quadtrees often use larger capacities, keep points in inner nodes, or balance by area. The page also skips deletes, k-nearest-neighbour search, and R-trees, which index rectangles instead of points.