LESSON 25.2
Quadtrees, S2 and H3
Spatial indexes that adapt to density, and the global cell systems that big location platforms use. How quadtrees split and search, and what S2 and H3 add.
7 min read
Geohash uses a fixed grid, so a cell in central Tokyo can hold thousands of points while a cell in the Sahara holds none. Quadtrees adapt the grid to the data. At global scale, systems like Google's S2 and Uber's H3 provide well-behaved cells on the sphere, used as keys everywhere from databases to analytics.
Quadtrees
- Start with one square covering the area.
- Insert points. When a node holds more than a threshold (say 100), split it into four equal quadrants and push its points down.
- Repeat. Dense areas end up deep with tiny cells; empty areas stay as large leaves.
- To search a radius, walk down from the root, visiting only quadrants that intersect the search circle, and collect points from the leaves.
- Points
- 200 million businesses
- Leaf capacity~2 million leaves
- 100 points
- Memory for points~4.8 GB
- 200M × ~24 bytes (id + lat + lng)
- Internal nodessmall in comparison
- ~1/3 of leaf count
That fits on one server, so a common design keeps a read-only quadtree in memory on each search server, rebuilt periodically from the database, and scales by adding replicas. For "k nearest" queries, search outward from the leaf containing the point until k candidates are found.
Quadtrees are great for mostly static data. For points that move every few seconds, re-inserting constantly is costly; a grid or geohash in Redis is simpler.
R-trees, briefly
Databases index shapes (polygons, lines) as well as points with R-trees: each node holds bounding rectangles of its children, which may overlap. PostGIS uses R-tree-like GiST indexes, so ST_DWithin and polygon containment queries are fast inside Postgres. That's often the simplest answer when the data already lives in a database.
S2 and H3
Geohash
- Simple strings
- Prefix = containment
- Rectangles distort near the poles
- Big jumps at edges
Pick it when: Simple nearby search with off-the-shelf indexes.
S2 (Google)
- Projects Earth onto a cube, then a Hilbert curve
- 64-bit cell ids that sort with good locality
- Covers any region with a set of cells
- More complex
Pick it when: Geofences, region coverings, large-scale indexing: Google Maps, MongoDB, Foursquare.
H3 (Uber)
- Hexagons with equidistant neighbors
- Uniform rings for radius queries
- Good for aggregation and pricing zones
The Hilbert curve used by S2 has better locality than geohash's Z-order: consecutive ids are always adjacent cells, so ranges of ids map to compact regions.
Region queries
Geofencing ("alert me when a truck enters this depot area") flips the query: given a point, which shapes contain it?
- Precompute a covering of each fence: the set of S2 or H3 cells that overlap it.
- Index fences by those cell ids.
- For each location update, compute the point's cell, look up candidate fences for that cell, then run an exact point-in-polygon test.
Try it
Ride Matching HLD
Match riders to nearby drivers as positions change.