How do apps like Uber find nearby drivers?

They index every driver position by a spatial key, such as a geohash, S2 or H3 cell, so a search reads only the few cells around the passenger instead of every driver. The candidates are then filtered by true distance and ranked. Live positions usually sit in an in-memory store because they are rewritten every few seconds.

What is the difference between geohash and quadtree?

A geohash cuts the world into a fixed grid and encodes each cell as a short string you can store and index in any database. A quadtree is an in-memory tree that splits only crowded regions, so it adapts to density but has to be rebuilt or updated as points move. Geohash is a key, quadtree is a data structure.

Why do I need to search the 8 neighbouring geohash cells?

Two points can be metres apart and still fall in different cells, sometimes with no shared prefix at all, for example either side of the Greenwich meridian. Searching the centre cell plus its eight neighbours covers that, provided the radius is no larger than a cell edge. You then filter the results by real distance.

Is PostGIS good enough for finding nearby places?

For most apps, yes. A geography column with a GiST index and ST_DWithin answers radius queries in metres in one SQL predicate, and it keeps location data next to your other tables. Reach for Redis or a cell library only when the update rate or scale proves it is not enough.

How does Redis GEOSEARCH work for nearby search?

GEOADD stores members in a sorted set scored by a 52-bit geohash, and GEOSEARCH, available since Redis 6.2.0, returns members inside a radius or box around a point or an existing member. You can sort by distance with ASC and limit results with COUNT. It has no per-member expiry, so stale drivers must be removed separately.

Geohash vs Quadtree: How Nearby Driver Search Works

How do apps find nearby drivers or places? Geohash vs quadtree explained with TypeScript, PostGIS ST_DWithin, Redis GEOSEARCH and write-rate maths.

Key Takeaway

To find nearby drivers or places, index each position by a spatial key, not a table scan. A geohash turns coordinates into a string you can prefix-match, but the eight neighbouring cells need querying too; a quadtree adapts to density in memory. The pragmatic default is PostGIS with a GiST index and ST_DWithin, or Redis GEOSEARCH for live positions.

A ride-hailing screen shows ten cars within two kilometres, and the first version of that query is always the same: compute the distance from the passenger to every row and sort. It works with a hundred test drivers and becomes the slowest query in the system the moment the fleet is real.

This is a worked design, not a war story. I have not run a dispatch system, so every figure below is derived from stated assumptions with the arithmetic shown, and the behaviour of each tool comes from its documentation. The stack is the one I reach for on a single VPS, Postgres and Redis behind a Node service, and the TypeScript is runnable as written.

Why is a distance query on every row too slow?

Because the distance is computed from the query point, no ordinary index can answer it. A btree on lat and lng can narrow one axis at a time, but it cannot express a circle, so the planner reads everything, computes a haversine per row and sorts. The query below is correct and is exactly the version to avoid.

-- Wrong: correct, and a full table scan on every request. No index can help,
-- because the distance is computed per row from the query point.
SELECT driver_id,
       6371 * 2 * asin(sqrt(
         power(sin(radians(lat - -6.2088) / 2), 2) +
         cos(radians(-6.2088)) * cos(radians(lat)) *
         power(sin(radians(lng - 106.8456) / 2), 2)
       )) AS km
FROM   driver_positions
ORDER  BY km
LIMIT  10;

The cost is the product of two numbers you do not control, fleet size and search rate. With the assumed inputs below the naive plan does 20 million distance computations per second. Restricting the work to nine geohash cells cuts that to roughly 149 thousand, because a cell is a coarse filter that rejects most of the city before any trigonometry runs.

Assumed inputs (a design exercise, not a measurement):
  online drivers          = 100,000
  nearby searches         = 200 per second

Naive plan: every search computes a distance for every driver
  100,000 x 200           = 20,000,000 distance computations per second

Bounded plan: only drivers in 9 geohash cells (precision 6, around Jakarta)
  one cell                = 0.611 km x 1.216 km = 0.743 km2
  nine cells              = 9 x 0.743 = 6.69 km2
  city area (assumed)     = 30 km x 30 km = 900 km2
  share of the city       = 6.69 / 900 = 0.74%
  candidates (if drivers are spread evenly) = 100,000 x 0.0074 = about 743
  work per second         = 743 x 200 = 148,600 distance computations
                            (135x fewer; real drivers cluster, so test your own density)

That is the whole idea behind every technique in this post: replace two-dimensional proximity with a one-dimensional key that an index can seek on, then filter the few survivors by true distance.

How does a geohash turn coordinates into a string?

A geohash repeatedly halves the world. Each bit says which half of the longitude range, then which half of the latitude range, the point falls in, and every five bits become one character of the base32 alphabet 0123456789bcdefghjkmnpqrstuvwxyz, which skips a, i, l and o. The encoder below follows that definition and reproduces the two reference examples on the Wikipedia page, ezs42 for 42.605, -5.603 and u4pruydqqvj for 57.64911, 10.40744.

const BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"; // no a, i, l, o

export interface Bounds { latMin: number; latMax: number; lngMin: number; lngMax: number }

// Bits alternate longitude, latitude, longitude ... starting with longitude.
export function encode(lat: number, lng: number, precision = 7): string {
  let latLo = -90, latHi = 90, lngLo = -180, lngHi = 180;
  let hash = "", bits = 0, ch = 0, evenBit = true;
  while (hash.length < precision) {
    if (evenBit) {
      const mid = (lngLo + lngHi) / 2;
      if (lng >= mid) { ch = (ch << 1) | 1; lngLo = mid; } else { ch <<= 1; lngHi = mid; }
    } else {
      const mid = (latLo + latHi) / 2;
      if (lat >= mid) { ch = (ch << 1) | 1; latLo = mid; } else { ch <<= 1; latHi = mid; }
    }
    evenBit = !evenBit;
    if (++bits === 5) { hash += BASE32[ch]; bits = 0; ch = 0; }
  }
  return hash;
}

export function bounds(hash: string): Bounds {
  let latLo = -90, latHi = 90, lngLo = -180, lngHi = 180, evenBit = true;
  for (const c of hash) {
    const idx = BASE32.indexOf(c);
    if (idx === -1) throw new RangeError("invalid geohash character: " + c);
    for (let mask = 16; mask > 0; mask >>= 1) {
      const bit = (idx & mask) !== 0;
      if (evenBit) { const mid = (lngLo + lngHi) / 2; if (bit) lngLo = mid; else lngHi = mid; }
      else { const mid = (latLo + latHi) / 2; if (bit) latLo = mid; else latHi = mid; }
      evenBit = !evenBit;
    }
  }
  return { latMin: latLo, latMax: latHi, lngMin: lngLo, lngMax: lngHi };
}

// The 8 surrounding cells: step one cell height/width from the centre and re-encode.
// Longitude wraps at 180; latitude is clamped, so polar cells have fewer neighbours.
export function neighbours(hash: string): string[] {
  const b = bounds(hash);
  const h = b.latMax - b.latMin, w = b.lngMax - b.lngMin;
  const lat = (b.latMin + b.latMax) / 2, lng = (b.lngMin + b.lngMax) / 2;
  const out = new Set<string>();
  for (const dLat of [-1, 0, 1]) {
    for (const dLng of [-1, 0, 1]) {
      if (dLat === 0 && dLng === 0) continue;
      const nLat = lat + dLat * h;
      if (nLat < -90 || nLat > 90) continue;
      const nLng = ((((lng + dLng * w + 180) % 360) + 360) % 360) - 180;
      out.add(encode(nLat, nLng, hash.length));
    }
  }
  return [...out];
}

// Cells to scan for "within radiusM of here": the centre cell plus its 8 neighbours,
// valid only while radiusM is no larger than one cell edge. Then filter by true distance.
export function searchCells(lat: number, lng: number, precision: number): string[] {
  const centre = encode(lat, lng, precision);
  return [centre, ...neighbours(centre)];
}

Precision is just the string length, and each extra character shrinks the cell. The sizes below are derived from the bit counts rather than quoted: 360 and 180 degrees divided by two to the power of the bit count, times about 111.32 km per degree. They agree with the error column on Wikipedia, which lists half-widths, for example 0.61 km at length 6.

Each base32 character carries 5 bits. Bits alternate longitude, latitude, longitude...
so odd lengths give longitude one extra bit.

  precision  lat bits  lng bits  cell height   cell width at the equator
      4         10       10        19.6 km        39.1 km
      5         12       13         4.89 km        4.89 km
      6         15       15         611 m          1.22 km
      7         17       18         153 m          153 m
      8         20       20         19 m           38 m

Derivation for precision 6:
  height = 180 deg / 2^15 = 0.00549 deg  x 111.32 km per deg = 0.611 km
  width  = 360 deg / 2^15 = 0.01099 deg  x 111.32 km per deg = 1.223 km
  width shrinks with cos(latitude): at Jakarta (-6.2 deg) 1.223 x 0.9942 = 1.216 km

Two properties matter. Cells are rectangles, wider than tall at even lengths, and they narrow towards the poles because a degree of longitude shrinks with the cosine of latitude. And a shared prefix means a shared parent cell, which is what lets a plain btree or a LIKE prefix query act as a spatial index.

Why do geohash searches miss nearby points, and what are the 8 neighbours?

A shared prefix proves two points are close, but close points do not always share a prefix. Wikipedia notes that points either side of the equator, the Greenwich meridian or the 180th meridian can have little or no common prefix. The two points below sit about 14 metres apart and have completely different first characters.

import { encode, neighbours } from "./geohash";

// Two drivers about 14 m apart (0.0002 deg of longitude at 51.5 N), either side of the
// Greenwich meridian. Same street corner, no shared prefix at all:
encode(51.5, -0.0001, 6); // "gcpuzz"
encode(51.5,  0.0001, 6); // "u10hbp"

// A prefix match only finds points in the SAME cell. The fix is to ask for the cell
// the passenger is in plus its 8 neighbours:
neighbours("qqguxm"); // ["qqguxh","qqguxk","qqguxs","qqguxj","qqguxt","qqguxn","qqguxq","qqguxw"]

The standard fix is to search the passenger's own cell plus its eight neighbours, then discard anything outside the real radius. This is only correct when the radius is no larger than the smaller cell edge, since then every match must lie in the centre cell or one adjacent to it. So you choose the longest precision whose smaller edge still covers the radius: 2 km needs precision 5 at 4.89 km, while 500 m fits precision 6 at 611 m.

-- Geohash in a plain btree column: 9 equality probes, then an exact distance filter.
-- Precondition: the radius is no larger than the smaller cell edge, or 9 cells miss points.
CREATE INDEX driver_positions_gh6_idx ON driver_positions (geohash6);

SELECT driver_id
FROM   driver_positions
WHERE  geohash6 = ANY ($1)            -- the centre cell plus its 8 neighbours
  AND  haversine_km(lat, lng, $2, $3) <= 0.5;   -- the cell is a coarse filter, not the answer

Neighbour lookup in the encoder is deliberately simple: step one cell height or width from the centre and re-encode, wrapping longitude and clamping latitude. Production libraries use lookup tables for speed, but this version is easy to verify against the decoded bounds.

Store the geohash as a short text column at one fixed precision and index it with a plain btree. Nine equality probes beat a prefix scan, and the column survives a move to a different database.

How is a quadtree different from a geohash?

A quadtree splits space into four quadrants, but only where it is crowded. Per Wikipedia, each cell has a maximum capacity and splits when it is reached, so a dense city centre gets deep, small cells while an empty ocean stays one big leaf. A geohash cuts the same grid everywhere, a quadtree grid follows the data. The sketch below uses capacity 4, the figure in Wikipedia's pseudocode, and prunes whole subtrees whose box misses the query.

interface Point { id: string; lat: number; lng: number }
interface Box { latMin: number; latMax: number; lngMin: number; lngMax: number }

const CAPACITY = 4; // a leaf splits into 4 children when the 5th point arrives

const overlaps = (a: Box, b: Box) =>
  a.latMin <= b.latMax && a.latMax >= b.latMin && a.lngMin <= b.lngMax && a.lngMax >= b.lngMin;
const contains = (b: Box, p: Point) =>
  p.lat >= b.latMin && p.lat <= b.latMax && p.lng >= b.lngMin && p.lng <= b.lngMax;

export class QuadTree {
  private points: Point[] = [];
  private children: QuadTree[] | null = null;
  private box: Box;
  private depth: number;
  constructor(box: Box, depth = 0) {
    this.box = box;
    this.depth = depth;
  }

  insert(p: Point): boolean {
    if (!contains(this.box, p)) return false;
    if (!this.children) {
      // depth cap: many points on one spot would otherwise split forever
      if (this.points.length < CAPACITY || this.depth >= 20) { this.points.push(p); return true; }
      this.split();
    }
    return this.children!.some((c) => c.insert(p));
  }

  query(range: Box, found: Point[] = []): Point[] {
    if (!overlaps(this.box, range)) return found; // prune a whole subtree
    for (const p of this.points) if (contains(range, p)) found.push(p);
    this.children?.forEach((c) => c.query(range, found));
    return found;
  }

  private split(): void {
    const { latMin, latMax, lngMin, lngMax } = this.box;
    const latMid = (latMin + latMax) / 2, lngMid = (lngMin + lngMax) / 2;
    this.children = [
      { latMin, latMax: latMid, lngMin, lngMax: lngMid },
      { latMin, latMax: latMid, lngMin: lngMid, lngMax },
      { latMin: latMid, latMax, lngMin, lngMax: lngMid },
      { latMin: latMid, latMax, lngMin: lngMid, lngMax },
    ].map((b) => new QuadTree(b, this.depth + 1));
    const old = this.points;
    this.points = [];
    for (const p of old) this.children.some((c) => c.insert(p));
  }
}

The trade is that a quadtree is a data structure you hold in memory, not a key you can store in a database column. It has no boundary problem, because the query walks every overlapping box, but moving a point means a delete and an insert, and the tree needs rebalancing as density shifts. It suits a single process that owns the live positions, such as a game server or a dispatch worker, less so a stateless web tier.

Is PostGIS with a GiST index the pragmatic default?

For most products, yes. PostGIS gives you a geography type measured in metres, a GiST index and ST_DWithin, which the documentation describes as including a bounding box comparison that uses any available index. You write one SQL predicate instead of maintaining cells, neighbours and precision yourself, and the data stays next to the rest of your relational model, which is the usual shape of an ERP or POS backend.

CREATE EXTENSION IF NOT EXISTS postgis;

CREATE TABLE driver_positions (
  driver_id  bigint PRIMARY KEY,
  location   geography(Point, 4326) NOT NULL,   -- 4326 = WGS 84 longitude/latitude
  updated_at timestamptz NOT NULL DEFAULT now()
);

CREATE INDEX driver_positions_location_gix
  ON driver_positions USING GIST (location);

-- Drivers within 2 km of a passenger in central Jakarta, seen in the last 30 seconds.
-- ST_DWithin takes metres for geography and uses the GiST index; note longitude FIRST.
SELECT d.driver_id,
       ST_Distance(d.location, p.pt) AS metres
FROM   driver_positions d,
       (SELECT ST_SetSRID(ST_MakePoint(106.8456, -6.2088), 4326)::geography AS pt) p
WHERE  ST_DWithin(d.location, p.pt, 2000)
  AND  d.updated_at > now() - interval '30 seconds'
ORDER  BY metres
LIMIT  10;

-- Wrong: ST_Distance(d.location, p.pt) < 2000 in the WHERE clause cannot use the index.

Two details cause most of the pain. Coordinates go longitude first, so ST_MakePoint(106.8456, -6.2088) is Jakarta and swapping them puts you in the Southern Ocean. And the distance must be passed to ST_DWithin as the filter, not computed in the WHERE clause, otherwise the index is bypassed. For geography the distance is in metres and, by default, measured on the spheroid; the documentation says setting use_spheroid to false measures on a sphere for faster evaluation.

Do not reach for a geohash column in Postgres unless you have a reason PostGIS cannot meet. It is the same idea with more code to own, and the nine-cell query above is the part people get subtly wrong.

ST_Distance(a, b) less than 2000 in a WHERE clause is correct but unindexed. Put the radius inside ST_DWithin, and use ST_Distance only in the SELECT and ORDER BY of the few rows that survive.

When should I use Redis GEOSEARCH instead?

Use Redis when the data is hot, small enough for RAM and rewritten constantly, such as the latest position of each online driver. GEOADD stores members in a sorted set, and GEOSEARCH, available since Redis 6.2.0, queries it from a coordinate or an existing member by radius or box, with ASC ordering, COUNT and WITHDIST. It replaces the deprecated GEORADIUS commands.

# Longitude first, then latitude. The member is whatever you want back.
GEOADD drivers 106.8456 -6.2088 driver:42
GEOADD drivers 106.8301 -6.1754 driver:77

# Nearest 10 within 2 km, closest first, with the distance. Needs Redis 6.2 or later.
GEOSEARCH drivers FROMLONLAT 106.8456 -6.2088 BYRADIUS 2 km ASC COUNT 10 WITHDIST

# GEOADD stores a sorted set whose score is a 52-bit geohash, so ordinary sorted-set
# commands work on it. Redis has no per-member TTL, so keep a last-seen set to expire drivers:
ZADD drivers:seen 1791619200 driver:42
ZRANGEBYSCORE drivers:seen -inf 1791619170      # not seen in 30 s: candidates to remove
ZREM drivers driver:42

Know what it is under the hood. The score is a 52-bit geohash, so the boundary problem exists internally, which is why the documented cost is proportional to the items in the grid-aligned bounding box around the shape, not just those inside it. Very large areas with a small COUNT can still be slow. There is no per-member expiry, so a driver who goes offline stays in the set until you remove it, and a companion sorted set of last-seen times is the simple way to do that.

How do moving drivers change the design?

A place index is read-mostly; a driver index is write-dominated, and that flips the decision. Take 100,000 online drivers pinging every 4 seconds. That is 25,000 position writes per second, over two billion a day, and each one is a new Postgres row version that also rewrites the GiST entry, because the PostgreSQL documentation says a heap-only update is possible only when no indexed column changes.

Assumed inputs (a design exercise, not a measurement):
  online drivers          = 100,000
  position ping interval  = 4 seconds
  driver speed            = 10 m/s (36 km/h)

Position updates
  100,000 / 4             = 25,000 updates per second
  25,000 x 86,400         = 2,160,000,000 updates per day

Postgres: every UPDATE writes a new row version, and because the indexed location
column changes it cannot be a heap-only (HOT) update, so the GiST entry is rewritten too.
  = 25,000 row versions and 25,000 index updates per second, for ever

How often does a driver actually change geohash cell (precision 6, straight-line bound)?
  north-south: 611 m / 10 m/s  = 61 s per cell
  east-west:  1,216 m / 10 m/s = 122 s per cell
  100,000 x (1/61 + 1/122)     = 2,459 cell changes per second, at most
  vs 25,000 position updates   = about 10x fewer index-relevant writes

Snapshot instead of every ping (live position in Redis, history in Postgres every 30 s)
  100,000 / 30                 = 3,333 Postgres writes per second

Two levers help. First, the cell, not the position, is what the index cares about: at 10 m/s a driver crosses a precision-6 cell at most every 61 seconds north-south, so cell changes top out around 2,459 per second, about ten times fewer than pings. Second, split the stores: keep the live position in Redis and write a snapshot to Postgres every 30 seconds, which is 3,333 writes per second instead of 25,000.

Also filter on freshness. A position older than 30 seconds is a driver who has entered a tunnel or closed the app, and showing them is worse than showing nobody. Whichever store you pick, the query should carry an updated_at condition, or a cleanup job should evict stale members.

Geohash vs quadtree vs S2, H3 and PostGIS: which should I pick?

S2 and H3 are the grown-up relatives of the geohash. S2 represents data on a three-dimensional sphere, avoiding the seams of flat map projections, and H3, developed at Uber, partitions the world into hexagonal cells. Hexagons matter because every neighbour is the same distance away, which removes the corner cases of squares, but both are libraries you add to your service, not features your database already has. The comparison below is how I would choose.

Approach	Where the index lives	Moving points	Pick it when
Geohash	A text column with a btree, or the key itself	Cheap, a point only changes key when it crosses a cell	You need a portable key, a cache key or sharding by area
Quadtree	An in-memory tree inside one process	Delete and insert, plus rebalancing	One worker owns the live positions and density is very uneven
S2 or H3	A cell id column computed by a library	Same as geohash, cell id changes on crossing	You need uniform neighbours or analytics over many cities
PostGIS with GiST	A GiST index on disk, queried with ST_DWithin	Every move rewrites a row version and an index entry	The default for places and for modest fleets
Redis GEOSEARCH	A sorted set in RAM with 52-bit geohash scores	Fast overwrite with GEOADD, but you evict stale members	Live positions that are rewritten every few seconds

Run this checklist before choosing, in order, and stop at the first yes:

Are the points places that rarely move, such as branches, outlets or carwashes? Use PostGIS with ST_DWithin.
Is the data rewritten every few seconds and read by one nearby search? Use Redis GEOSEARCH, with a last-seen set.
Does one process own all positions and density vary by orders of magnitude? Use an in-memory quadtree.
Do you need a stable area key for caching, sharding or analytics? Use geohash, S2 or H3 cells.
Is the radius larger than a cell edge? Drop one precision level, or you will silently miss points.

My own bias is to start with PostGIS, add Redis only when the write rate is the measured problem, and never hand-roll a quadtree before either has failed. The arithmetic above is the test: if 25,000 writes per second is not your number, you do not need the second store.

Nearby search is a key design problem. Turn two-dimensional proximity into something an index can seek on, remember that a cell is a coarse filter and not an answer, search the neighbours as well as the centre, and let the write rate of your moving points, not the elegance of the data structure, decide where the live positions live.

Sources and further reading

Frequently Asked Questions

Geohash vs Quadtree: How Nearby Driver Search Works

Frequently Asked Questions

Geohash vs Quadtree: How Nearby Driver Search Works

Why is a distance query on every row too slow?

How does a geohash turn coordinates into a string?

Why do geohash searches miss nearby points, and what are the 8 neighbours?

How is a quadtree different from a geohash?

Is PostGIS with a GiST index the pragmatic default?

When should I use Redis GEOSEARCH instead?

How do moving drivers change the design?

Geohash vs quadtree vs S2, H3 and PostGIS: which should I pick?

Why is a distance query on every row too slow?

How does a geohash turn coordinates into a string?

Why do geohash searches miss nearby points, and what are the 8 neighbours?

How is a quadtree different from a geohash?

Is PostGIS with a GiST index the pragmatic default?

When should I use Redis GEOSEARCH instead?

How do moving drivers change the design?

Geohash vs quadtree vs S2, H3 and PostGIS: which should I pick?