Post

Geohash vs. Quadtree: How Proximity Search Actually Works

Every find-nearby design needs a spatial index, and the interview usually comes down to geohash or quadtree. Here is how each one works, the arithmetic, where each breaks, the alternatives (S2, H3, R-trees, Redis GEO), and how to choose by workload.

Geohash vs. Quadtree: How Proximity Search Actually Works

“Find restaurants within two kilometers” sounds like a query. It is actually an indexing problem. A database index sorts things along one line, and the earth is a surface. Every proximity design, from Yelp to ride matching to “friends nearby”, is a trick for folding two dimensions onto one line so that things close on the map stay mostly close in the index.

Geohash and the quadtree are the two tricks interviewers expect you to know. They look like rivals, and the interview is often framed as “which one?”. The more useful view is that they are the same idea, recursive division of space into four, stored two different ways. Geohash fixes the grid and turns each cell into a string any database can index. The quadtree lets the data decide where to divide and keeps the result as a tree in memory. Almost every pro and con follows from that one difference.

The Question

“Design a service that returns the businesses near a user’s location.”

Variants you will hear:

  • “Design Yelp” or “Design Google Places nearby search.”
  • “Find the 20 closest drivers to this rider.”
  • “Show friends who are within five kilometers.”
  • “How would you index a billion points so you can search by radius?”
  • “Geohash or quadtree? Defend your choice.”

What They Are Really Asking

  1. Do you know why an ordinary index fails? A B-tree on latitude and a B-tree on longitude do not make a spatial index. A candidate who says “index lat and lng” has not thought about the query.
  2. Can you explain one spatial index from first principles? Not “use geohash”, but how a point becomes a key, how a radius becomes a set of key ranges, and why the result needs a final distance filter.
  3. Do you know where it breaks? Cell edges, dense cities next to empty desert, the poles, objects that move every four seconds. Each scheme fails somewhere different, and naming the failure is the signal.
  4. Do you choose by workload? Static businesses read millions of times a day and drivers that move every few seconds want different indexes. The strong answer starts with the read and write pattern, not the data structure.

The Gotchas

Gotcha 1: Indexing latitude and longitude separately. A range scan on latitude returns a strip that runs around the whole planet; the one on longitude returns a strip from pole to pole. The database intersects two enormous sets to find a small square. A composite index on (lat, lng) is no better: it only narrows on the first column.

Gotcha 2: Searching only the cell the user is in. A user standing near the edge of a cell has neighbors a few meters away in the next cell. Every grid query is the user’s cell plus its neighbors, never the cell alone.

Gotcha 3: Assuming a shared prefix means close, and close means a shared prefix. The first half is true: two geohashes with a long common prefix are near each other. The second half is false. Two points one meter apart on either side of the equator can have geohashes that share no characters at all.

Gotcha 4: Returning the cells instead of the answer. Cells are a coarse filter. The candidates they return include points outside the radius, sometimes most of them. Always finish with an exact distance check and a sort.

Gotcha 5: Using degrees as distance. One degree of longitude is 111 kilometers at the equator and 56 kilometers at 60 degrees north. Euclidean distance on raw latitude and longitude is wrong everywhere except the equator. Use the haversine formula, or let the database do it.

Gotcha 6: Ignoring density. A fixed grid cell in midtown Manhattan holds ten thousand businesses; the same size cell in Wyoming holds none. A fixed precision is either too coarse for the city or too fine for the country. This is the problem the quadtree exists to solve.

Gotcha 7: Putting fast-moving objects in a structure that rebalances. A quadtree that splits and merges as points move is a poor fit for 250,000 driver updates a second. Moving objects want a grid where an update is two set operations.

Gotcha 8: Treating k-nearest as a radius search. “The 20 nearest” has no radius. Searching the neighboring cells and taking the first 20 is wrong if the 20th result is farther away than the edge of the area you searched; a closer point may sit just outside it.

Gotcha 9: Building a custom index when the database has one. PostGIS, MySQL, MongoDB, Elasticsearch, and Redis all ship spatial indexes. In most designs the right answer is “a spatial index in the database we already run”, and the geohash or quadtree discussion explains what that index does.

How to Answer

Why an ordinary index does not work

A B-tree answers “everything between A and B” on one sorted key. A radius query asks for everything inside a circle, which is a range on two keys at once. Put the index on latitude and the query “37.76 to 37.79” returns a band about 3 kilometers tall that circles the globe. Every point in that band has to be checked against the longitude range.

The fix is to make one key that encodes both coordinates, such that points near each other on the map usually get keys near each other in sort order. That is a space-filling curve: a line that wanders through every cell of a grid. Sort the cells by their position along the curve, and a small square on the map turns into a handful of short ranges on the line. A B-tree is good at short ranges.

Every scheme in this post is a choice of how to cut the map into cells and in which order to visit them.

Two families: fixed grids and adaptive trees

  Fixed grid Adaptive tree
Examples Geohash, S2, H3 Quadtree, R-tree, k-d tree
Where cell boundaries come from Pure math on the coordinates; the same everywhere The data; cells split where points are dense
A point’s cell Computed from the point alone Found by walking the tree
Stored as A key (string or 64-bit integer) in any index A tree structure, usually in memory or a specialized index
Strength Simple, distributable, cheap updates Even load per cell, natural nearest-neighbor search

Geohash: how it works

Geohash divides the world in half, then in half again, alternating between longitude and latitude. Each split produces one bit: 1 for the upper or eastern half, 0 for the lower or western half. Interleave the bits (longitude, latitude, longitude, …) and encode every five bits as one base-32 character.

San Francisco City Hall at 37.7749, -122.4194 becomes 9q8yyk8. The first character 9 is a 5,000 kilometer cell covering much of western North America. Each additional character divides the cell into 32 smaller cells. The prefix is the containment: every point inside 9q8yy has a geohash starting with 9q8yy.

Length Cell size at the equator Roughly the size of
4 39 km x 19.5 km A metro area
5 4.9 km x 4.9 km A town
6 1.2 km x 0.6 km A neighborhood
7 153 m x 152 m A city block
8 38 m x 19 m A building
9 4.8 m x 4.8 m A parking space

The widths shrink with latitude: at 60 degrees north every cell is half as wide as the table says.

Because the result is a string, storage is trivial. Add a geohash column, put an ordinary B-tree index on it, and a cell lookup is a prefix scan:

1
2
3
SELECT id, lat, lng
FROM businesses
WHERE geohash LIKE '9q8yy%';

The query. For a radius search, choose a precision whose cell is at least as wide as the radius, compute the user’s cell and its eight neighbors, scan all nine prefixes, then filter by exact distance:

flowchart LR
    P["User at 37.7749, -122.4194, radius 1 km"] --> C["Cell at precision 6: 9q8yyk"]
    C --> N["Cell plus 8 neighbors"]
    N --> S["9 prefix scans"]
    S --> F["Haversine filter: drop points beyond 1 km"]
    F --> R["Sort by distance, return top N"]

The user’s cell and its neighbors at precision 6:

  West Center East
North 9q8yyj 9q8yym 9q8yyt
Center 9q8yyh 9q8yyk 9q8yys
South 9q8yy5 9q8yy7 9q8yye

Notice that sort order and map order disagree. The strings just before and after 9q8yyk are 9q8yyj and 9q8yym, its northwest and north neighbors, while 9q8yy7, directly south, sorts far away. You compute neighbors with a library function, never by incrementing characters.

The boundary problem. Here the neighbors all share the prefix 9q8yy, so all nine scans hit one small region of the index. That is luck. Two points 31 meters apart straddling the equator and the prime meridian have geohashes s0000000, 7zzzzzzz, ebpbpbpb, and kpbpbpbp, which share nothing. The cells are adjacent on the map and at opposite ends of the index. The same thing happens, less dramatically, along every major cell boundary. This is why “search the neighbors” is mandatory and why the nine scans can land on unrelated parts of the index or on different shards.

Coarse or fine. Precision is a trade-off between the number of scans and the number of false positives. For a 2 kilometer radius:

Choice Cells scanned Area scanned Versus the 12.6 km² circle
Precision 5, 3 x 3 block 9 about 214 km² 17 times too much
Precision 6, covering only the circle’s bounding box about 40 about 30 km² about 2.4 times

Few scans with many wasted rows, or many scans with few wasted rows. Libraries such as S2’s region coverer pick a mix of cell sizes to balance the two, and adjacent cells often merge into one range scan.

Geohash in one line: fixed cells, a key any database can index, and a fixed precision that ignores density.

Quadtree: how it works

A quadtree starts with one node covering the whole map. When a node holds more than a threshold of points, say 100, it splits into four children: northwest, northeast, southwest, southeast. Points move down into the children. Splitting continues until every leaf holds 100 points or fewer.

flowchart TD
    W["World: 200M points, split"] --> NW["NW: 40M, split"]
    W --> NE["NE: 120M, split"]
    W --> SW["SW: 15M, split"]
    W --> SE["SE: 25M, split"]
    NE --> A["... dense city: 12 more levels"]
    NE --> B["... ocean: leaf with 3 points"]
    A --> L1["Leaf: 87 restaurants in one block"]

The tree is deep where the data is dense and shallow where it is sparse. A leaf in Manhattan covers a block; a leaf in Wyoming covers a county. Every leaf holds about the same number of points, which is the property a fixed grid cannot give you.

The query. Walk from the root to the leaf that contains the user. For a radius search, visit every node whose rectangle intersects the circle and skip every node that does not; this prunes most of the tree. For “the k nearest”, run a best-first search: a priority queue ordered by the minimum possible distance from the user to each node’s rectangle. Pop the closest node, expand it, and stop when the k-th best point found is closer than the next node in the queue. That stopping rule makes the answer exact, which is the main thing geohash lacks.

The arithmetic. For 200 million businesses with a leaf limit of 100:

  • At least 2 million leaves, and about a third as many internal nodes.
  • Storing only business IDs at 8 bytes each: 1.6 GB.
  • Storing IDs plus coordinates (24 bytes per point): about 5 GB, plus a few hundred megabytes of node overhead.

It fits in the memory of one server. Building it from a database scan takes minutes. So the classic design is a read-only quadtree on each of several index servers, rebuilt from the database periodically, with businesses rarely moving and a few minutes of staleness acceptable for a new listing.

Where it struggles. The tree is a pointer structure in one process’s memory, not something a database indexes for you. Each server rebuilds it on startup. Splitting it across machines is awkward because subtrees are uneven by design. And updates are expensive for moving points: a moving point is a delete and an insert, which can trigger a split in one place and a merge in another, all under a lock while queries run.

Quadtree in one line: cells shaped by the data, even load per leaf, exact nearest-neighbor search, and a structure that lives in one process’s memory.

Geohash is a quadtree, flattened

Each geohash bit halves a cell; two bits divide it into four. A geohash is a path down a quadtree of fixed depth, written as a string in Z-order (the order a quadtree visits its children: one row of quadrants, then the next). Bing Maps “quadkeys” make this explicit: tile 0231 is child 0, then 2, then 3, then 1.

That gives you a way out of the either-or. Store a variable-length cell key: short prefixes for sparse regions, long ones for dense regions. That is an adaptive quadtree stored in a B-tree. Several production systems do exactly this, and S2 is built around it, with cells at 30 levels that you mix freely.

Head to head

  Geohash Quadtree
Cell boundaries Fixed by math Set by data density
Load per cell Uneven: a city cell can hold 10,000 times a rural one Even by construction
Storage A string column; any B-tree or key-value store An in-memory tree, rebuilt on startup
Point update Recompute the string, update one row Delete and insert; may split or merge nodes
Moving objects Good: an update is “move from cell A to cell B” Poor: rebalancing under load
Radius query Cell plus 8 neighbors, then distance filter Prune nodes outside the circle
k-nearest Approximate unless you expand rings carefully Exact with best-first search
Sharding Easy by prefix, but dense prefixes become hot shards Hard; subtrees are uneven
Edge problem Neighbors can have unrelated prefixes None; the tree knows its neighbors spatially
Distortion Cells narrow toward the poles Same, if built on latitude and longitude
Caching Easy: cache results per cell string Harder: nodes are not stable keys

The alternatives

Option What it is Pick it when
R-tree (PostGIS GiST, MySQL spatial, SQLite R*Tree) An adaptive tree of overlapping bounding rectangles, built for disk pages. GiST is the Generalized Search Tree framework PostGIS uses. You already run the database, need polygons as well as points, or want ORDER BY distance LIMIT 20 with no custom code. This is the default for most systems.
Google S2 (MongoDB 2dsphere, Google Maps, Foursquare) The sphere projected onto a cube, each face divided into a quadtree, cells ordered along a Hilbert curve and stored as 64-bit integers. 31 levels, from a cube face down to about a square centimeter. You need accuracy on a sphere, polygon coverings (delivery zones, geofences), or a mix of cell sizes. The Hilbert curve has fewer long jumps than geohash’s Z-order.
Uber H3 Hexagonal cells at 16 resolutions, as 64-bit integers. All six neighbors of a cell are the same distance from its center. Moving objects, “cell plus k rings” search, and aggregation by area (surge pricing, demand heat maps). The real-time shape post uses it for ride matching.
Redis GEO (GEOADD, GEOSEARCH) A 52-bit geohash stored as the score in a sorted set, with radius and box search built in. You need a fast, mutable, in-memory index of moving things and already run Redis.
Elasticsearch / OpenSearch geo_point Lucene’s BKD (block k-dimensional) tree, plus geohash and geotile grid aggregations. Proximity is one filter in a search that also matches text, ratings, and opening hours.
k-d tree A binary tree alternating splits on x and y. Static, in-memory point sets and nearest-neighbor work in analytics or machine learning. Rarely the service answer.

Choosing by workload

Workload Choice Why
Static points, read-heavy, already on Postgres PostGIS with a GiST index No new system; exact distance and sort in SQL
Static points, very high read rate, own service Geohash cells in a key-value store, or an in-memory quadtree on replicas Both are cacheable; the quadtree handles density better
Moving points, very high write rate (drivers, couriers) Geohash or H3 cells in memory (Redis or a custom service) An update is two set operations; no rebalancing
Polygons: delivery zones, geofences, “which zone contains this point” S2 coverings or an R-tree Grids of points cannot answer containment for shapes
Proximity plus text and filters Elasticsearch geo_point One query, one index, ranked
Aggregation by area: heat maps, pricing per zone H3 Equal-area-ish hexagons with equidistant neighbors

Scaling: replicate before you shard

The index for 200 million points is a few gigabytes. That fits on one machine, so the first move is the one from the read-heavy lookup post: scale reads by copying the index to more servers, not by splitting it.

Shard only when the data or the write rate outgrows one machine. When you do, a geographic shard key (a geohash prefix or an S2 cell ID) keeps each query on one or a few shards, but density makes the shards uneven: the shard holding New York is a hot shard. Fix it the quadtree way, by splitting dense prefixes into more shards than sparse ones, and remember that queries near a shard boundary fan out to two to four shards. The alternative is to shard the business data by business ID and keep the geo index fully replicated, which works as long as the index fits in memory.

A worked answer: nearby businesses

Requirements. 200 million businesses, 100 million daily users, about 5,000 searches a second at peak, results within 200 milliseconds. Businesses are added and edited rarely; a new listing can take minutes to appear.

Shape. Read-heavy lookup. The data is nearly static, so the design is about the read path.

Storage. Businesses live in a relational database sharded by business ID, with details cached.

Index. A location service holds an in-memory index of business ID and coordinates, about 5 GB. I would use a quadtree with a 100-point leaf limit so that dense cities and empty regions return similar numbers of candidates. The index is rebuilt from the database every few minutes, and the new tree is swapped in atomically. If I did not want a custom service, I would use geohash precision 6 in a key-value store, cell plus 8 neighbors, and accept uneven cells.

Query. Find candidates within the radius, filter by haversine distance, then fetch details from the business cache and rank by distance, rating, and opening hours.

Scale. Five thousand reads a second is a handful of replicas. I would not shard the index until it outgrows memory, and then I would shard by geographic cell with dense cities split further.

What would change my mind. If the points moved every few seconds, like drivers, I would drop the quadtree for H3 or geohash cells in Redis, because rebalancing a tree at that write rate costs more than uneven cells.

The thirty-second answer

“A normal index sorts one dimension, so I need a key that folds two dimensions into one: a space-filling curve. Geohash does it with a fixed grid; the key is a string, so any database can index it, and a radius search is the user’s cell plus eight neighbors, then an exact distance filter. Its weakness is density: one precision is wrong for both Manhattan and Wyoming. A quadtree splits cells where the data is dense, so every leaf holds about the same number of points and nearest-neighbor search is exact, but it lives in memory and rebalances badly under heavy updates. Static businesses: a quadtree or PostGIS. Moving drivers: geohash or H3 cells. Polygons: S2 or an R-tree.”

Follow-Up Questions to Expect

“How do you find the 20 nearest with geohash?” Search the cell and its neighbors. If you have 20 candidates and the 20th is closer than the nearest edge of the searched area, you are done. Otherwise add another ring of cells or drop one character of precision and repeat. The edge check is what makes it correct; without it you can miss a closer point just outside the area you searched.

“What happens when one cell has 50,000 businesses?” With geohash, use a finer precision in that region, which means storing more than one precision or variable-length keys, and cap the candidates per cell. With a quadtree it cannot happen: the leaf would have split.

“A business moves. How does the index update?” Geohash: recompute the string and update the row; the index follows. Quadtree: delete and reinsert, or, more simply, tolerate a few minutes of staleness and pick it up on the next rebuild.

“Why not just use PostGIS?” Usually you should. A GiST index answers radius and nearest-neighbor queries with exact distances in SQL. The custom-index answer is for read rates or write rates one database cannot serve, and the interview wants to see that you know which one you are in.

“How does this work for 250,000 location updates a second?” Keep only live state in memory, keyed by cell: cell -> set of driver IDs. An update is two set operations, removing the driver from the old cell and adding it to the new one. Partition by city or region so each node owns a manageable area. The real-time shape post walks through it.

“What about the poles and the antimeridian?” Geohash cells get narrower toward the poles, so a fixed precision covers less ground; at 60 degrees north a cell is half as wide. At the 180 degree line, longitude wraps, and a correct neighbor function wraps with it. S2 and H3 avoid most of this by working on the sphere. For a business search in populated areas, it rarely matters; say so.

“How would you index delivery zones, where the question is which zone contains this address?” That is containment, not proximity. Cover each polygon with S2 cells, look up the address’s cell to get candidate zones, then run an exact point-in-polygon test. An R-tree over the polygons’ bounding boxes works the same way.

Key Takeaways

  1. A spatial index folds two dimensions onto one sortable line. Every scheme is a choice of cells and the order to visit them.
  2. Geohash is a fixed grid stored as a string: simple, cacheable, shardable, cheap to update, and blind to density.
  3. A quadtree divides space where the data is dense: even leaves and exact nearest-neighbor search, but it is an in-memory structure that rebalances under updates.
  4. Geohash is a flattened quadtree of fixed depth. Variable-length cell keys get you the adaptive version inside an ordinary index.
  5. Always search the cell plus its neighbors, and always finish with an exact distance filter.
  6. Choose by workload: static and read-heavy suggests a quadtree or PostGIS; moving objects suggest geohash or H3 cells; polygons suggest S2 or an R-tree.
  7. The index for hundreds of millions of points fits in memory. Replicate it before you shard it.

Further Reading

This post is licensed under CC BY 4.0 by the author.