Design a Proximity Service: Geohash vs Quadtree

"Find the twenty nearest cafés" is a classic system design prompt that hides one hard question: how do you index a position? A place has a latitude and a longitude, and a B-tree sorts by one key. An index on latitude finds a thin band around the planet, most of it thousands of kilometres away. The expected answer folds two dimensions into one sortable key, and knows where that fold lies.

The problem it solves

Given a point and a radius, return the nearest places, ranked by distance. With the lesson's numbers and illustrative assumptions:

• Fifty million places, changing slowly: a new café is an insert, not a stream.
• Reads dominate. Every map pan and every "near me" tap is a search.
• Latency matters. The list should appear while the user is still looking at the map.

Measuring the distance to all fifty million rows is correct and hopeless. The index has to narrow the search to a few hundred candidates first.

The intuition

A geohash halves the world by longitude, then by latitude, alternating, and records which side the point fell on each time. Every five bits become one base-32 character. Two properties make it an index key:

• A longer hash is a smaller box. Five characters describe a cell about 4.9 km tall; seven characters, about 150 m.
• A shared prefix means a shared box. Every place whose hash starts with u33db lies inside the same cell, so "everything in this cell" becomes WHERE geohash LIKE 'u33db%', a plain range scan on an ordinary sorted index.

The search then has three steps. Encode the query point and trim the hash to a length whose cell is at least as big as the radius. Scan that cell and its eight neighbours. Compute true distances only for the candidates, sort and cut.

The neighbours are not optional. Two places metres apart across a cell edge can share a much shorter prefix, or none at all: either side of the prime meridian, the hashes start with e and s.

The other classic answer is a quadtree: whenever a square holds more than a few places, split it into four. Empty desert stays one big leaf and a busy city centre splits many levels deep, so every leaf holds a similar number of places. A fixed geohash grid cannot do that.

Watch it run

The animation begins with fifty million places, each position two numbers that no single sorted index can order by. So at write time each place is folded into one string that encodes its square, and nearby places share leading characters. A search arrives: a point, and a radius the user never thinks about. The point is encoded too, then trimmed; fewer characters means a bigger box. Everything in that square is a prefix match, an ordinary range scan, and it finds two places. But the third place is metres away across a cell edge and falls outside the prefix. So the eight surrounding squares are scanned as well: nine cheap scans. Only the survivors are measured, sorted by distance and cut to twenty. The last frame is the bill: a fixed grid is one square for a desert and one for a city centre, and a quadtree splits only the busy ones.

The code

A geohash encoder, checked against a published example, and cell sizes for five to seven characters. The last lines show the edge problem in Berlin and on the prime meridian:

import math

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"

def encode(lat, lon, length):
    """Geohash: interleave longitude and latitude bits, five bits per character."""
    box = [-90.0, 90.0, -180.0, 180.0]             # lat_lo, lat_hi, lon_lo, lon_hi
    out, value, bit = [], 0, 0
    while len(out) < length:
        i, x = (2, lon) if bit % 2 == 0 else (0, lat)   # even bits split longitude
        mid = (box[i] + box[i + 1]) / 2
        value = value * 2 + (x >= mid)
        box[i + (x < mid)] = mid                   # keep the half that holds x
        bit += 1
        if bit % 5 == 0:
            out.append(BASE32[value])
            value = 0
    return "".join(out)

def cell_size(length):
    """Degrees of latitude and longitude one cell spans."""
    lat_bits, lon_bits = 5 * length // 2, (5 * length + 1) // 2
    return 180 / 2 ** lat_bits, 360 / 2 ** lon_bits

print(encode(57.64911, 10.40744, 11))              # u4pruydqqvj
KM_PER_DEG = 6371.0 * math.pi / 180
for n in (5, 6, 7):
    dlat, dlon = cell_size(n)
    print(n, round(dlat * KM_PER_DEG, 3), "x", round(dlon * KM_PER_DEG, 3), "km at the equator")
# 5 4.886 x 4.886 km at the equator
# 6 0.611 x 1.222 km at the equator
# 7 0.153 x 0.153 km at the equator

print(encode(52.52, 13.4031, 7), encode(52.52, 13.4035, 7))    # 27 m apart in Berlin
# u33dbbz u33dc0b
print(encode(0.0001, -0.0001, 7), encode(0.0001, 0.0001, 7))    # 22 m apart on the meridian
# ebpbpbp s000000

A toy model of the service: a sorted list stands in for the B-tree, and bisect does the prefix range scan. The precision is the longest prefix whose cell is at least the radius tall and wide at the query's latitude, so nine cells always cover the circle:

from bisect import bisect_left

def haversine_km(a, b):
    (la1, lo1), (la2, lo2) = [(math.radians(x), math.radians(y)) for x, y in (a, b)]
    h = math.sin((la2 - la1) / 2) ** 2 + math.cos(la1) * math.cos(la2) * math.sin((lo2 - lo1) / 2) ** 2
    return 2 * 6371.0 * math.asin(math.sqrt(h))

class GeoIndex:
    """Toy model: a sorted list of (geohash, id) stands in for a B-tree index."""
    def __init__(self, places, length=9):
        self.places, self.length = places, length
        self.rows = sorted((encode(lat, lon, length), pid) for pid, (lat, lon) in places.items())
        self.keys = [h for h, _ in self.rows]

    def prefix_scan(self, prefix):                 # WHERE geohash LIKE 'u33db%'
        i = bisect_left(self.keys, prefix)
        while i < len(self.rows) and self.keys[i].startswith(prefix):
            yield self.rows[i][1]
            i += 1

    def precision_for(self, lat, radius_km):
        """Longest prefix whose cell is at least radius_km tall and wide here."""
        need_lat = math.degrees(radius_km / 6371.0)
        s = math.sin(radius_km / 6371.0) / math.cos(math.radians(lat))
        need_lon = math.degrees(math.asin(min(1.0, s)))
        n = self.length
        while n > 1 and (cell_size(n)[0] < need_lat or cell_size(n)[1] < need_lon):
            n -= 1
        return n

    def nearby(self, lat, lon, radius_km, k, neighbours=True):
        n = self.precision_for(lat, radius_km)
        dlat, dlon = cell_size(n)
        steps = (-1, 0, 1) if neighbours else (0,)
        cells = {encode(max(-89.9999, min(89.9999, lat + i * dlat)),
                        (lon + j * dlon + 180) % 360 - 180, n)
                 for i in steps for j in steps}    # the cell and its eight neighbours
        found = [(haversine_km((lat, lon), self.places[p]), p)
                 for c in cells for p in self.prefix_scan(c)]
        return sorted(x for x in found if x[0] <= radius_km)[:k], sorted(cells)

places = {"cafe": (52.5200, 13.4010), "bar": (52.5206, 13.4022), "deli": (52.5199, 13.4041),
          "museum": (52.5163, 13.3777), "zoo": (52.5079, 13.3377)}
idx = GeoIndex(places)
best, cells = idx.nearby(52.5201, 13.4028, 1.0, 20, neighbours=False)
print(cells, [p for _, p in best])
# ['u33db'] ['bar', 'cafe']
best, cells = idx.nearby(52.5201, 13.4028, 1.0, 20)
print(len(cells), [(p, round(d * 1000)) for d, p in best])
# 9 [('bar', 69), ('deli', 91), ('cafe', 122)]

With one cell, the deli 91 m away is missed because it sits in u33dc; with nine, it is second. A quadtree on a seeded map with 2,000 places in a small "city" and 40 in a "desert", splitting any square with more than eight:

def quadtree_depths(points, box, capacity=8, depth=0):
    """Split a square only while it holds more than `capacity` points."""
    if len(points) <= capacity:
        return [depth]
    (x0, y0, x1, y1), mx, my = box, (box[0] + box[2]) / 2, (box[1] + box[3]) / 2
    out = []
    for q in ((x0, y0, mx, my), (mx, y0, x1, my), (x0, my, mx, y1), (mx, my, x1, y1)):
        inside = [(x, y) for x, y in points if q[0] <= x < q[2] and q[1] <= y < q[3]]
        out += quadtree_depths(inside, q, capacity, depth + 1)
    return out

import random
random.seed(29)
city = [(random.uniform(0.40, 0.41), random.uniform(0.40, 0.41)) for _ in range(2_000)]
desert = [(random.uniform(0, 1), random.uniform(0, 1)) for _ in range(40)]
d = quadtree_depths(city + desert, (0, 0, 1, 1))
print(len(d), "leaves, depth", min(d), "to", max(d))
# 586 leaves, depth 2 to 12

Checked on 300 seeded random maps between 70° south and 70° north, with 1,500 queries of radius 50 m to 5 km, against a brute force that measures the distance to every place:

random.seed(29)
ok = True
for _ in range(300):
    clat, clon = random.uniform(-70, 70), random.uniform(-179, 179)
    spread = random.choice([0.01, 0.05, 0.3])
    pts = {i: (clat + random.uniform(-spread, spread), clon + random.uniform(-spread, spread))
           for i in range(random.randint(1, 80))}
    gi = GeoIndex(pts)
    for _ in range(5):
        q = (clat + random.uniform(-spread, spread), clon + random.uniform(-spread, spread))
        r, k = random.choice([0.05, 0.3, 1.0, 5.0]), random.randint(1, 10)
        want = sorted((haversine_km(q, p), i) for i, p in pts.items() if haversine_km(q, p) <= r)[:k]
        ok &= gi.nearby(q[0], q[1], r, k)[0] == want          # brute force: every place
print(ok)                                                        # True

The complexity

• Write: one encode, O(L) for a hash of length L, plus one index insert, O(log n).
• Read: nine range scans, each O(log n + c) for c rows in the cell, then O(m log m) to sort the m candidates. The cost follows cell density, not world size.
• Memory: with an illustrative 40 bytes per index entry, fifty million places is about 2 GB, small enough to replicate to every read node.

Where it goes wrong

• Scanning only the centre cell. Anything just across an edge is missed, as the deli shows.
• A precision chosen for the wrong latitude. A cell 4.9 km wide at the equator is about 3 km wide in Berlin.
• Dense cells. A fixed grid puts thousands of places in one downtown cell. Use a longer prefix there, or a quadtree.
• Ranking by hash similarity. Similar strings are not a distance; measure the candidates.
• Sharding by region. A city becomes a hot shard; a small read-mostly index is easier to replicate than to split, as in database sharding.

As of September 2026, production systems often use ready-made cell schemes, such as hexagonal or sphere-curve cell ids, or the geo commands of common databases; the design questions are the same.

When it shows up in interviews

As "design a proximity service", "design a nearby-restaurants search", or the matching step of a ride-hailing design, where drivers move and the index is rewritten every few seconds. The coding cousin is k closest points, the final ranking step on its own. Follow-ups ask about caching popular cells and spreading the index over machines.

How to say it in an interview

"The hard part is indexing two dimensions with a one-dimensional index. I store a geohash per place, so a shared prefix means a shared cell and a cell search is a prefix range scan on a normal B-tree. For a query I trim the point's hash to a cell at least as big as the radius and scan it plus its eight neighbours, because nearby places can sit across an edge. Then I compute real distances for the candidates, sort and take twenty. If density varies a lot, a quadtree splits only busy squares. The index is small and read-heavy, so I replicate it."