Geospatial Indexing: Geohash and Quadtrees

1The core idea#

Start with the problem in one sentence: a point on Earth has two coordinates, and a normal B-tree index sorts on one dimension at a time.

Why that one-dimension limit hurts.

• Index on longitude and you can find every point in a vertical strip of the planet fast.
• But "nearby" is a small box or circle that spans a range in both longitude and latitude.
• The B-tree narrows longitude, then you still scan every row in that north-to-south strip to filter latitude.
• In a dense city that strip might hold a million points when you wanted twelve.

Make it concrete with real numbers.

• Rides service, 5,000,000 driver rows, indexed on longitude.
• Query longitude BETWEEN -122.43 AND -122.40, a strip about 2.5 km wide.
• In San Francisco that strip runs the full height of the data, so it matches roughly 180,000 rows.
• The B-tree hands you all 180,000, then you filter latitude in memory to get the 40 drivers actually near the rider.
• You paid for 180,000 reads to answer a 40-row question. That is the failure mode spatial indexing kills.

The game of geospatial indexing, stated once.

• Turn two dimensions into one, keeping points that are close on the map close in the index.
• Then a single range scan gives you a tight candidate set instead of a strip.

Two popular ways to do it.

• Geohash encodes a lat/long pair into a short string like 9q8yyk. Points that share a prefix are near each other, so it drops straight into any ordinary B-tree, sorted key store, or Redis sorted set.
• Quadtree recursively splits a region into four quadrants. A cell splits only where points pile up, so dense areas get fine cells and empty ocean stays one big cell.

Both solve the same core problem. They make different bets about your data and your infrastructure.

2How it works#

Geohash#

Take a point, say 37.775, -122.418 (somewhere in San Francisco). Geohash interleaves the bits of the two coordinates.

The encoding, step by step.

• Ask "is longitude in the left or right half of its range?" and "is latitude in the top or bottom half?"
• Record a bit each time and halve the range.
• Interleave those bits, group them into chunks of 5, and base-32 encode each chunk into a character.

The length of the string sets the precision.

The magic property, and how you search a radius.

• 9q8yy and 9q8yz are adjacent cells, so a prefix search ("everything starting with 9q8yy") returns one cell's worth of points in a single range scan.
• To search a radius, compute the geohash of your center, add its 8 neighbor cells, and query all 9 prefixes.

A worked example, end to end

Run the 2 km rider query through this so the numbers are real. Rider is at 37.775, -122.418. A 2 km radius wants a cell a bit bigger than that, so pick 5-character precision (a ~2.4 km cell). The rider encodes to 9q8yy.

• Step 1: compute the 8 neighbors. North, south, east, west, and the 4 diagonals give 9q8yz, 9q8yw, 9q8yx, 9q8yv, and so on: 9 prefixes total including the center.
• Step 2: fire 9 prefix scans against Redis, one per cell, for example ZRANGEBYLEX drivers [9q8yy ( 9q8yz. Say each cell holds about 70 live drivers, so you pull back roughly 9 x 70 = 630 candidate driver ids. Compare that to the 180,000 rows the naive longitude strip returned: same question, 285x fewer reads.
• Step 3: filter by true distance. For each of the 630 candidates compute haversine distance from the rider and drop anything past 2 km. The 5-char cells cover about 7.2 km edge to edge across the 3x3 block, so plenty of the 630 sit outside the circle. After the filter you have about 110 drivers genuinely within 2 km.
• Step 4: sort and return. Sort those 110 by distance and return the nearest 20 to the ranking service.

The tally: 9 small scans plus 630 distance calculations, call it well under 5 ms. That is the gap between a design that pages and one that does not.

Quadtree#

A quadtree starts with one cell covering your whole map and adapts to density as points arrive.

How it grows.

• Set a capacity, say 100 points per cell.
• When a cell exceeds that, it splits into four children: northwest, northeast, southwest, southeast.
• Points move down into whichever child contains them.
• Dense downtown blocks end up many levels deep; a quiet rural county stays shallow.

How you query a radius.

• Start at the root and walk down, descending only into child cells that intersect your search box.
• Skip whole branches that cannot contain a match. That pruning is what keeps it fast.

The one-line difference from geohash: a quadtree adapts its resolution to density automatically, while geohash precision is something you choose up front.

3Trade-offs#

This is the part interviewers actually grade.

Geohash wins on operational simplicity.

• It is a plain string you can store in Postgres, in a Redis sorted set with ZRANGEBYLEX, in DynamoDB as a sort key.
• No special server, no custom tree to keep in sync.
• If you are building fast and want something a whole team understands, this is the boring correct answer.

The geohash catch is the boundary problem plus fixed precision.

• Two points 10 meters apart can land in different cells if they straddle a cell edge, which is why you query the 8 neighbors too.
• Precision is fixed, so a 6-character search in rural Montana might return 3 points while the same search in Manhattan returns 50,000.
• You cannot tune per region without re-encoding.

Quadtree wins on adaptive density.

• It gives roughly even work per query because it refines where the data is.
• For a map that renders pins and must stay smooth whether you are over the Pacific or over Tokyo, that balancing is genuinely valuable.

The quadtree catch is that it is a living tree.

• It usually lives in memory on one machine, splits and merges on writes, and does not shard cleanly across a cluster.
• High write churn means constant rebalancing.
• Spreading a quadtree over 50 servers is a real engineering project. Spreading geohash keys is just prefix-based routing.

My rough rule: heavy writes, many machines, keep-it-simple leans geohash. Mostly-read, single-box, needs even resolution leans quadtree. Production systems often use something more advanced than either, which brings us to the next section.

4Where it is used#

Ride-hailing and delivery.

• Open a rides app and the nearby cars came from matching your geohash cell against drivers who recently wrote their location into the same cell.
• A common pattern is a Redis layer keyed by geohash prefix, so "drivers in cell 9q8yy" is one lookup.
• Uber's H3 library is a hexagonal grid built on exactly this motivation. With square cells a diagonal neighbor's center is 1.41x farther than an edge neighbor's, so "the 8 neighbors" are not all equally near.
• Hexagons give 6 neighbors all at the same distance, which makes radius math cleaner.

Mapping and points-of-interest search.

• Google's S2 library maps the sphere onto a space-filling curve, a cousin of geohash that avoids the distortion you get near the poles with plain lat/long grids.
• Quadtree variants show up in map rendering, where you load only the tiles in view.

Databases you already use.

• PostGIS (the Postgres extension) uses R-trees under the hood via GiST indexes, a spatial structure optimized for shapes, not just points.
• Elasticsearch indexes geo points using geohash-style tiling.
• MongoDB supports geohash-based 2d indexes and S2-based 2dsphere indexes.

When you reach for the raw structures yourself.

• Mostly when you are inside the serving path and need control.
• A matching service that holds live driver locations in memory, or a cache layer where you want geohash keys so you can shard by region.

5Common pitfalls and gotchas#

Forgetting the neighbor cells.

• The single most common bug.
• You geohash the center, query that one prefix, and silently miss half the nearby points sitting just across a cell boundary.
• Always query the center plus 8 neighbors, then filter by true distance.

Treating cells as circles.

• A geohash cell is a rectangle and your search is usually a radius, so the cell's corners stick out past your circle.
• Skip the final exact-distance filter and you return points farther than the user asked for.
• In the worked example that filter was the difference between 630 candidates and 110 real matches.

Picking precision blind.

• A 5-character geohash is about 2.4 km wide.
• Want "within 500 meters"? A single 5-char cell is too coarse and you over-fetch.
• A 7-char cell might split your result across so many neighbor cells that you issue a dozen queries.
• Match cell size to your typical radius.

Pole and antimeridian weirdness.

• Plain lat/long geohashes distort badly near the poles, and the +180/-180 longitude seam can split a region.
• If your product is global and precision-sensitive, this is the argument for S2 or H3 over naive geohash.

Stale locations in a high-write world.

• For moving objects the index is only as fresh as your last write.
• If drivers report every 4 seconds but your index lags, you match riders to cars that already left.
• The indexing structure is not the bottleneck here. Your write path and TTLs are. Say that out loud in an interview.

Hot cells.

• A stadium just let out and 40,000 people open the app in one geohash cell. That cell is now a hot shard.
• Flat prefix sharding does not save you.
• You need a plan: finer cells in dense zones, or a secondary split.

6How it shows up in interviews#

The classic prompts.

• "Design a ride-sharing service", "find restaurants near me", "proximity service for a social app".
• The geospatial index is usually one component, and the interviewer wants to see you reach for it unprompted.

What they probe. For each one, here is what a weak answer sounds like next to a strong one, because the gap between them is the whole grade.

Why not just query lat BETWEEN and long BETWEEN?

• Weak: "That would be too slow."
• Strong: "A B-tree sorts on one axis, so a bounding-box query narrows one dimension and then scans the whole strip and filters the rest in memory. On 5 million rows a 2.5 km longitude strip in SF can match 180,000 rows to answer a 40-row question. That read amplification is the entire reason spatial indexes exist."

Geohash or quadtree, and why?

• Weak: "Geohash, because it is popular and most people use it."
• Strong: "This is write-heavy with drivers pinging every 4 seconds, and I want to shard across regions, so geohash keys in Redis give me simple prefix sharding and cheap single-key updates. A quadtree would rebalance on nearly every write and does not distribute cleanly across 50 machines, so I would only pick it for a read-mostly single-box workload like map tile rendering."

How do you handle the radius query exactly?

• Weak: "I look up the user's cell and return everyone in it."
• Strong: "I encode the center to a 5-char geohash, add the 8 neighbor cells, run 9 prefix scans, collect the roughly 600 candidates, then compute real haversine distance on each and drop anything past 2 km before sorting the survivors and returning the top 20." Mentioning the haversine step is what tells the interviewer you have actually shipped this.

What about hot cells and skew?

• Weak: silence, or "Redis can handle it."
• Strong: "A stadium emptying puts 40,000 users in one cell, which becomes a hot shard that flat prefix sharding cannot save. I would use finer precision in known dense zones, offload hot cells onto dedicated capacity, or move to H3 whose even neighbor geometry makes the dense-area math cleaner." This is the answer that separates seniors from everyone else.

Scale and freshness.

• Weak: "The index makes lookups fast, so we are fine."
• Strong: "For moving objects the lookup was never the constraint. At a million location writes per second my real problem is write amplification and index freshness. I put short TTLs on location entries so stale drivers age out, and I accept that match quality is bounded by how recently the index was written, not how fast I can read it."

The weak candidate recites what geohash is. The strong one treats the index as one dial and reasons about writes, sharding, skew, and staleness around it.

Want to see this wired into a full design? Read the System Design Question walkthrough on building a proximity service for nearby-drivers matching.