18. Geospatial Indexing
18.2 What are spatial indexes?
On the map: The grid squares. Every place gets a square name, squares can be split into smaller squares, and a place's name tells you which bigger square it's in.
In the system: A spatial index divides the Earth's surface into cells and gives each cell an ID. To find things near a point, you find the point's cell and look only at things in that cell and its neighbours. The three common families:
| Shape | Splits | Known for | |
|---|---|---|---|
| Geohash | Rectangles | Fixed grid, 32 children per level | Simple strings; used by Redis GEO, Elasticsearch |
| Quadtree | Squares | Into 4, only where crowded | Adapts to density; built in memory |
| S2 / H3 | Cube-face cells / hexagons | Fixed hierarchy | Google (S2), Uber (H3) |
18.2.1 Geohash
On the map: A square's name gets longer as you zoom in: "B" is a big district, "B4" a neighbourhood, "B4c" a few streets. Anything whose name starts with "B4" is inside B4.
In the system: A geohash turns (lat, lng) into a short string by repeatedly halving the world:
- Is the longitude in the east or west half? That's one bit.
- Is the latitude in the north or south half? Another bit.
- Keep halving, alternating longitude and latitude.
- Every 5 bits become one character from a 32-character alphabet.
Our store in central Bengaluru (12.9716, 77.5946) becomes tdr1v at 5 characters, tdr1v9 at 6 and tdr1v9q at 7.
Figure: every extra character zooms into one of 32 smaller cells. A shared prefix means the same bigger cell.
Cell sizes at Bengaluru's latitude (computed in the chapter's code):
| Characters | Cell size (approx.) |
|---|---|
| 5 | 4.8 km × 4.9 km |
| 6 | 1.2 km × 0.6 km |
| 7 | 150 m × 150 m |
Why it's popular:
- It's just a string. Store it in any database column and index it;
WHERE geohash LIKE 'tdr1v%'is a prefix range scan that a B-tree handles well. - Shared prefix = nearby (usually). Places in the same cell share a prefix.
The catch: two points 40 m apart can have completely different geohashes if a cell border falls between them. That's why you always search the neighbours too (18.3). Redis GEO commands (GEOADD, GEOSEARCH) are built on this idea: Redis stores each member in a sorted set, scored by a 52-bit geohash, and a radius search checks the centre area and the eight around it.
Memory code: "Each extra letter zooms in; a shared start means the same square."
18.2.2 Quadtree
On the map: The city centre is crowded, so its map pages are zoomed in with tiny squares. The outskirts are empty, so one page covers a huge square. The grid gets finer only where there's a lot to see.
In the system: A quadtree starts with one square covering the whole area. When a square holds more than N points (say 16), it splits into four children, and the points move down into them. Busy areas end up with many small squares; empty areas keep a few big ones.
Figure: a quadtree splits only where it's crowded.
To search, walk down from the root and skip any square that doesn't overlap your search box, then filter by exact distance. In the chapter's code, 5,000 riders end up in 580 leaf squares, none holding more than 16, and the quadtree's answer matches checking every rider by hand.
- Good: adapts to uneven density, which real cities always have.
- Costs: usually kept in memory on one server and rebuilt or updated as points move; not a simple string you can put in any database.
Memory code: "Split the square only where it's crowded."
18.2.3 S2 and H3 in brief
On the map: Two better-designed map books. One wraps the Earth in a cube and draws a grid on each face, so squares don't stretch near the poles. The other uses hexagons, like a honeycomb, so every neighbour is the same distance away.
In the system:
- S2 (from Google): projects the Earth onto the six faces of a cube, then divides each face into a hierarchy of cells, levels 0 to 30. The smallest cells are about a centimetre across. Cell IDs are 64-bit integers ordered along a space-filling curve, so nearby cells usually get nearby IDs. It can also cover any shape (a circle, a delivery zone) with a set of cells of mixed sizes.
- H3 (from Uber, open-sourced): covers the Earth with hexagons at 16 resolutions; each finer resolution has cells about one-seventh the area. A hexagon's six neighbours are all the same distance from its centre, which makes things like "demand in this area and the ring around it" clean to compute.
In an interview, you don't need their internals. Know that they exist, why (fewer distortions, better coverage, equal-distance neighbours for hexagons), and that geohash or a quadtree is a fine answer unless the interviewer pushes further.
Memory code: "S2 wraps the world in a cube; H3 tiles it with honeycomb."