Quadtrees and Geohashes: How Apps Find Nearby Riders Fast

It gets slower as the city grows, because every search measures the distance to every rider. A normal database index helps only a little, because a location is two numbers, not one. Geohash quadtree indexing fixes that by filing points by place.

Picture a common setup. A bike-taxi app in Pune must offer the nearest free rider within a couple of seconds of a customer tapping Book. The setup is made up, but the problem is real.

At the evening peak, about 6,000 riders are online. Each rider's phone sends its location every 4 seconds. Customers send about 200 booking requests a second.

The naive first version loads every free rider, works out each distance, sorts the list and picks the closest. That is 6,000 distance sums per booking, or 12 lakh (1.2 million) a second at peak.

The second try adds a normal database index on latitude and then longitude. A normal index is a sorted copy of some columns, usually a B-tree (a sorted tree structure), that lets the database jump straight to a range of values.

The query asks for riders within about 1 km north, south, east and west of the customer. It gets faster, but much less than hoped. The reason is the heart of this guide.

An index sorted by latitude first can jump only to a latitude range. That range is a thin band running across the whole city, east to west. The database then checks each rider in the band for longitude, one by one.

The app also needs three things:

• The nearest free rider on screen in under 2 seconds, network time included.
• Speed at 6 p.m., when riders crowd around the Hinjewadi IT park and the outskirts are nearly empty.
• Fresh positions, since a bike at 20 km/h covers about 330 metres a minute.

So riders who are close on the map must also sit close together in the index. That is exactly the job of a spatial index.

It cuts the map into boxes, files each point under its box, and answers a nearby search by reading only the boxes around the user. Then it measures real distances to the few points it found.

A spatial index is any data structure that groups points by where they sit on a map. That lets a search skip far-away points without reading them. Geohashes and quadtrees are two common ones.

Latitude and longitude. Latitude says how far north or south a place is, from -90 to 90 degrees. Longitude says how far east or west, from -180 to 180 degrees. Swargate in Pune is roughly latitude 18.50, longitude 73.86.

Cell. A cell is one box on the map that the index treats as a unit. At a given box size, every point belongs to exactly one cell.

Nearby query. A nearby query asks for the points within some distance of a spot, or for the few closest ones. Example: the five free riders closest to a customer at Swargate.

Think about how a census is counted. The office does not send one enumerator (a person who counts households) to walk the whole town. It splits the town into wards, each ward into blocks, and each block into pieces one person can count.

Map the parts. The town is the map, a block is a cell, and a block code like 14-3 is a geohash. Code 14-3-2 sits inside block 14-3, just as a longer geohash sits inside any shorter code it starts with. A crowded block cut into more pieces is a quadtree splitting a box.

Where the picture breaks: census blocks follow roads and are drawn by people. Geohash cells are exact slices of latitude and longitude, so a cell line can cut straight through a building.

A geohash halves the map again and again, writes a bit (a 0 or 1) for the half the point falls in, then turns those bits into letters and digits. Each extra character makes the box smaller.

Start with the whole world. Cut it down the middle from top to bottom. Pune is east of that line, so the first bit is 1. Now cut the world across the equator. Pune is north of it, so the second bit is also 1.

Keep going, switching between east-west and north-south cuts. After every five bits, look up one character in a 32-character alphabet. It uses the digits 0 to 9 and the lowercase letters, except a, i, l and o.

Notice that two cuts split a box into four. So a geohash is really a quadtree with the same depth everywhere, written as a string. That is why the two ideas belong in one guide.

Here is a geohash encoder in plain Python, with no libraries. It takes a latitude, a longitude and a length, and returns the code.

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"   # no a, i, l or o

def geohash(lat, lon, length=6):
    lat_range, lon_range = [-90.0, 90.0], [-180.0, 180.0]
    bits = []
    while len(bits) < length * 5:
        use_lon = len(bits) % 2 == 0          # even bits: longitude
        rng, value = (lon_range, lon) if use_lon else (lat_range, lat)
        mid = (rng[0] + rng[1]) / 2
        if value >= mid:
            bits.append("1")
            rng[0] = mid                      # keep the upper half
        else:
            bits.append("0")
            rng[1] = mid                      # keep the lower half
    groups = ["".join(bits[i:i + 5]) for i in range(0, len(bits), 5)]
    return "".join(BASE32[int(g, 2)] for g in groups)

Three parts matter. The use_lon line alternates the cut, starting with longitude. The two rng updates keep only the half that holds the point, so the box shrinks with every bit. The last line packs each group of five bits into one character.

Run it for Swargate at 18.5018, 73.8636 and you get tek92b. Ask for seven characters and you get tek92b1, a smaller box inside tek92b. The shared start of two codes is called a prefix, so tek92b is a prefix of tek92b1.

How big is each box? The Elasticsearch documentation gives these sizes, measured at the equator, where cells are widest:

• 5 characters: about 4.9 km by 4.9 km.
• 6 characters: about 1.2 km wide by 609 m tall.
• 7 characters: about 153 m by 152 m.
• 8 characters: about 38 m by 19 m.

Even lengths give both axes the same number of bits. Longitude spans 360 degrees and latitude only 180, so those cells are about twice as wide as tall. At odd lengths longitude gets one extra bit, so cells are nearly square.

Away from the equator, cells get narrower from east to west, by the cosine of the latitude. Pune sits about 18.5 degrees north, and the cosine of 18.5 degrees is 0.948. So Pune's cells are about 5 percent narrower than these numbers.

You compute the customer's geohash, fetch riders from that cell and the eight cells around it, then measure exact distances and keep the closest. That is always nine lookups, however big the city is. The candidates grow only with how crowded those nine cells are.

The app stores each free rider's 6-character geohash in a cell column next to the rider's ID, with a normal index on that column. Fetching nine cells is nine quick indexed lookups instead of a scan.

Here is the lookup for one booking at Swargate. Follow it from the customer's tap to the chosen rider.

Why search the eight neighbouring cells?

A customer standing near the edge of a cell may have a rider 50 metres away in the next cell. Search only the customer's own cell, and you miss that rider. You might offer one 500 metres away instead.

The prefix rule also works only one way. A shared prefix means two points are in the same box. But two close points on either side of a box line can have quite different geohashes.

Pause and predict. Kothrud and Deccan Gymkhana are about 4 km apart, and Kothrud and Hinjewadi about 12 km. Which pair shares the longer geohash prefix?

Pune shows this, using rough centre points for each area. Kothrud's geohash starts tek3r and Deccan Gymkhana's starts tek92, though they are about 3.7 km apart. Hinjewadi starts tek3v, sharing four characters with Kothrud, though it is about 12 km away.

The worst case is a major line such as the equator. Two points 22 metres apart on either side of it, at longitude 73.86, get t8h808 and mxuxbx. They share no prefix at all.

So never treat the length of a shared prefix as a distance. Use cells only to collect candidates, then measure.

Finding the eight neighbours is simpler than it looks. Every cell of one length is the same size in degrees. So step one cell height or width away from the user and encode again.

def cell_size(length):
    lat_bits = length * 5 // 2                # longitude gets the odd bit out
    lon_bits = length * 5 - lat_bits
    return 180 / 2 ** lat_bits, 360 / 2 ** lon_bits   # height, width in degrees

def nine_cells(lat, lon, length=6):
    h, w = cell_size(length)
    cells = set()
    for dy in (-1, 0, 1):
        for dx in (-1, 0, 1):
            y = lat + dy * h
            if -90 <= y <= 90:
                x = (lon + dx * w + 180) % 360 - 180      # wrap at 180 degrees
                cells.add(geohash(y, x, length))
    return cells

The cell_size function splits the bits between the axes, as the encoder does. The modulo line wraps longitude at 180 degrees, where the map's east and west edges meet. Rows past a pole are skipped.

For Swargate, nine_cells returns tek92b and eight neighbours, from tek90x to tek931. In our test it matched pygeohash 3.5.1's get_adjacent function on 20,000 random points.

Choose the cell size from the search radius

Choose a geohash length whose cell, at your latitude, is at least as tall and as wide as your search radius. Then the 3 by 3 block of cells around the customer holds every point within that radius.

The reason is simple. A point within the radius is at most one cell width away east or west, and at most one cell height away north or south. So it lands in the customer's cell or a neighbour.

In Pune, a 6-character cell is about 1.16 km wide and 0.61 km tall. So the app can safely search 500 metres with it. If it finds fewer than three free riders, it switches to 5-character cells, about 4.6 km wide, and searches 3 km.

How Redis does this for you

You do not always have to build this yourself. Redis, a popular in-memory data store, has geo commands. GEOADD stores points in a sorted set, a collection kept in order by a number called the score.

The Redis documentation says the score is a 52-bit integer made by interleaving latitude and longitude bits. It is a variant of geohash: Redis uses latitude limits of about plus or minus 85.05 degrees instead of 90, so the raw score is not a standard geohash. The GEOHASH command converts it back to the standard string. A radius or box search checks the 1 plus 8 areas that cover the shape, then drops points outside it.

Distances use the Haversine formula, which treats Earth as a sphere. The docs say the error can reach 0.5 percent in the worst case. Valid latitudes run only from -85.05112878 to 85.05112878 degrees.

As of 19 October 2026, the docs list GEOSEARCH, available since Redis 6.2.0, as the replacement for the deprecated GEORADIUS. Here is a session we ran on Redis 7.0.15, shown as redis-cli prints it in a terminal:

$ redis-cli GEOADD riders 73.8636 18.5018 r1 73.8660 18.5040 r2 73.8077 18.5074 r3
(integer) 3
$ redis-cli GEOHASH riders r1
1) "tek92b1uf90"
$ redis-cli GEOSEARCH riders FROMLONLAT 73.8636 18.5018 BYRADIUS 500 m ASC WITHDIST
1) 1) "r1"
   2) "0.2759"
2) 1) "r2"
   2) "352.1571"
$ redis-cli GEOADD riders 0 86 polar
(error) ERR invalid longitude,latitude pair 0.000000,86.000000

Notice r1 is 0.2759 metres from its own position. Redis keeps each point only as its 52-bit score, so a stored position can be off by a fraction of a metre. The latitude 86 point is refused, as the docs say.

A quadtree is a tree of boxes on the map, where any box holding too many points splits into four smaller boxes. Crowded areas end up with many small boxes, and empty areas keep a few big ones.

The quadtree name goes back to a 1974 paper by Raphael Finkel and Jon Bentley in Acta Informatica. Their structure was built for records searched on composite keys, meaning two or more keys at once, such as a latitude and a longitude.

This guide uses the region quadtree, the version most system design answers mean. It always splits a box into four equal quarters at its middle.

Say the app's rule is that a box may hold at most 50 riders. At 6 p.m., the IT park in Hinjewadi fills with riders waiting for office crowds, so its box splits several times. Boxes over the hills at the city's edge stay large and nearly empty.

You build a quadtree by inserting points one at a time and splitting any box that goes over its limit. You search it by visiting only the boxes that overlap your search circle, and skipping the rest.

Here is an insert in Python. Each rider object has x for longitude and y for latitude. A Block holds its corners, its riders and, once split, its four kids (child boxes).

class Block:
    def __init__(self, x0, y0, x1, y1, cap=50, min_size=0.0005):
        self.box, self.cap, self.min_size = (x0, y0, x1, y1), cap, min_size
        self.riders, self.kids = [], []

    def insert(self, rider):                  # rider.x = longitude, rider.y = latitude
        x0, y0, x1, y1 = self.box
        mx, my = (x0 + x1) / 2, (y0 + y1) / 2
        if self.kids:                         # already split: pass it down
            return self.kids[(rider.x >= mx) + 2 * (rider.y >= my)].insert(rider)
        self.riders.append(rider)
        if len(self.riders) > self.cap and x1 - x0 > self.min_size:   # too crowded
            self.kids = [Block(*b, self.cap, self.min_size) for b in
                         [(x0, y0, mx, my), (mx, y0, x1, my), (x0, my, mx, y1), (mx, my, x1, y1)]]
            crowd, self.riders = self.riders, []
            for r in crowd:
                self.insert(r)                # now goes down to a child

The key line picks a child with (rider.x >= mx) + 2 * (rider.y >= my). In Python, True counts as 1, so this gives 0, 1, 2 or 3. That means bottom-left, bottom-right, top-left or top-right, the same order as the kids list.

When a box overflows, it makes four kids and inserts its riders again, and they now flow down. The min_size check stops splitting once a box is 0.0005 degrees wide or less, about 53 metres in Pune.

That check is not optional. In our test on Python 3.13, 51 riders on the exact same spot without it raised RecursionError. With it, they simply share one leaf.

Searching uses the same tree from the top down. To find riders within 500 metres of a customer, the search follows these steps:

1. 1

   Start at the root

   Check whether the root box overlaps the 500 metre circle around the customer. It always does, because the root covers all of Pune.

2. 2

   Skip boxes that miss the circle

   For each child, test whether it overlaps the circle. A box fully outside it is skipped, along with everything under it.

3. 3

   Collect riders from leaf boxes

   A leaf is a box with no kids. In each overlapping leaf, measure every rider's real distance and keep those within 500 metres.

4. 4

   Sort and offer

   Sort the kept riders by distance and offer the closest free one.

Here is that search in Python. The km_between function is the Haversine formula, the same sphere model Redis uses. The checked counter records how many distances were measured, so you can see the work saved.

import math

def km_between(lat1, lon1, lat2, lon2):       # Haversine: Earth as a sphere
    p1, p2 = math.radians(lat1), math.radians(lat2)
    a = (math.sin((p2 - p1) / 2) ** 2
         + math.cos(p1) * math.cos(p2) * math.sin(math.radians(lon2 - lon1) / 2) ** 2)
    return 2 * 6371.0 * math.asin(math.sqrt(a))

def search(block, lat, lon, km, found, checked):
    dlat = km / 111.0                         # a degree of latitude is about 111.2 km
    dlon = km / (111.0 * math.cos(math.radians(lat)))
    x0, y0, x1, y1 = block.box
    if x1 < lon - dlon or x0 > lon + dlon or y1 < lat - dlat or y0 > lat + dlat:
        return found                          # box misses the circle: skip it all
    for r in block.riders:                    # only leaf boxes hold riders
        checked[0] += 1
        if km_between(lat, lon, r.y, r.x) <= km:
            found.append(r)
    for kid in block.kids:
        search(kid, lat, lon, km, found, checked)
    return found

The box test uses a square drawn around the circle, a little larger than the circle itself. It may visit a few extra boxes, but for city-sized radii away from the poles it never skips a box that could hold an answer.

Across 500 random searches of 0.2 to 3 km, the tree and the full check never disagreed. To find the nearest few riders instead, visit boxes closest-first. Stop once no unvisited box could hold anyone nearer than what you already found.

Use geohashes when the index must live in a shared database or cache that many servers read and write. Use a quadtree when crowding is very uneven and one server can hold the whole tree in memory.

The app chooses geohashes for the live rider index. Riders send 1,500 location updates a second, which is 6,000 riders every 4 seconds. Each update is one small write to a shared store that every booking server can read.

At 6 p.m., one 6-character cell near Hinjewadi can hold 400 riders (made up). The fix is 7-character cells in that area. A quadtree would make that choice on its own.

Here is the choice as a set of questions. Start at the top and answer each one for your own system.

What about the database's own spatial index?

Check your database before building either. The PostGIS workshop, for the spatial extension of PostgreSQL, describes its spatial index as an R-tree, created through PostgreSQL's generic GiST index method.

An R-tree groups shapes into rectangles, then rectangles of rectangles, and adapts to crowding on its own. Like cells, it finds candidates by box first, then runs exact checks. If your points already live in PostGIS, start there.

You re-index each point when its location changes, and remove points that stop reporting. The hard part is doing this thousands of times a second without slowing down the searches.

The app keeps the live index in Redis, because it changes 1,500 times a second. Follow the rider's location ping and the customer's booking in the diagram. Both meet at one shared index.

Four rules keep the index correct:

• Index only free riders. Remove a rider the moment they accept a booking, so the next customer is not offered someone already busy. The location service writes a ping to the geo set only while the rider is marked free.
• Keep the exact position with the cell. The cell finds candidates, and the exact position gives the real distance.
• Expire silent riders yourself. Redis's EXPIRE sets a timeout on a whole key, and the geo set is one key holding every rider.
• For a quadtree, consider building a fresh tree every few seconds and swapping it in. Then searches never read a tree that is half edited.

So the sweeper keeps a second sorted set of last-seen times, scored by when each rider last reported. Every few seconds it reads the riders silent for 30 seconds and removes them from both sets with ZREM, the Redis command that deletes members of a sorted set.

S2 and H3 are cell systems that ease some geohash weak spots. S2 builds a quadtree of cells on a cube wrapped around Earth, and H3 covers Earth mostly with hexagons.

S2 projects the six faces of a cube onto the sphere. Each face splits into four children, again and again, through levels 0 to 30. Level 30 cells are about 1 cm across.

S2 numbers its cells along a Hilbert curve, a path that winds through every cell. Cells with close numbers are close on the map, though close cells do not always get close numbers.

H3 was developed at Uber for its data science needs. It covers Earth with hexagons plus exactly 12 pentagons at every resolution, one at each corner of an icosahedron (a 20-sided solid).

H3 calls each level of cell size a resolution. Each hexagon has seven children, but the fit is approximate, because hexagons do not split cleanly into seven smaller ones. In our h3 4.5.0 test, 7.2 percent of random Pune points had a resolution-9 cell whose parent was not their resolution-8 cell.

Why hexagons? A hexagon's six neighbours all share a full edge with it. In h3 4.5.0, the six neighbour centres of one resolution-8 cell at Swargate sat 865 to 929 metres away: close, though not exactly equal on a sphere. A square's corner neighbours sit about 1.4 times farther than its edge neighbours.

For the rider app, geohash is enough today. If the team later studies how riders move across the city, H3 helps. Its docs say all neighbours of a hexagon are equidistant, which makes movement analysis simpler.

Explain them as two ways to cut the map into boxes. Then show how those boxes turn a city-wide scan into a few small lookups.

1. 1

   State the problem

   A normal index jumps to a range of one value, and a location has two. Scanning every point on every request does not scale.

2. 2

   Introduce cells

   Cut the map into boxes and store each point with its box. Search only nearby boxes, then measure real distances.

3. 3

   Explain geohash

   Halving the map again and again gives a string. A shared prefix means the same box. Pick the length from the search radius.

4. 4

   Handle edges

   Always search the 8 neighbouring cells, with cells at least as big as the radius. Say that close points can still have different prefixes.

5. 5

   Bring in the quadtree

   For very uneven crowding, boxes split when they get too full. Mention the smallest box size, the memory cost and how you update moving points.

6. 6

   Do the maths out loud

   6,000 riders sending every 4 seconds is 1,500 writes a second. Say whether one shared store handles that, or whether you split the index by city.