Geohash vs Quadtree vs S2/H3: Location Indexing for System Design

Every ride-hailing, food-delivery, quick-commerce and dating app has the same core query: given a user's latitude and longitude, find the drivers, restaurants, dark stores or people within some radius, fast, among millions of points. Swiggy, Zomato, Uber, Ola, Rapido and Blinkit-style apps all face it. This guide explains the four standard ways to index location, with hand-worked examples, runnable code and a clear rule for which to choose in a design or an interview.

Why Location Needs a Special Index

The naive query is:

SELECT id FROM restaurants
WHERE lat BETWEEN 12.95 AND 12.99
  AND lng BETWEEN 77.57 AND 77.61;

A B-tree index on lat narrows to a horizontal band across the whole country at that latitude, then scans it for matching longitudes. A composite index on (lat, lng) does not help much either, because B-trees order by the first column; the second only sorts ties. You need a structure that keeps points close in 2-D space close in the index. Two families exist:

• Space-filling-curve encodings (geohash, S2, H3): map each location to a cell ID such that nearby locations usually have nearby IDs. Then any 1-D index (B-tree, sorted set, key-value store) works.
• Spatial trees (quadtree, R-tree, k-d tree, BKD tree): partition space hierarchically and search the tree. PostGIS uses R-tree-like GiST indexes; Elasticsearch and Lucene use BKD trees for geo points.

How Geohash Works, Step by Step

Geohash repeatedly halves the world. Starting with longitude range [−180, 180] and latitude range [−90, 90], alternate between longitude and latitude (longitude first). At each step, write 1 if the point is in the upper half and 0 if in the lower half, then shrink the range to that half. Every 5 bits become one base32 character from the alphabet 0123456789bcdefghjkmnpqrstuvwxyz (no a, i, l, o).

Worked example: central Bengaluru (12.9716° N, 77.5946° E)

First five bits: 11001 = 25, and index 25 in the alphabet is t. Continuing gives tdr1v9qtj at 9 characters. A point in Koramangala (12.9352, 77.6245), about 5 km away, encodes to tdr1w6u3j. They share the 4-character prefix tdr1, a cell roughly 39 km × 19.5 km, which fits: both are in Bengaluru.

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"

def encode(lat: float, lon: float, precision: int = 9) -> str:
    lat_rng, lon_rng = [-90.0, 90.0], [-180.0, 180.0]
    out, ch, nbits, even = [], 0, 0, True        # even bit -> longitude
    while len(out) < precision:
        rng, val = (lon_rng, lon) if even else (lat_rng, lat)
        mid = (rng[0] + rng[1]) / 2
        if val >= mid:
            ch, rng[0] = (ch << 1) | 1, mid
        else:
            ch, rng[1] = ch << 1, mid
        even = not even
        nbits += 1
        if nbits == 5:
            out.append(BASE32[ch])
            ch, nbits = 0, 0
    return "".join(out)

def decode_bbox(gh: str):
    lat_rng, lon_rng, even = [-90.0, 90.0], [-180.0, 180.0], True
    for c in gh:
        bits = BASE32.index(c)
        for shift in range(4, -1, -1):
            rng = lon_rng if even else lat_rng
            mid = (rng[0] + rng[1]) / 2
            if (bits >> shift) & 1:
                rng[0] = mid
            else:
                rng[1] = mid
            even = not even
    return lat_rng, lon_rng           # cell bounds

print(encode(12.9716, 77.5946))   # tdr1v9qtj
print(encode(12.9352, 77.6245))   # tdr1w6u3j
print(decode_bbox("tdr1"))

Each character adds 5 bits, alternating which axis gets the extra bit, so cells alternate between roughly square and 2:1 rectangles. Because the encoding is just a string, you can store it in a MySQL column with a B-tree index, a DynamoDB sort key, a Cassandra clustering column, or a Redis sorted set, and do LIKE 'tdr1v%' or range scans.

Geohash Precision Table

Approximate cell dimensions at the equator (cells get narrower in longitude as you move toward the poles):

Bengaluru sits at ~13° N, so cos(13°) ≈ 0.97 and the widths are barely smaller than at the equator. In Srinagar (~34° N) longitude widths shrink by about 17%.

Neighbor Queries and the Edge Problem

The appealing idea "same prefix means nearby" is only half true. The converse fails: nearby points can have different prefixes. Two points on either side of a cell boundary may differ in an early character. The extreme case: (0.0001, 0.0001) encodes to s00000, while (−0.0001, −0.0001), about 30 meters away, encodes to 7zzzzz. No common prefix at all.

The standard nearby-search algorithm

1. Choose precision so the cell is at least as large as the search radius (length 6 for ~1 km).
2. Compute the user's cell and its 8 neighbors (libraries provide neighbors(); you can also compute them by decoding the bbox and encoding points just outside each edge).
3. Fetch candidates from all 9 cells: 9 prefix lookups or range scans.
4. Filter by exact distance (haversine) and sort. The 9-cell area is larger than the circle, so some candidates are discarded.
5. If too few results, drop one character (cells 32× larger) and repeat.

from math import radians, sin, cos, asin, sqrt

def haversine_km(lat1, lon1, lat2, lon2):
    dlat, dlon = radians(lat2 - lat1), radians(lon2 - lon1)
    a = sin(dlat / 2) ** 2 + cos(radians(lat1)) * cos(radians(lat2)) * sin(dlon / 2) ** 2
    return 2 * 6371.0 * asin(sqrt(a))

print(round(haversine_km(12.9716, 77.5946, 12.9352, 77.6245), 2))   # ~5.2 km

Other geohash weaknesses: cells are not equal-area across latitudes; the Z-order curve has jumps, so a range of geohash strings is not one compact region; and density is ignored, so a cell in Koramangala may hold thousands of restaurants while a cell over the Thar desert holds none.

Quadtrees: Adaptive Cells for Uneven Density

A point quadtree starts with one square covering the area. When a node holds more than a capacity (say 100 points), it splits into four children (NW, NE, SW, SE) and pushes its points down. Dense areas end up deep with tiny cells; sparse areas stay shallow.

class QuadTree:
    CAPACITY = 4                                     # tiny, for illustration

    def __init__(self, x0, y0, x1, y1):
        self.bounds = (x0, y0, x1, y1)               # lon_min, lat_min, lon_max, lat_max
        self.points = []                             # (lon, lat, payload)
        self.children = None

    def _contains(self, x, y):
        x0, y0, x1, y1 = self.bounds
        return x0 <= x < x1 and y0 <= y < y1

    def _intersects(self, qx0, qy0, qx1, qy1):
        x0, y0, x1, y1 = self.bounds
        return not (qx1 < x0 or qx0 >= x1 or qy1 < y0 or qy0 >= y1)

    def insert(self, x, y, payload):
        if not self._contains(x, y):
            return False
        if self.children is None:
            if len(self.points) < self.CAPACITY:
                self.points.append((x, y, payload))
                return True
            self._split()
        return any(c.insert(x, y, payload) for c in self.children)

    def _split(self):
        x0, y0, x1, y1 = self.bounds
        mx, my = (x0 + x1) / 2, (y0 + y1) / 2
        self.children = [QuadTree(x0, my, mx, y1), QuadTree(mx, my, x1, y1),
                         QuadTree(x0, y0, mx, my), QuadTree(mx, y0, x1, my)]
        for p in self.points:
            any(c.insert(*p) for c in self.children)
        self.points = []

    def query(self, qx0, qy0, qx1, qy1, out=None):
        out = [] if out is None else out
        if not self._intersects(qx0, qy0, qx1, qy1):
            return out                               # prune whole subtree
        for x, y, p in self.points:
            if qx0 <= x <= qx1 and qy0 <= y <= qy1:
                out.append(p)
        for c in self.children or []:
            c.query(qx0, qy0, qx1, qy1, out)
        return out

qt = QuadTree(68.0, 6.0, 98.0, 37.0)                 # rough bounding box of India
for i, (lon, lat) in enumerate([(77.5946, 12.9716), (77.6245, 12.9352),
                                (72.8777, 19.0760), (77.2090, 28.6139),
                                (77.64, 12.97), (77.60, 12.98)]):
    qt.insert(lon, lat, f"place-{i}")
print(qt.query(77.55, 12.90, 77.70, 13.00))          # Bengaluru places only

Quadtree trade-offs

• Pros: adapts to density, so "nearest 20 restaurants" works equally well in Mumbai and rural Rajasthan; supports k-nearest-neighbor search by expanding outward.
• Cons: usually lives in memory on application servers (rebuild on startup or load from a snapshot); not natively supported by most databases; frequent updates for moving objects cause splits and merges and need locking.
• Memory math: 200M places × (8-byte ID + 16 bytes of coordinates) ≈ 4.8 GB plus node overhead; fits on one large server, replicated for read throughput. The classic proximity-service design uses exactly this; see Design a Proximity Service.

Google S2: Hilbert Curves on a Cube

S2 (the open-source S2 Geometry library from Google) fixes geohash's two big flaws, polar distortion and locality jumps:

1. Project the sphere onto a cube. The six faces each cover part of the Earth with modest distortion and no singularities at the poles.
2. Subdivide each face as a quadtree down to 30 levels (level 0 = a whole face, level 30 ≈ 1 cm²).
3. Order cells along a Hilbert curve. Unlike geohash's Z-curve, the Hilbert curve never jumps: consecutive cell IDs are always spatially adjacent, so ranges of IDs map to compact regions more often.
4. Encode as a 64-bit integer: 3 bits for the face, then position along the curve, then a level marker. All descendants of a cell fall in a contiguous ID range, so "everything inside this cell" is one range scan.
5. Region coverer: approximate any circle or polygon (a delivery zone, a city boundary) with a small set of cells of mixed levels. "Points in zone" becomes a handful of ID range scans.

S2 is the stronger choice for global data, polygons (geofences, serviceability zones) and accurate spherical geometry. The cost is complexity: IDs are not human-readable and the library is heavier. MongoDB's 2dsphere index is built on S2, and Google's own products use it widely.

Uber H3: Hierarchical Hexagons

H3, open-sourced by Uber in 2018, tiles the globe with hexagons (plus exactly 12 pentagons per resolution, unavoidable on a sphere) based on an icosahedron projection. It has 16 resolutions (0 to 15); each step down has roughly 7× smaller cells.

(Values are rounded averages from the H3 documentation; actual cells vary somewhat by location.)

Why hexagons?

• Equidistant neighbors. A square has 4 edge neighbors and 4 corner neighbors at different distances; a hexagon's 6 neighbors are all the same distance from its center. Smoothing and gradients ("demand is spilling into adjacent cells") become uniform.
• k-rings. "All cells within k steps" is a clean, near-circular disk, which makes radius approximations simple.
• Better for movement and flow analysis: a vehicle moving in any direction crosses edges, never ambiguous corners.

The trade-off: hexagons cannot be perfectly subdivided into smaller hexagons, so H3 parent-child containment is approximate. For exact hierarchical containment, S2's squares are cleaner. H3 is the go-to for analytics and marketplace dynamics: surge pricing, ETA modeling, demand forecasting, heatmaps in ride-hailing and delivery. See how surge and matching use it in Design Uber / Ola.

Geohash vs Quadtree vs S2 vs H3: Side by Side

Which Systems Use What

• Redis GEO (GEOADD, GEOSEARCH): stores a 52-bit interleaved geohash-style integer as the sorted-set score; searches the center area and neighbors, then filters by distance. More in Redis Deep Dive.
• MongoDB: 2dsphere indexes use S2 cells.
• Elasticsearch / OpenSearch: geo_point fields are indexed with BKD trees; geohash and geotile grid aggregations are available for bucketing.
• PostgreSQL + PostGIS: R-tree-style GiST indexes with full spatial SQL (ST_DWithin, polygons, routing extensions).
• Uber: created and open-sourced H3 for its marketplace and analytics.
• Google: created S2; used across its geo products.

Which index a specific Indian company runs internally is mostly not public, so in interviews, reason from requirements rather than claiming "Swiggy uses X".

Static Places vs Moving Objects

The single most important distinction in location system design is whether points move.

Static: restaurants, stores, ATMs

• Updated rarely (a new restaurant per minute is nothing). Reads dominate heavily.
• Options: a quadtree in memory rebuilt periodically; or geohash/S2 columns in a database with read replicas; or PostGIS/Elasticsearch if you also need filters (cuisine, rating, open now).
• Cache results per geohash-6 cell plus filter combination; nearby searches from users in the same cell share results.

Moving: drivers, delivery partners

• Each driver sends a location every few seconds. 500K online drivers updating every 4 s = 125K writes/s, all of which overwrite the previous value.
• Do not rebuild trees; use a cell → set of drivers map in memory or Redis. On update, if the driver's cell changed, remove from the old cell and add to the new one; also keep driver → latest location with a TTL so stale drivers disappear.
• Shard by city or by coarse geohash/H3 cell so each shard handles a region; driver matching is local anyway.
• Persist the location stream to Kafka for trip tracking and analytics instead of writing every ping to a database.

# driver pings (overwrite in place)
GEOADD drivers:blr 77.5946 12.9716 driver:881
GEOADD drivers:blr 77.6245 12.9352 driver:902
SET driver:881:alive 1 EX 15          # liveness: expires if pings stop

# rider at Indiranagar wants drivers within 2 km, nearest first
GEOSEARCH drivers:blr FROMLONLAT 77.6408 12.9784 BYRADIUS 2 km ASC COUNT 20 WITHDIST

Note that GEO members do not expire individually, so stale drivers must be removed with ZREM when liveness keys expire or by a periodic sweep. These patterns appear in Design Swiggy / Zomato, and the routing side in Design Google Maps.

How Location Indexing Comes Up in Interviews

Expect it inside "Design Uber", "Design Swiggy", "Design Yelp/nearby places", "Design Tinder" or "Design a geofencing service". Interviewers look for:

1. Recognizing the 2-D problem and explaining why a lat/lng B-tree index is insufficient.
2. Explaining one technique properly, usually geohash or quadtree, including the boundary problem and the 9-cell fix.
3. Choosing precision from the radius and doing the exact-distance filter.
4. Separating static from moving data and doing the write-rate math for location updates.
5. Knowing when S2/H3 fit: polygons and global scale (S2), aggregation and pricing (H3).

Follow-up questions to prepare

• "The user is right on a cell boundary. Do you miss results?" (No: you search the 8 neighbors.)
• "Search returns 3 results in a village and 5,000 in Koramangala. Fix it." (Adaptive: quadtree, or expand/shrink geohash precision until the candidate count is in range.)
• "How do you check if a delivery address is within a store's serviceable polygon?" (S2 covering or H3 polyfill to precompute cells, then point-in-polygon for boundary cells; or PostGIS.)
• "How would you shard the driver location service?" (By city or coarse cell; handle drivers crossing shard boundaries by moving them between shards on update.)
• "How would you compute surge pricing?" (Aggregate open requests and available drivers per H3 resolution-8 cell over a sliding window; smooth over k-ring neighbors.)

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.