Skip to content
Tutorials Center
My learning

Topics

Lesson 44 of 65 ยท Core Algorithms and Data Structures for Design

Geospatial Indexing

Learn how systems like Uber and Yelp find nearby points: geohash, quadtrees, S2 and H3 cells, proximity search and boundary pitfalls, with runnable Python examples.

"Find restaurants within 2 km." "Match this rider with the closest driver." "Which stores are near this zip code?" Location queries are everywhere in apps such as ride hailing, delivery, dating and maps. They look simple, but a database index handles them poorly. A B-tree orders values along one dimension, while a location has two (latitude and longitude). A query like lat BETWEEN a AND b AND lon BETWEEN c AND d can use an index on only one of the columns well and then scans the rest.

Geospatial indexing solves this by mapping two-dimensional space into something a standard index or in-memory structure can search quickly. This lesson covers the three families you should know: grids and geohash, quadtrees, and hierarchical cell systems such as S2 and H3.

The core idea: divide the world into cells

If you divide the map into cells and give each cell an ID, then "find nearby points" becomes: compute the cell of the query point, fetch the points in that cell and its neighbors, and compute exact distances only for those candidates. A cell ID can be an ordinary string or integer key, so any key-value or relational index works.

Three ways to cut the map

Fixed grid Equal squares. Simple but uneven density.
Geohash Recursive halving, encoded as a string.
Quadtree Split only crowded cells into four.
S2 and H3 Cells on a sphere, with neighbors defined.

All of them turn 2D location into a searchable key.

1 / 2

Geohash

A geohash encodes a latitude and longitude into a short string by repeatedly halving the world:

  1. Start with longitude from -180 to 180 and latitude from -90 to 90.
  2. Alternate between longitude and latitude. At each step, ask "is the point in the lower or upper half?" and record bit 0 or 1.
  3. Group the bits into 5-bit chunks and encode each chunk as a character from a 32-letter alphabet (digits and letters, without a few look-alikes).

Each extra character narrows the cell. A longer string means a smaller cell. Crucially, points with the same prefix are close together, so you can index geohashes as plain strings and search by prefix: WHERE geohash LIKE 'u33d%'.

Characters Cell size (approximate)
4 39 km ร— 20 km
5 4.9 km ร— 4.9 km
6 1.2 km ร— 0.6 km
7 153 m ร— 153 m
8 38 m ร— 19 m
Python Geohash encoding

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The three Berlin places share a prefix; Paris starts differently. With a database, an index on the geohash column turns proximity into a prefix scan.

The boundary problem

Two points can be a few meters apart yet sit on opposite sides of a cell edge, so their geohashes share no prefix (a famous example is the prime meridian). Therefore a proximity search must always query the target cell and its eight neighbors, then filter by real distance. Also note that cells are not circles: the nearest point may be in a neighbor cell, and a cell contains points up to its diagonal away.

Python Nearby search: cell plus neighbors, then exact distance

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only a handful of candidates needed an exact distance check, instead of every place in the city. With millions of rows that is the difference between milliseconds and a full scan.

Quadtrees

A quadtree starts with one square covering the whole area. If it contains more than a threshold of points (say 4), it splits into four equal child squares, and so on recursively. Dense areas such as city centers end up with many small cells; empty areas such as the ocean stay as a few big cells. The tree adapts to the data, which a fixed grid cannot do.

A search descends only into the cells that overlap the query region, skipping the rest. Quadtrees are usually kept in memory; services such as proximity servers rebuild or update them as points move, and shard them by region when they grow too large.

Python A tiny quadtree with range search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

S2 and H3

Geohash and square grids distort near the poles and have awkward neighbors (diagonals sit farther away than sides). S2 (Google) projects the sphere onto a cube and uses a Hilbert curve to number the cells, so cells that are close in number are close on the map, which is great for range scans. H3 (Uber) tiles the globe with hexagons; every hexagon has six neighbors at the same distance, making "k-ring" neighbor searches and heat maps clean. Pick them when you need accuracy at global scale, uniform neighbor logic or analytics over areas.

Approach Good for Weak spot
Fixed grid Simple prototypes, uniform data Uneven density
Geohash Storing in any database, prefix queries Boundary cases, distortion at poles
Quadtree In-memory, uneven density Rebalancing as points move
S2 / H3 Global systems, neighbor logic More concepts, a library needed
R-tree (PostGIS) Polygons and rectangles in a database Heavier than point indexes

Databases offer these natively: PostGIS (R-tree/GiST), MongoDB 2dsphere, Redis GEOADD/GEOSEARCH (geohash in a sorted set) and Elasticsearch geo queries.

Designing proximity services

For "nearby drivers" or "nearby places", a typical design is:

  • Store static places (restaurants) in a database indexed by cell ID, and cache popular cells.
  • Keep moving objects (drivers) in memory, such as Redis geo sets or sharded quadtrees, updated every few seconds. Constant writes would overwhelm a durable database.
  • Shard by region or cell prefix so a query touches one or a few shards (see Sharding and Partitioning); beware hot cells in city centers and split them further.
  • Query the cell plus neighbors, filter by exact distance, rank by distance, rating or ETA, then return the first page.
  • Use a radius expansion loop: start small, and widen the search ring until enough results are found.

Be explicit in interviews: "Geohash or H3 gives candidates; haversine distance gives the final answer." Mention boundary cells and hot spots before the interviewer asks.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is a plain B-tree index on latitude and longitude poor for nearby search?

    An index sorted by one column can only narrow the search along that axis, so many irrelevant rows are still scanned.
  2. 2. Why must a geohash proximity query also check neighboring cells?

    Points on both sides of an edge can be meters apart yet lie in different cells, so the search covers the target cell and its neighbors.
  3. 3. What advantage does a quadtree have over a fixed grid?

    Crowded areas are split into many small cells while empty areas stay as large cells.
  4. 4. Where should rapidly moving driver locations be kept?

    Updates every few seconds are too heavy for a durable database; fast in-memory stores handle them.

Summary

  • Location queries need 2D indexing; cells turn them into key lookups plus an exact distance filter.
  • Geohash encodes location as a string where shared prefixes mean nearby; always search the cell plus its neighbors.
  • Quadtrees adapt to density and prune whole regions during search; S2 and H3 handle the sphere with consistent neighbors.
  • Keep moving objects in memory, shard by region and watch for hot cells.
  • Candidates come from the index; final answers come from exact distance and ranking.

Next: Tries and Top-K