“Find drivers near me” is a two-dimensional range query, and B-trees are one-dimensional. Here’s how you turn a map into something a database can index.
Prerequisites: Indexing, Sharding Time to read: ~20 minutes
A rider opens Careem. Find every available driver within 3 km.
The naive query:
SELECT * FROM drivers
WHERE lat BETWEEN 24.83 AND 24.89
AND lng BETWEEN 67.00 AND 67.06;
🚨 This is slower than it looks, and the reason is subtle.
An index on lat finds every driver in that latitude band — which is a strip circling the entire
planet. An index on lng finds a strip from pole to pole. The database picks one index, scans that
strip, and filters the rest in memory.
📐 With 1 million drivers globally, a 0.06° latitude band contains maybe 5,000 of them, of which
perhaps 50 are actually in your box. You scanned 100× more rows than you needed. A composite index
on (lat, lng) doesn’t fix it either — the
leftmost-prefix rule means once
you use a range on lat, lng can only filter, not seek.
The core issue: B-trees are one-dimensional. They sort along a single line. Geographic proximity is two-dimensional, and there’s no ordering of a plane that preserves all proximity.
Every technique below is a way of mapping 2D space onto a 1D line while preserving locality as well as possible — so that nearby points get nearby index keys.
Recursively divide the world in half, alternating longitude and latitude, recording each choice as a bit. Encode the bits in base32.
Start: lng ∈ [-180, 180], lat ∈ [-90, 90]
Is lng > 0? yes → bit 1, lng ∈ [0, 180]
Is lat > 0? yes → bit 1, lat ∈ [0, 90]
Is lng > 90? no → bit 0, lng ∈ [0, 90]
...
Result: "tkm4d8f" — Karachi, roughly
The property that makes it useful: shared prefixes mean physical proximity.
tkm4d8f ← two points with the same 6-character prefix
tkm4d8g ← are within ~1.2 km of each other
| Geohash length | Approximate cell size |
|---|---|
| 1 | 5,000 × 5,000 km |
| 4 | 39 × 20 km |
| 5 | 4.9 × 4.9 km |
| 6 | 1.2 × 0.6 km |
| 7 | 153 × 153 m |
| 8 | 38 × 19 m |
Why this is so practical: a proximity search becomes a string prefix query, which any ordinary B-tree index handles perfectly.
CREATE INDEX idx_geohash ON drivers (geohash);
SELECT * FROM drivers WHERE geohash LIKE 'tkm4d%'; -- ~5 km cell, uses the index
🚨 The edge problem — and this is the standard interview follow-up. Two points can be 10 metres apart and share no prefix, because they sit on opposite sides of a cell boundary:
│
tkm4c │ tkm4d
●─┼─● 10 metres apart, completely different prefixes
│
The fix: always query the target cell plus its 8 neighbours. Every geohash library provides a
neighbors() function. Nine prefix queries instead of one — still fast, still index-backed.
⚖️ The other weakness: fixed cell sizes. A geohash-6 cell is ~1 km² whether it contains 10,000 drivers in downtown Karachi or zero in the desert. You can’t adapt resolution to density, which is what quadtrees do.
Recursively subdivide a square into four quadrants — but only where there’s data.
┌─────────┬─────────┐ Dense area subdivides further;
│ │ ┌──┬──┐│ empty area stays as one big node.
│ sparse │ ├──┼──┤│
│ │ └──┴──┘│
├─────────┼─────────┤
│ │ │
│ │ sparse │
└─────────┴─────────┘
The rule: a node splits into four children when it exceeds a capacity threshold (say 100 points).
✅ Adaptive to density. Manhattan gets deep subdivision; the Sahara gets one node. Each leaf holds a similar number of points, so query cost is uniform regardless of where you look. ✅ Efficient for both proximity and bounding-box queries. ❌ It’s an in-memory tree structure, not a simple index column — harder to store in a standard database and harder to distribute. ❌ Rebalancing as points move is expensive. For constantly-moving objects (drivers), you’re updating the tree continuously.
Use for: relatively static points with wildly varying density — restaurants, stores, points of interest.
The production-grade options, and worth knowing by name.
S2 projects the sphere onto the six faces of a cube, then applies a Hilbert curve to each face to map 2D to 1D.
🧠 Why a Hilbert curve? It’s a space-filling curve with better locality than geohash’s Z-order curve — points close on the curve are almost always close in space, and it has fewer of geohash’s sudden “jumps” at cell boundaries. It also handles the sphere properly, avoiding the distortion you get near the poles when you treat lat/lng as a flat plane.
An S2 cell ID is a 64-bit integer, so it indexes like any other number, and cells come in 31 levels from ~85 km² down to ~1 cm².
H3 (Uber’s) uses hexagons instead of squares.
🚨 Why hexagons matter — a genuinely nice detail: every neighbour of a hexagon is the same distance away (centre to centre). With squares, diagonal neighbours are 1.41× further than edge neighbours, which distorts any distance-based calculation, smoothing, or flow analysis. Hexagons also tile the plane with more uniform coverage.
The trade-off: hexagons can’t be perfectly subdivided into smaller hexagons, so H3’s hierarchy is approximate — a parent cell’s children don’t tile it exactly.
| Geohash | Quadtree | S2 | H3 | |
|---|---|---|---|---|
| Shape | Rectangle | Square | Square (on cube faces) | Hexagon |
| Curve | Z-order | — | Hilbert | Hilbert-ish |
| Adaptive to density | ❌ | ✅ | ❌ | ❌ |
| Index as | String prefix | Tree | 64-bit int | 64-bit int |
| Distributes easily | ✅ | ❌ | ✅ | ✅ |
| Uniform neighbours | ❌ | ❌ | ❌ | ✅ |
| Used by | Elasticsearch, Redis | Classic implementations | Google Maps, MongoDB | Uber |
🚨 Don’t implement any of this by hand. Every serious database has geospatial support:
PostGIS (PostgreSQL) — the gold standard for anything static:
CREATE EXTENSION postgis;
ALTER TABLE places ADD COLUMN geog geography(POINT, 4326);
CREATE INDEX idx_geog ON places USING GIST (geog); -- R-tree based
SELECT name, ST_Distance(geog, ST_MakePoint(67.03, 24.86)::geography) AS metres
FROM places
WHERE ST_DWithin(geog, ST_MakePoint(67.03, 24.86)::geography, 3000)
ORDER BY metres LIMIT 20;
PostGIS uses GiST indexes (R-trees), which handle 2D natively — a different approach again, based on bounding-box hierarchies rather than space-filling curves.
Redis — for high-frequency moving objects:
GEOADD drivers 67.03 24.86 "driver:1234"
GEOSEARCH drivers FROMLONLAT 67.03 24.86 BYRADIUS 3 km ASC COUNT 20
Backed by a sorted set of geohash scores. In-memory, so updates are cheap — which is exactly what you need when a million drivers report position every 4 seconds.
Elasticsearch — geo_point and geo_shape types, good when combining geo filters with text
search and faceting (“Italian restaurants within 2 km, rated 4+”).
MongoDB — 2dsphere indexes, built on S2.
Static points (restaurants) are easy. Moving points are the hard case, and it’s what ride-hailing interviews are really about.
📐 The write load:
1,000,000 active drivers, reporting position every 4 seconds
= 250,000 location writes/second
That’s a serious write workload, and if every write updates a B-tree index it’s worse — every position change moves the row in the index.
How real systems handle it:
1. Keep locations in memory, not in the primary database. Redis GEO or a purpose-built in-memory service. Positions are ephemeral — you don’t need durability for “where was this driver 3 seconds ago.” Losing it on restart is acceptable; drivers report again in 4 seconds.
2. Separate the write path from the read path. Location updates go to a fast in-memory store; matching queries read from it. Historical tracks go to a time-series store asynchronously, via a queue.
3. Shard by geographic cell. All drivers in cell tkm4d live on the same node.
🚨 But then you get hot cells — downtown at rush hour has 100× the density of a suburb, and that one shard saturates. Fixes: variable cell sizes by density (finer cells where it’s busy), or sub-shard hot cells with a suffix. This is the hot key problem in geographic form, and recognizing it is a strong signal.
4. Reduce update frequency adaptively. A stationary driver doesn’t need to report every 4 seconds. A driver on a highway does. Adaptive reporting can cut the write volume substantially.
🎙️ “Driver locations go to Redis GEO — they’re ephemeral and updated 250,000 times a second, so they don’t belong in the primary database. Historical tracks go to a time-series store via Kafka. I’d shard by S2 cell, and I’d expect hot cells downtown at peak, so cell sizes need to vary with density.”
Two formulas, and picking the right one matters:
Haversine — great-circle distance on a sphere. Accurate to ~0.5%, fast, and the standard choice.
Euclidean on lat/lng — 🚨 wrong, and wrong in a way that varies by latitude. One degree of
longitude is 111 km at the equator and 0 km at the poles. Treating lat/lng as a flat plane produces
distances that are badly distorted away from the equator. Acceptable only for very small areas with a
latitude correction factor (cos(lat)), and even then be careful.
Vincenty / geodesic — accounts for Earth being an oblate spheroid. Accurate to millimetres, noticeably slower. Only needed for surveying-grade work.
⚖️ The practical pattern: use the index to get candidates cheaply (a bounding box or cell query), then compute exact distances only for those candidates and sort. Never compute Haversine across your whole table.
-- Cheap index-backed filter first, exact distance second
WHERE ST_DWithin(geog, point, 3000) -- uses the GiST index
ORDER BY ST_Distance(geog, point) -- exact, only on the survivors
| Decision | Gain | Cost |
|---|---|---|
| Geohash | Works with any B-tree index; trivial to shard | Edge problem; fixed cell sizes |
| Quadtree | Adapts to density | In-memory structure; expensive updates; hard to distribute |
| S2 / H3 | Better locality, 64-bit integer keys, production-grade | Library dependency; more concepts |
| PostGIS / GiST | Exact, full geometry support, SQL-native | Heavier writes; single-node scaling limits |
| Redis GEO | Very fast updates, ideal for moving objects | In-memory only; no durability |
| Sharding by cell | Queries stay local to one shard | Hot cells in dense areas |
1. Feel the geohash prefix property.
import geohash2 as gh
karachi = gh.encode(24.8607, 67.0011, precision=7)
nearby = gh.encode(24.8620, 67.0025, precision=7)
lahore = gh.encode(31.5204, 74.3587, precision=7)
print(karachi, nearby, lahore)
# The first two share a long prefix; the third shares almost nothing.
2. Find the edge problem yourself. Generate points on a grid, geohash them at precision 6, and find pairs that are under 50 metres apart but share no prefix. They exist, and finding them makes the “query the neighbours” rule feel necessary rather than arbitrary.
3. Compare index strategies in PostGIS. Load a million random points. Run a radius query with:
(a) a plain lat/lng composite index, (b) a geohash prefix, (c) a GiST index with ST_DWithin.
EXPLAIN ANALYZE all three. The row counts scanned will differ by orders of magnitude.
4. Try Redis GEO with movement. Add 100,000 points, then update 10,000 of them per second in a
loop while running GEOSEARCH queries. This is the moving-objects workload, in miniature — watch how
comfortably it handles updates compared to a B-tree-indexed table.