System Design (High-Level Design) Module 14 – Search, geospatial and probabilistic data structures

Geospatial indexing: geohash, quadtrees, S2, H3

How nearby search turns positions into cells: geohash, quadtrees, S2 and H3 compared, with geohash in 14 languages and the cells every search reads.

Intermediate
25 minutes
Examples run with Python 3.14.8, Pyodide 314.0.7, Node.js 24.21.0 and quickjs 0.32.0
By MySmartCoPilot

Free: Why nearby search needs its own index · Four ways to cut the map into cells · Geohash names nested cells by halving the map · Practise: the cells around a cell. With a pass: 3 in-depth parts and 3 interview answers, about 17 minutes.

What you will learn

Encode locations with geohash and find a cell's neighbouring cells
Compare quadtrees, S2 cells and H3 hexagons by cell shape, nesting and density
Handle cell boundaries, search radii larger than a cell and the 180th meridian
Design the location index for moving objects such as drivers
Choose a cell scheme for ride matching, restaurant search and pricing zones

Before you start

Database indexes: how they work, when they help

What you’ll learn · Before you start

What you will learn

Encode locations with geohash and find a cell's neighbouring cells
Compare quadtrees, S2 cells and H3 hexagons by cell shape, nesting and density
Handle cell boundaries, search radii larger than a cell and the 180th meridian
Design the location index for moving objects such as drivers
Choose a cell scheme for ride matching, restaurant search and pricing zones

Before you start

Database indexes: how they work, when they help

On this page

To find the drivers within 1 km of a rider, a geospatial index cuts the map into cells and gives each cell a key that an ordinary index can store: a string, a 64-bit number or a node in a tree. A nearby search computes the rider’s cell, reads that cell and the cells around it, and filters the candidates by their true distance. Geohash, quadtrees, S2 and H3 are four ways of cutting the cells. They differ in the shape of a cell, in how small cells nest inside large ones and in how they cope with crowded areas, and those differences decide which fits ride matching, restaurant search or pricing zones.

Why nearby search needs its own index

A position is two numbers, and an ordinary index sorts by one key. An index on latitude finds the drivers in a band of latitude around the rider, but the band runs right around the planet, so every driver in it still has to be checked for longitude. Two separate indexes help little: each returns a band, and the answer is their small overlap. The program measures both bands for a 1 km search:

What one sorted coordinate returns for a 1 km search Python · bands/bands.py

# What an ordinary index on one coordinate returns for a nearby search, on a sphere of the Earth's mean radius.
import math

R_KM = 6371.0  # the Earth's mean radius
lat = 12.97194  # the rider, in Bengaluru
radius_km = 1.0

circle = math.pi * radius_km**2
# Latitude within 1 km of the rider: a band 2 km tall that runs right round the planet at this latitude.
lat_band = 2 * radius_km * 2 * math.pi * R_KM * math.cos(math.radians(lat))
# Longitude within 1 km of the rider (at the rider's latitude): a band from pole to pole, widest at the equator.
dlon = 2 * radius_km / (R_KM * math.cos(math.radians(lat)))  # radians
lon_band = dlon * R_KM**2 * 2

print(f"A search within {radius_km:.0f} km of a rider covers {circle:.1f} km². An index on one coordinate returns:")
print(f"  latitude within 1 km:  {lat_band:>8,.0f} km², {lat_band / circle:>6,.0f} times the circle")
print(f"  longitude within 1 km: {lon_band:>8,.0f} km², {lon_band / circle:>6,.0f} times the circle")
print(f"  both, intersected:     {(2 * radius_km) ** 2:>8,.1f} km², the square around the circle")

Output

A search within 1 km of a rider covers 3.1 km². An index on one coordinate returns:
  latitude within 1 km:    78,017 km², 24,834 times the circle
  longitude within 1 km:   26,151 km²,  8,324 times the circle
  both, intersected:          4.0 km², the square around the circle

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 bands.py

Each band is thousands of times the circle. A nearby search wants the inside of a small circle, and no single sort order gives that.

Two families of indexes solve it. Trees of boxes, such as the R-tree: A tree index of nested rectangles. Each node's box encloses the boxes or shapes below it, so a search descends only into boxes that overlap the area asked for; PostGIS's GiST indexes build one. behind PostGIS’s GiST indexes, group nearby shapes into nested rectangles (PostGIS workshop, spatial indexing). Cell schemes first turn every position into a cell key, so that the store underneath can be a sorted table, a hash map in memory or a key-value store.

Four ways to cut the map into cells

geohash: A position written as base-32 characters by halving the longitude and latitude ranges in turn, five halvings per character. A longer geohash is a smaller cell inside the shorter one. interleaves the bits of longitude and latitude and writes them five at a time as base-32 characters. Each extra character makes the cell 32 times smaller, and points in one small cell share a long prefix, so a sorted index finds a cell with a prefix scan. PostGIS computes geohashes with ST_GeoHash, and Redis stores 52 interleaved bits as the score of a sorted set (PostGIS, ST_GeoHash; Redis, GEOADD).

A quadtree: A tree that splits a square into four equal quarters, and each quarter again, only where it holds more points than a set limit, so its leaves are small where points crowd and large where they are sparse. splits a square into four and splits again only where a square holds too many points. Its cells are small where things crowd together and large where they are sparse. Step through one square of a city:

Interactive · step by step A quadtree splits only where drivers crowd Step through the splits. Each box is a square of the map; a square that holds more than 4 drivers splits into four.

The drawing shows the whole scene; its 5 steps are listed below.

Every step as text

Too many. A square of the city holds 12 drivers, and a leaf of this quadtree may hold at most 4. Twelve is too many, so the square splits into four equal quarters.
Four quarters. The quarters hold 1, 2, 7 and 2 drivers. Three of them are within the limit and stay as leaves, however large they are.
A crowded quarter. The south-west quarter, around a busy station, holds 7 drivers, more than 4, so it splits again.
Small where it is busy. Its quarters hold 2, 1, 3 and 1 drivers, and every leaf now holds 4 or fewer. The leaves near the station are a sixteenth of the city square; the quiet quarters stay a quarter.
What a search reads. A search near the station walks down to a small leaf and reads a few drivers, instead of one big cell holding everyone there. The split happened only where it was needed.

S2 cells: The hierarchy of cells S2 makes by projecting the sphere onto the six faces of a cube, numbered with 64-bit ids along a Hilbert curve, from whole faces down to leaf cells about 1 cm across. projects the sphere onto the six faces of a cube and divides each face into a hierarchy of cells, from level 0 down to leaf cells about 1 cm across at level 30. It numbers the cells along a Hilbert curve with 64-bit ids, so cells whose ids are close are close on the ground (S2, cell hierarchy). Any region can be approximated by a set of S2 cells (S2 Geometry).

H3: A grid of hexagons, plus 12 pentagons, that covers the world at 16 resolutions. Every neighbour of a hexagon is the same distance from its centre. covers the world with hexagons at 16 resolutions, plus 12 pentagons at every resolution, because hexagons alone cannot cover a sphere (H3, overview). All six neighbours of a hexagon are the same distance from its centre, while a square has neighbours at two distances. That simplifies analysing movement between cells (H3, aggregation) and suits heat maps and pricing zones.

Scheme	How it cuts the map	Fits best
Geohash	Rectangles named by base-32 strings; a prefix is the enclosing cell	Prefix scans in any sorted store
Quadtree	Squares split in four where points crowd	Uneven density held in memory
S2	Cells on a cube’s six faces, 64-bit ids along a Hilbert curve	Covering regions anywhere on the sphere
H3	Hexagons and 12 pentagons; six neighbours, all equally far	Heat maps and pricing zones

Checkpoint

Check: Why one sorted coordinate fails · Four ways to cut the map

Question 1 of 2 A table of drivers has an ordinary index on latitude. What does a search for latitudes within 1 km of a rider return?
Choose one answer.

Nothing, because an index cannot search a range of numbers Every driver in a band 2 km tall that runs right round the planet, still to be checked for longitude The drivers in a 2 km by 2 km square around the rider The drivers within 1 km of the rider

Show the answer: Question 1 of 2

Answer: Every driver in a band 2 km tall that runs right round the planet, still to be checked for longitude

An ordinary index sorts by one key. Latitudes within 1 km form a band 2 km tall at that latitude all the way round the Earth, about 78,000 km² in the program's run, and every driver in it must still be checked for longitude.
Question 2 of 2 In the quadtree figure a leaf may hold at most 4 drivers, and the south-west quarter holds 7. What happens to it?
Choose one answer.

Nothing, because the limit only applies to the first split It splits into four smaller squares, and each of them holds 4 drivers or fewer The whole city square splits again into sixteen equal parts Its drivers move to the quieter quarters

Show the answer: Question 2 of 2

Answer: It splits into four smaller squares, and each of them holds 4 drivers or fewer

A quadtree splits a square into four only when it holds too many points, and keeps going level by level. Cells end up small where drivers crowd and large where they are sparse, so leaves hold similar numbers of drivers.

Geohash names nested cells by halving the map

Geohash halves a range again and again, longitude on even steps and latitude on odd ones, and every five halvings make one character. Step through the first ten for the rider:

Interactive · line by line Ten halvings make the first two characters of a geohash Step through the loop. The lit line has just run and the numbered chip marks the line that runs next; rng is the same list as lons or lats, so watch that list shrink.

Program · trace/two_chars.py

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"
lat, lon = 12.97194, 77.59369
lats = [-90.0, 90.0]
lons = [-180.0, 180.0]
cell, value = "", 0
for i in range(10):
    if i % 2 == 0:
        rng, x = lons, lon
    else:
        rng, x = lats, lat
    mid = (rng[0] + rng[1]) / 2
    if x >= mid:
        value = value * 2 + 1
        rng[0] = mid
    else:
        value = value * 2
        rng[1] = mid
    if i % 5 == 4:
        cell += BASE32[value]
        value = 0
print(cell, lats, lons)

Variables

just taken by the loop
changed in this step
passed by the loop
read next
where the loop stopped
the stop value, never given

Printed so far

Nothing printed yettd [11.25, 16.875] [67.5, 78.75]

Every step was recorded from a run with Python 3.14.8 on macOS 26 arm64.

The drawing shows the variables when the program ends, and the program's 92 steps are listed below.

Line run 21

Next line end

Loop pass –

Every step as text

Start. No line has run yet, so there are no variables. Python starts with line 1.
Line 1. BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz" sets BASE32 to '0123456789bcdefghjkmnpqrstuvwxyz'.
Line 2. lat, lon = 12.97194, 77.59369 sets lat to 12.97194 and sets lon to 77.59369.
Line 3. lats = [-90.0, 90.0] makes lats a list of 2 items.
Line 4. lons = [-180.0, 180.0] makes lons a list of 2 items.
Line 5. cell, value = "", 0 sets cell to '' and sets value to 0.
Line 6. for i in range(10): gives its first number: i is 0.
Line 7. i % 2 == 0 is true (i is 0), so the block under if i % 2 == 0: runs.
Line 8. rng, x = lons, lon makes rng a second name for the list lons names: one list, two names, not a copy and sets x to 77.59369.
Line 11. mid = (rng[0] + rng[1]) / 2 sets mid to 0.0.
Line 12. x >= mid is true (x is 77.59369 and mid is 0.0), so the block under if x >= mid: runs.
Line 13. value = value * 2 + 1 sets value to 1 (it was 0).
Line 14. rng[0] = mid changes rng: it is now [0.0, 180.0]. Key point 77.59369 is at least 0, the middle of −180 to 180, so the bit is 1 and the longitude range becomes 0 to 180. rng is lons itself, so lons changes.
Line 18. i % 5 == 4 is false (i is 0), so Python skips the block under if i % 5 == 4:.
Line 6. for i in range(10): gives the next number: i is 1.
Line 7. i % 2 == 0 is false (i is 1), so the else block runs.
Line 10. rng, x = lats, lat makes rng a second name for the list lats names: one list, two names, not a copy and sets x to 12.97194 (it was 77.59369).
Line 11. mid = (rng[0] + rng[1]) / 2 mid keeps its value, 0.0.
Line 12. x >= mid is true (x is 12.97194 and mid is 0.0), so the block under if x >= mid: runs.
Line 13. value = value * 2 + 1 sets value to 3 (it was 1).
Line 14. rng[0] = mid changes rng: it is now [0.0, 90.0].
Line 18. i % 5 == 4 is false (i is 1), so Python skips the block under if i % 5 == 4:.
Line 6. for i in range(10): gives the next number: i is 2.
Line 7. i % 2 == 0 is true (i is 2), so the block under if i % 2 == 0: runs.
Line 8. rng, x = lons, lon makes rng a second name for the list lons names: one list, two names, not a copy and sets x to 77.59369 (it was 12.97194).
Line 11. mid = (rng[0] + rng[1]) / 2 sets mid to 90.0 (it was 0.0).
Line 12. x >= mid is false (x is 77.59369 and mid is 90.0), so the else block runs.
Line 16. value = value * 2 sets value to 6 (it was 3).
Line 17. rng[1] = mid changes rng: it is now [0.0, 90.0]. The rider's longitude, 77.59369, is below 90, the middle of 0 to 180, so this bit is 0 and the range keeps its western half, 0 to 90.
Line 18. i % 5 == 4 is false (i is 2), so Python skips the block under if i % 5 == 4:.
Line 6. for i in range(10): gives the next number: i is 3.
Line 7. i % 2 == 0 is false (i is 3), so the else block runs.
Line 10. rng, x = lats, lat makes rng a second name for the list lats names: one list, two names, not a copy and sets x to 12.97194 (it was 77.59369).
Line 11. mid = (rng[0] + rng[1]) / 2 sets mid to 45.0 (it was 90.0).
Line 12. x >= mid is false (x is 12.97194 and mid is 45.0), so the else block runs.
Line 16. value = value * 2 sets value to 12 (it was 6).
Line 17. rng[1] = mid changes rng: it is now [0.0, 45.0].
Line 18. i % 5 == 4 is false (i is 3), so Python skips the block under if i % 5 == 4:.
Line 6. for i in range(10): gives the next number: i is 4.
Line 7. i % 2 == 0 is true (i is 4), so the block under if i % 2 == 0: runs.
Line 8. rng, x = lons, lon makes rng a second name for the list lons names: one list, two names, not a copy and sets x to 77.59369 (it was 12.97194).
Line 11. mid = (rng[0] + rng[1]) / 2 mid keeps its value, 45.0.
Line 12. x >= mid is true (x is 77.59369 and mid is 45.0), so the block under if x >= mid: runs.
Line 13. value = value * 2 + 1 sets value to 25 (it was 12).
Line 14. rng[0] = mid changes rng: it is now [45.0, 90.0].
Line 18. i % 5 == 4 is true (i is 4), so the block under if i % 5 == 4: runs.
Line 19. cell += BASE32[value] changes cell from '' to 't'. Key point Five halvings gave the bits 1, 1, 0, 0, 1, which is 25 in binary, and character 25 of BASE32 is t. Every point whose first five halvings agree shares the prefix t.
Line 20. value = 0 sets value to 0 (it was 25).
Line 6. for i in range(10): gives the next number: i is 5.
Line 7. i % 2 == 0 is false (i is 5), so the else block runs.
Line 10. rng, x = lats, lat makes rng a second name for the list lats names: one list, two names, not a copy and sets x to 12.97194 (it was 77.59369).
Line 11. mid = (rng[0] + rng[1]) / 2 sets mid to 22.5 (it was 45.0).
Line 12. x >= mid is false (x is 12.97194 and mid is 22.5), so the else block runs.
Line 16. value = value * 2 value keeps its value, 0.
Line 17. rng[1] = mid changes rng: it is now [0.0, 22.5].
Line 18. i % 5 == 4 is false (i is 5), so Python skips the block under if i % 5 == 4:.
Line 6. for i in range(10): gives the next number: i is 6.
Line 7. i % 2 == 0 is true (i is 6), so the block under if i % 2 == 0: runs.
Line 8. rng, x = lons, lon makes rng a second name for the list lons names: one list, two names, not a copy and sets x to 77.59369 (it was 12.97194).
Line 11. mid = (rng[0] + rng[1]) / 2 sets mid to 67.5 (it was 22.5).
Line 12. x >= mid is true (x is 77.59369 and mid is 67.5), so the block under if x >= mid: runs.
Line 13. value = value * 2 + 1 sets value to 1 (it was 0).
Line 14. rng[0] = mid changes rng: it is now [67.5, 90.0].
Line 18. i % 5 == 4 is false (i is 6), so Python skips the block under if i % 5 == 4:.
Line 6. for i in range(10): gives the next number: i is 7.
Line 7. i % 2 == 0 is false (i is 7), so the else block runs.
Line 10. rng, x = lats, lat makes rng a second name for the list lats names: one list, two names, not a copy and sets x to 12.97194 (it was 77.59369).
Line 11. mid = (rng[0] + rng[1]) / 2 sets mid to 11.25 (it was 67.5).
Line 12. x >= mid is true (x is 12.97194 and mid is 11.25), so the block under if x >= mid: runs.
Line 13. value = value * 2 + 1 sets value to 3 (it was 1).
Line 14. rng[0] = mid changes rng: it is now [11.25, 22.5].
Line 18. i % 5 == 4 is false (i is 7), so Python skips the block under if i % 5 == 4:.
Line 6. for i in range(10): gives the next number: i is 8.
Line 7. i % 2 == 0 is true (i is 8), so the block under if i % 2 == 0: runs.
Line 8. rng, x = lons, lon makes rng a second name for the list lons names: one list, two names, not a copy and sets x to 77.59369 (it was 12.97194).
Line 11. mid = (rng[0] + rng[1]) / 2 sets mid to 78.75 (it was 11.25).
Line 12. x >= mid is false (x is 77.59369 and mid is 78.75), so the else block runs.
Line 16. value = value * 2 sets value to 6 (it was 3).
Line 17. rng[1] = mid changes rng: it is now [67.5, 78.75].
Line 18. i % 5 == 4 is false (i is 8), so Python skips the block under if i % 5 == 4:.
Line 6. for i in range(10): gives the next number: i is 9.
Line 7. i % 2 == 0 is false (i is 9), so the else block runs.
Line 10. rng, x = lats, lat makes rng a second name for the list lats names: one list, two names, not a copy and sets x to 12.97194 (it was 77.59369).
Line 11. mid = (rng[0] + rng[1]) / 2 sets mid to 16.875 (it was 78.75).
Line 12. x >= mid is false (x is 12.97194 and mid is 16.875), so the else block runs.
Line 16. value = value * 2 sets value to 12 (it was 6).
Line 17. rng[1] = mid changes rng: it is now [11.25, 16.875].
Line 18. i % 5 == 4 is true (i is 9), so the block under if i % 5 == 4: runs.
Line 19. cell += BASE32[value] changes cell from 't' to 'td'.
Line 20. value = 0 sets value to 0 (it was 12).
Line 6. for i in range(10): has no number left: a range stops before its stop value, 10, so the loop ends.
Line 21. print(cell, lats, lons) prints td [11.25, 16.875] [67.5, 78.75]. That was the last line, so the program ends. Ten halvings give td. The rider lies between latitudes 11.25 and 16.875 and longitudes 67.5 and 78.75; each further character divides that cell into 32 smaller ones.

The full program, in 14 languages:

One program · 14 languages Geohash cells for a rider, and the block of nine O(p) halvings for a geohash of p characters

Python 3.14 · main.py

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"


def encode(lat: float, lon: float, precision: int) -> str:
    # Even bits halve the longitude, odd bits the latitude.
    lat_range, lon_range = [-90.0, 90.0], [-180.0, 180.0]
    cell, value = "", 0
    for i in range(5 * precision):
        rng, x = (lon_range, lon) if i % 2 == 0 else (lat_range, lat)
        mid = (rng[0] + rng[1]) / 2
        if x >= mid:
            value, rng[0] = value * 2 + 1, mid
        else:
            value, rng[1] = value * 2, mid
        if i % 5 == 4:
            cell, value = cell + BASE32[value], 0
    return cell


def shared(a: str, b: str) -> int:
    n = 0
    while n < len(a) and a[n] == b[n]:
        n += 1
    return n


lat, lon = 12.97194, 77.59369
print("Cells that hold the rider:")
for precision in range(4, 9):
    print(f"  precision {precision}: {encode(lat, lon, precision)}")
print("Close points, short prefixes:")
for lat1, lon1, lat2, lon2 in [
    (13.00763, 77.59369, 13.00799, 77.59369),
    (0.0002, 0.0002, -0.0002, -0.0002),
]:
    a, b = encode(lat1, lon1, 8), encode(lat2, lon2, 8)
    print(f"  {a} and {b} share {shared(a, b)} characters")
# Precision 6 has 15 bits per axis.
width, height = 360 / 2**15, 180 / 2**15
cells = [
    encode(lat + dy * height, lon + dx * width, 6)
    for dy in (1, 0, -1)
    for dx in (-1, 0, 1)
]
print("The 9 cells to search:", " ".join(cells))

In Python: rng names the same list as lat_range or lon_range, so assigning rng[0] or rng[1] narrows that range itself; every five halvings add one character.

Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py

JavaScript Node 24 · main.mjs

const BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";

function encode(lat, lon, precision) {
  // Even bits halve the longitude, odd bits the latitude.
  const latRange = [-90, 90];
  const lonRange = [-180, 180];
  let [cell, value] = ["", 0];
  for (let i = 0; i < 5 * precision; i++) {
    const [range, x] = i % 2 === 0 ? [lonRange, lon] : [latRange, lat];
    const mid = (range[0] + range[1]) / 2;
    if (x >= mid) {
      value = value * 2 + 1;
      range[0] = mid;
    } else {
      value *= 2;
      range[1] = mid;
    }
    if (i % 5 === 4) {
      cell += BASE32[value];
      value = 0;
    }
  }
  return cell;
}

function shared(a, b) {
  let n = 0;
  while (n < a.length && a[n] === b[n]) n++;
  return n;
}

const [lat, lon] = [12.97194, 77.59369];
console.log("Cells that hold the rider:");
for (let precision = 4; precision <= 8; precision++) {
  console.log(`  precision ${precision}: ${encode(lat, lon, precision)}`);
}
console.log("Close points, short prefixes:");
for (const [lat1, lon1, lat2, lon2] of [
  [13.00763, 77.59369, 13.00799, 77.59369],
  [0.0002, 0.0002, -0.0002, -0.0002],
]) {
  const [a, b] = [encode(lat1, lon1, 8), encode(lat2, lon2, 8)];
  console.log(`  ${a} and ${b} share ${shared(a, b)} characters`);
}
// Precision 6 has 15 bits per axis.
const [width, height] = [360 / 2 ** 15, 180 / 2 ** 15];
const cells = [];
for (const dy of [1, 0, -1]) {
  for (const dx of [-1, 0, 1]) cells.push(encode(lat + dy * height, lon + dx * width, 6));
}
console.log("The 9 cells to search:", cells.join(" "));

In JavaScript: Destructuring picks the range and the coordinate in one line; the arrays are shared by reference, so range[0] = mid narrows lonRange or latRange itself.

Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs

Java 25 LTS · Main.java

import java.util.ArrayList;
import java.util.List;

public class Main {
  static final String BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";

  static String encode(double lat, double lon, int precision) {
    // Even bits halve the longitude, odd bits the latitude.
    double[] latRange = {-90, 90};
    double[] lonRange = {-180, 180};
    var cell = new StringBuilder();
    int value = 0;
    for (int i = 0; i < 5 * precision; i++) {
      double[] range = i % 2 == 0 ? lonRange : latRange;
      double x = i % 2 == 0 ? lon : lat;
      double mid = (range[0] + range[1]) / 2;
      if (x >= mid) {
        value = value * 2 + 1;
        range[0] = mid;
      } else {
        value *= 2;
        range[1] = mid;
      }
      if (i % 5 == 4) {
        cell.append(BASE32.charAt(value));
        value = 0;
      }
    }
    return cell.toString();
  }

  static int shared(String a, String b) {
    int n = 0;
    while (n < a.length() && a.charAt(n) == b.charAt(n)) {
      n++;
    }
    return n;
  }

  public static void main(String[] args) {
    double lat = 12.97194;
    double lon = 77.59369;
    System.out.println("Cells that hold the rider:");
    for (int precision = 4; precision <= 8; precision++) {
      System.out.println("  precision " + precision + ": " + encode(lat, lon, precision));
    }
    System.out.println("Close points, short prefixes:");
    double[][] pairs = {
      {13.00763, 77.59369, 13.00799, 77.59369},
      {0.0002, 0.0002, -0.0002, -0.0002}
    };
    for (double[] p : pairs) {
      String a = encode(p[0], p[1], 8);
      String b = encode(p[2], p[3], 8);
      System.out.println("  " + a + " and " + b + " share " + shared(a, b) + " characters");
    }
    // Precision 6 has 15 bits per axis.
    double width = 360.0 / (1 << 15);
    double height = 180.0 / (1 << 15);
    List<String> cells = new ArrayList<>();
    for (int dy = 1; dy >= -1; dy--) {
      for (int dx = -1; dx <= 1; dx++) {
        cells.add(encode(lat + dy * height, lon + dx * width, 6));
      }
    }
    System.out.println("The 9 cells to search: " + String.join(" ", cells));
  }
}

In Java: double[] is a reference type, so range points at lonRange or latRange and narrowing it narrows them; a StringBuilder collects the characters.

Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java

C++23 · main.cpp

#include <array>
#include <print>
#include <string>
#include <string_view>

constexpr std::string_view base32 = "0123456789bcdefghjkmnpqrstuvwxyz";

std::string encode(double lat, double lon, int precision) {
  // Even bits halve the longitude, odd bits the latitude.
  std::array<double, 2> lat_range = {-90, 90}, lon_range = {-180, 180};
  std::string cell;
  int value = 0;
  for (int i = 0; i < 5 * precision; ++i) {
    auto &range = i % 2 == 0 ? lon_range : lat_range;
    const double x = i % 2 == 0 ? lon : lat;
    const double mid = (range[0] + range[1]) / 2;
    if (x >= mid) {
      value = value * 2 + 1;
      range[0] = mid;
    } else {
      value *= 2;
      range[1] = mid;
    }
    if (i % 5 == 4) {
      cell += base32[value];
      value = 0;
    }
  }
  return cell;
}

int shared(std::string_view a, std::string_view b) {
  int n = 0;
  while (n < std::ssize(a) && a[n] == b[n]) {
    ++n;
  }
  return n;
}

int main() {
  const double lat = 12.97194, lon = 77.59369;
  std::println("Cells that hold the rider:");
  for (int precision = 4; precision <= 8; ++precision) {
    std::println("  precision {}: {}", precision, encode(lat, lon, precision));
  }
  std::println("Close points, short prefixes:");
  const std::array<std::array<double, 4>, 2> pairs = {{
      {13.00763, 77.59369, 13.00799, 77.59369},
      {0.0002, 0.0002, -0.0002, -0.0002},
  }};
  for (const auto &[lat1, lon1, lat2, lon2] : pairs) {
    const std::string a = encode(lat1, lon1, 8), b = encode(lat2, lon2, 8);
    std::println("  {} and {} share {} characters", a, b, shared(a, b));
  }
  // Precision 6 has 15 bits per axis.
  const double width = 360.0 / (1 << 15), height = 180.0 / (1 << 15);
  std::string cells;
  for (const int dy : {1, 0, -1}) {
    for (const int dx : {-1, 0, 1}) {
      cells += " " + encode(lat + dy * height, lon + dx * width, 6);
    }
  }
  std::println("The 9 cells to search:{}", cells);
}

In C++: auto &range binds a reference to one of the two std::array ranges, so range[0] = mid narrows it in place; the nine cells are appended to one string.

Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main

C# 14 · .NET 10 · app.cs

const string Base32 = "0123456789bcdefghjkmnpqrstuvwxyz";

double lat = 12.97194, lon = 77.59369;
Console.WriteLine("Cells that hold the rider:");
for (int precision = 4; precision <= 8; precision++)
    Console.WriteLine($"  precision {precision}: {Encode(lat, lon, precision)}");
Console.WriteLine("Close points, short prefixes:");
(double, double, double, double)[] pairs =
[
    (13.00763, 77.59369, 13.00799, 77.59369),
    (0.0002, 0.0002, -0.0002, -0.0002),
];
foreach (var (lat1, lon1, lat2, lon2) in pairs)
{
    string a = Encode(lat1, lon1, 8), b = Encode(lat2, lon2, 8);
    Console.WriteLine($"  {a} and {b} share {Shared(a, b)} characters");
}
// Precision 6 has 15 bits per axis.
double width = 360.0 / (1 << 15), height = 180.0 / (1 << 15);
var cells = new List<string>();
foreach (int dy in new[] { 1, 0, -1 })
    foreach (int dx in new[] { -1, 0, 1 })
        cells.Add(Encode(lat + dy * height, lon + dx * width, 6));
Console.WriteLine($"The 9 cells to search: {string.Join(" ", cells)}");

static string Encode(double lat, double lon, int precision)
{
    // Even bits halve the longitude, odd bits the latitude.
    double[] latRange = [-90, 90], lonRange = [-180, 180];
    var cell = new System.Text.StringBuilder();
    int value = 0;
    for (int i = 0; i < 5 * precision; i++)
    {
        double[] range = i % 2 == 0 ? lonRange : latRange;
        double x = i % 2 == 0 ? lon : lat;
        double mid = (range[0] + range[1]) / 2;
        if (x >= mid)
        {
            value = value * 2 + 1;
            range[0] = mid;
        }
        else
        {
            value *= 2;
            range[1] = mid;
        }
        if (i % 5 == 4)
        {
            cell.Append(Base32[value]);
            value = 0;
        }
    }
    return cell.ToString();
}

static int Shared(string a, string b)
{
    int n = 0;
    while (n < a.Length && a[n] == b[n])
        n++;
    return n;
}

In C#: Arrays are reference types, so range[0] = mid narrows lonRange or latRange, and the cells are collected with nested foreach loops over two inline arrays.

Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs

C23 · main.c

#include <stdio.h>

static const char base32[] = "0123456789bcdefghjkmnpqrstuvwxyz";

// Writes the geohash of (lat, lon) to cell, which holds precision + 1 chars.
static void encode(double lat, double lon, int precision, char *cell) {
  // Even bits halve the longitude, odd bits the latitude.
  double lat_range[2] = {-90, 90}, lon_range[2] = {-180, 180};
  int value = 0;
  for (int i = 0; i < 5 * precision; i++) {
    double *range = i % 2 == 0 ? lon_range : lat_range;
    const double x = i % 2 == 0 ? lon : lat;
    const double mid = (range[0] + range[1]) / 2;
    if (x >= mid) {
      value = value * 2 + 1;
      range[0] = mid;
    } else {
      value *= 2;
      range[1] = mid;
    }
    if (i % 5 == 4) {
      cell[i / 5] = base32[value];
      value = 0;
    }
  }
  cell[precision] = '\0';
}

static int shared(const char *a, const char *b) {
  int n = 0;
  while (a[n] != '\0' && a[n] == b[n])
    n++;
  return n;
}

int main(void) {
  const double lat = 12.97194, lon = 77.59369;
  char a[16], b[16];
  printf("Cells that hold the rider:\n");
  for (int precision = 4; precision <= 8; precision++) {
    encode(lat, lon, precision, a);
    printf("  precision %d: %s\n", precision, a);
  }
  printf("Close points, short prefixes:\n");
  static const double pairs[2][4] = {{13.00763, 77.59369, 13.00799, 77.59369},
                                     {0.0002, 0.0002, -0.0002, -0.0002}};
  for (int i = 0; i < 2; i++) {
    encode(pairs[i][0], pairs[i][1], 8, a);
    encode(pairs[i][2], pairs[i][3], 8, b);
    printf("  %s and %s share %d characters\n", a, b, shared(a, b));
  }
  // Precision 6 has 15 bits per axis.
  const double width = 360.0 / (1 << 15), height = 180.0 / (1 << 15);
  printf("The 9 cells to search:");
  for (int dy = 1; dy >= -1; dy--) {
    for (int dx = -1; dx <= 1; dx++) {
      encode(lat + dy * height, lon + dx * width, 6, a);
      printf(" %s", a);
    }
  }
  printf("\n");
  return 0;
}

In C: The caller passes a buffer of precision + 1 characters, and encode writes each character at position i / 5 and the terminating zero at the end.

Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main

PHP 8.5 · main.php

<?php

declare(strict_types=1);

const BASE32 = '0123456789bcdefghjkmnpqrstuvwxyz';

function encode(float $lat, float $lon, int $precision): string
{
    // Even bits halve the longitude, odd bits the latitude.
    $ranges = ['lat' => [-90.0, 90.0], 'lon' => [-180.0, 180.0]];
    [$cell, $value] = ['', 0];
    for ($i = 0; $i < 5 * $precision; $i++) {
        [$axis, $x] = $i % 2 === 0 ? ['lon', $lon] : ['lat', $lat];
        $mid = ($ranges[$axis][0] + $ranges[$axis][1]) / 2;
        if ($x >= $mid) {
            $value = $value * 2 + 1;
            $ranges[$axis][0] = $mid;
        } else {
            $value *= 2;
            $ranges[$axis][1] = $mid;
        }
        if ($i % 5 === 4) {
            $cell .= BASE32[$value];
            $value = 0;
        }
    }
    return $cell;
}

function shared(string $a, string $b): int
{
    $n = 0;
    while ($n < strlen($a) && $a[$n] === $b[$n]) {
        $n++;
    }
    return $n;
}

[$lat, $lon] = [12.97194, 77.59369];
echo "Cells that hold the rider:\n";
for ($precision = 4; $precision <= 8; $precision++) {
    echo "  precision {$precision}: " . encode($lat, $lon, $precision) . "\n";
}
echo "Close points, short prefixes:\n";
$pairs = [
    [13.00763, 77.59369, 13.00799, 77.59369],
    [0.0002, 0.0002, -0.0002, -0.0002],
];
foreach ($pairs as [$lat1, $lon1, $lat2, $lon2]) {
    [$a, $b] = [encode($lat1, $lon1, 8), encode($lat2, $lon2, 8)];
    echo "  {$a} and {$b} share " . shared($a, $b) . " characters\n";
}
// Precision 6 has 15 bits per axis.
[$width, $height] = [360 / 2 ** 15, 180 / 2 ** 15];
$cells = [];
foreach ([1, 0, -1] as $dy) {
    foreach ([-1, 0, 1] as $dx) {
        $cells[] = encode($lat + $dy * $height, $lon + $dx * $width, 6);
    }
}
echo 'The 9 cells to search: ' . implode(' ', $cells) . "\n";

In PHP: Arrays are values in PHP, so the two ranges live in one array under the keys lat and lon, and $ranges[$axis][0] = $mid changes the stored range in place.

Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php

Rust 1.99 · main.rs

const BASE32: &[u8; 32] = b"0123456789bcdefghjkmnpqrstuvwxyz";

fn encode(lat: f64, lon: f64, precision: usize) -> String {
    // Even bits halve the longitude, odd bits the latitude.
    let (mut lat_range, mut lon_range) = ([-90.0, 90.0], [-180.0, 180.0]);
    let (mut cell, mut value) = (String::new(), 0);
    for i in 0..5 * precision {
        let (range, x) = if i % 2 == 0 {
            (&mut lon_range, lon)
        } else {
            (&mut lat_range, lat)
        };
        let mid = (range[0] + range[1]) / 2.0;
        if x >= mid {
            value = value * 2 + 1;
            range[0] = mid;
        } else {
            value *= 2;
            range[1] = mid;
        }
        if i % 5 == 4 {
            cell.push(char::from(BASE32[value]));
            value = 0;
        }
    }
    cell
}

fn shared(a: &str, b: &str) -> usize {
    a.bytes().zip(b.bytes()).take_while(|(x, y)| x == y).count()
}

fn main() {
    let (lat, lon) = (12.97194, 77.59369);
    println!("Cells that hold the rider:");
    for precision in 4..=8 {
        println!("  precision {precision}: {}", encode(lat, lon, precision));
    }
    println!("Close points, short prefixes:");
    let pairs = [
        (13.00763, 77.59369, 13.00799, 77.59369),
        (0.0002, 0.0002, -0.0002, -0.0002),
    ];
    for (lat1, lon1, lat2, lon2) in pairs {
        let (a, b) = (encode(lat1, lon1, 8), encode(lat2, lon2, 8));
        println!("  {a} and {b} share {} characters", shared(&a, &b));
    }
    // Precision 6 has 15 bits per axis.
    let (width, height) = (360.0 / f64::from(1 << 15), 180.0 / f64::from(1 << 15));
    let mut cells = Vec::new();
    for dy in [1.0, 0.0, -1.0] {
        for dx in [-1.0, 0.0, 1.0] {
            cells.push(encode(lat + dy * height, lon + dx * width, 6));
        }
    }
    println!("The 9 cells to search: {}", cells.join(" "));
}

In Rust: The if expression borrows one of the two ranges mutably, so range[0] = mid narrows it in place, and shared zips the two strings' bytes.

Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main

TypeScript 6.0 · main.ts

const BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";

function encode(lat: number, lon: number, precision: number): string {
  // Even bits halve the longitude, odd bits the latitude.
  const latRange: [number, number] = [-90, 90];
  const lonRange: [number, number] = [-180, 180];
  let [cell, value] = ["", 0];
  for (let i = 0; i < 5 * precision; i++) {
    const [range, x] = i % 2 === 0 ? [lonRange, lon] : [latRange, lat];
    const mid = (range[0] + range[1]) / 2;
    if (x >= mid) {
      value = value * 2 + 1;
      range[0] = mid;
    } else {
      value *= 2;
      range[1] = mid;
    }
    if (i % 5 === 4) {
      cell += BASE32[value];
      value = 0;
    }
  }
  return cell;
}

function shared(a: string, b: string): number {
  let n = 0;
  while (n < a.length && a[n] === b[n]) n++;
  return n;
}

const [lat, lon] = [12.97194, 77.59369];
console.log("Cells that hold the rider:");
for (let precision = 4; precision <= 8; precision++) {
  console.log(`  precision ${precision}: ${encode(lat, lon, precision)}`);
}
console.log("Close points, short prefixes:");
const pairs: [number, number, number, number][] = [
  [13.00763, 77.59369, 13.00799, 77.59369],
  [0.0002, 0.0002, -0.0002, -0.0002],
];
for (const [lat1, lon1, lat2, lon2] of pairs) {
  const [a, b] = [encode(lat1, lon1, 8), encode(lat2, lon2, 8)];
  console.log(`  ${a} and ${b} share ${shared(a, b)} characters`);
}
// Precision 6 has 15 bits per axis.
const [width, height] = [360 / 2 ** 15, 180 / 2 ** 15];
const cells: string[] = [];
for (const dy of [1, 0, -1]) {
  for (const dx of [-1, 0, 1]) cells.push(encode(lat + dy * height, lon + dx * width, 6));
}
console.log("The 9 cells to search:", cells.join(" "));

In TypeScript: The ranges are typed as [number, number] tuples, so the destructured range is mutable and narrowing it narrows lonRange or latRange.

Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts

Go 1.27 · main.go

package main

import (
	"fmt"
	"strings"
)

const base32 = "0123456789bcdefghjkmnpqrstuvwxyz"

func encode(lat, lon float64, precision int) string {
	// Even bits halve the longitude, odd bits the latitude.
	latRange, lonRange := [2]float64{-90, 90}, [2]float64{-180, 180}
	var cell strings.Builder
	value := 0
	for i := range 5 * precision {
		rng, x := &lonRange, lon
		if i%2 == 1 {
			rng, x = &latRange, lat
		}
		mid := (rng[0] + rng[1]) / 2
		if x >= mid {
			value = value*2 + 1
			rng[0] = mid
		} else {
			value *= 2
			rng[1] = mid
		}
		if i%5 == 4 {
			cell.WriteByte(base32[value])
			value = 0
		}
	}
	return cell.String()
}

func shared(a, b string) int {
	n := 0
	for n < len(a) && a[n] == b[n] {
		n++
	}
	return n
}

func main() {
	lat, lon := 12.97194, 77.59369
	fmt.Println("Cells that hold the rider:")
	for precision := 4; precision <= 8; precision++ {
		fmt.Printf("  precision %d: %s\n", precision, encode(lat, lon, precision))
	}
	fmt.Println("Close points, short prefixes:")
	pairs := [][4]float64{
		{13.00763, 77.59369, 13.00799, 77.59369},
		{0.0002, 0.0002, -0.0002, -0.0002},
	}
	for _, p := range pairs {
		a, b := encode(p[0], p[1], 8), encode(p[2], p[3], 8)
		fmt.Printf("  %s and %s share %d characters\n", a, b, shared(a, b))
	}
	// Precision 6 has 15 bits per axis.
	width, height := 360.0/(1<<15), 180.0/(1<<15)
	var cells []string
	for _, dy := range []float64{1, 0, -1} {
		for _, dx := range []float64{-1, 0, 1} {
			cells = append(cells, encode(lat+dy*height, lon+dx*width, 6))
		}
	}
	fmt.Println("The 9 cells to search:", strings.Join(cells, " "))
}

In Go: rng is a pointer to one of the two [2]float64 arrays, because an array assigned to a variable would be copied and the halving would be lost.

Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go

Swift 6.4 · main.swift

let base32 = Array("0123456789bcdefghjkmnpqrstuvwxyz")

func encode(_ lat: Double, _ lon: Double, precision: Int) -> String {
  // Even bits halve the longitude, odd bits the latitude.
  var latRange = (-90.0, 90.0)
  var lonRange = (-180.0, 180.0)
  var cell = ""
  var value = 0
  for i in 0..<5 * precision {
    let isLon = i % 2 == 0
    let range = isLon ? lonRange : latRange
    let x = isLon ? lon : lat
    let mid = (range.0 + range.1) / 2
    let halved = x >= mid ? (mid, range.1) : (range.0, mid)
    value = value * 2 + (x >= mid ? 1 : 0)
    if isLon { lonRange = halved } else { latRange = halved }
    if i % 5 == 4 {
      cell.append(base32[value])
      value = 0
    }
  }
  return cell
}

func shared(_ a: String, _ b: String) -> Int {
  zip(a, b).prefix { $0 == $1 }.count
}

let (lat, lon) = (12.97194, 77.59369)
print("Cells that hold the rider:")
for precision in 4...8 {
  print("  precision \(precision): \(encode(lat, lon, precision: precision))")
}
print("Close points, short prefixes:")
let pairs = [
  (13.00763, 77.59369, 13.00799, 77.59369),
  (0.0002, 0.0002, -0.0002, -0.0002),
]
for (lat1, lon1, lat2, lon2) in pairs {
  let a = encode(lat1, lon1, precision: 8)
  let b = encode(lat2, lon2, precision: 8)
  print("  \(a) and \(b) share \(shared(a, b)) characters")
}
// Precision 6 has 15 bits per axis.
let (width, height) = (360.0 / Double(1 << 15), 180.0 / Double(1 << 15))
var cells: [String] = []
for dy in [1.0, 0.0, -1.0] {
  for dx in [-1.0, 0.0, 1.0] {
    cells.append(encode(lat + dy * height, lon + dx * width, precision: 6))
  }
}
print("The 9 cells to search: \(cells.joined(separator: " "))")

In Swift: Tuples are values, so the program builds the halved range and assigns it back to lonRange or latRange; Array of the alphabet indexes its characters by position.

Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main

Ruby 4.0 · main.rb

# frozen_string_literal: true

BASE32 = '0123456789bcdefghjkmnpqrstuvwxyz'

def halve(range, coordinate)
  mid = range.sum / 2
  bit = coordinate >= mid ? 1 : 0
  range[1 - bit] = mid
  bit
end

def encode(lat, lon, precision)
  # Even bits halve the longitude, odd bits the latitude.
  ranges = { lat: [-90.0, 90.0], lon: [-180.0, 180.0] }
  cell = +''
  value = 0
  (5 * precision).times do |i|
    value = (value * 2) + (i.even? ? halve(ranges[:lon], lon) : halve(ranges[:lat], lat))
    next unless i % 5 == 4

    cell << BASE32[value]
    value = 0
  end
  cell
end

def shared(first, second)
  first.chars.zip(second.chars).take_while { |x, y| x == y }.size
end

lat = 12.97194
lon = 77.59369
puts 'Cells that hold the rider:'
(4..8).each { |precision| puts "  precision #{precision}: #{encode(lat, lon, precision)}" }
puts 'Close points, short prefixes:'
[
  [13.00763, 77.59369, 13.00799, 77.59369],
  [0.0002, 0.0002, -0.0002, -0.0002]
].each do |lat1, lon1, lat2, lon2|
  first = encode(lat1, lon1, 8)
  second = encode(lat2, lon2, 8)
  puts "  #{first} and #{second} share #{shared(first, second)} characters"
end
# Precision 6 has 15 bits per axis.
width = 360.0 / (2**15)
height = 180.0 / (2**15)
cells = [1, 0, -1].product([-1, 0, 1]).map do |dy, dx|
  encode(lat + (dy * height), lon + (dx * width), 6)
end
puts "The 9 cells to search: #{cells.join(' ')}"

In Ruby: halve narrows the array it is given in place and returns the bit, so encode only packs bits; Array#product pairs every dy with every dx.

Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb

Kotlin 2.4 · Main.kt

const val BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"

fun encode(
    lat: Double,
    lon: Double,
    precision: Int,
): String {
    // Even bits halve the longitude, odd bits the latitude.
    val latRange = doubleArrayOf(-90.0, 90.0)
    val lonRange = doubleArrayOf(-180.0, 180.0)
    val cell = StringBuilder()
    var value = 0
    for (i in 0 until 5 * precision) {
        val range = if (i % 2 == 0) lonRange else latRange
        val x = if (i % 2 == 0) lon else lat
        val mid = (range[0] + range[1]) / 2
        if (x >= mid) {
            value = value * 2 + 1
            range[0] = mid
        } else {
            value *= 2
            range[1] = mid
        }
        if (i % 5 == 4) {
            cell.append(BASE32[value])
            value = 0
        }
    }
    return cell.toString()
}

fun shared(
    a: String,
    b: String,
): Int = a.zip(b).takeWhile { (x, y) -> x == y }.size

fun main() {
    val lat = 12.97194
    val lon = 77.59369
    println("Cells that hold the rider:")
    for (precision in 4..8) {
        println("  precision $precision: ${encode(lat, lon, precision)}")
    }
    println("Close points, short prefixes:")
    val pairs =
        listOf(
            doubleArrayOf(13.00763, 77.59369, 13.00799, 77.59369),
            doubleArrayOf(0.0002, 0.0002, -0.0002, -0.0002),
        )
    for ((lat1, lon1, lat2, lon2) in pairs) {
        val a = encode(lat1, lon1, 8)
        val b = encode(lat2, lon2, 8)
        println("  $a and $b share ${shared(a, b)} characters")
    }
    // Precision 6 has 15 bits per axis.
    val width = 360.0 / (1 shl 15)
    val height = 180.0 / (1 shl 15)
    val cells = mutableListOf<String>()
    for (dy in intArrayOf(1, 0, -1)) {
        for (dx in intArrayOf(-1, 0, 1)) {
            cells.add(encode(lat + dy * height, lon + dx * width, 6))
        }
    }
    println("The 9 cells to search: ${cells.joinToString(" ")}")
}

In Kotlin: DoubleArray ranges are references, so range[0] = mid narrows the original, and destructuring a DoubleArray reads its first four values as lat1 to lon2.

Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

Dart 3.13 · main.dart

const base32 = '0123456789bcdefghjkmnpqrstuvwxyz';

String encode(double lat, double lon, int precision) {
  // Even bits halve the longitude, odd bits the latitude.
  final latRange = [-90.0, 90.0], lonRange = [-180.0, 180.0];
  final cell = StringBuffer();
  var value = 0;
  for (var i = 0; i < 5 * precision; i++) {
    final (range, x) = i.isEven ? (lonRange, lon) : (latRange, lat);
    final mid = (range[0] + range[1]) / 2;
    if (x >= mid) {
      value = value * 2 + 1;
      range[0] = mid;
    } else {
      value *= 2;
      range[1] = mid;
    }
    if (i % 5 == 4) {
      cell.write(base32[value]);
      value = 0;
    }
  }
  return cell.toString();
}

int shared(String a, String b) {
  var n = 0;
  while (n < a.length && a[n] == b[n]) {
    n++;
  }
  return n;
}

void main() {
  final (lat, lon) = (12.97194, 77.59369);
  print('Cells that hold the rider:');
  for (var precision = 4; precision <= 8; precision++) {
    print('  precision $precision: ${encode(lat, lon, precision)}');
  }
  print('Close points, short prefixes:');
  const pairs = [
    (13.00763, 77.59369, 13.00799, 77.59369),
    (0.0002, 0.0002, -0.0002, -0.0002),
  ];
  for (final (lat1, lon1, lat2, lon2) in pairs) {
    final (a, b) = (encode(lat1, lon1, 8), encode(lat2, lon2, 8));
    print('  $a and $b share ${shared(a, b)} characters');
  }
  // Precision 6 has 15 bits per axis.
  final (width, height) = (360.0 / (1 << 15), 180.0 / (1 << 15));
  final cells = [
    for (final dy in [1, 0, -1])
      for (final dx in [-1, 0, 1])
        encode(lat + dy * height, lon + dx * width, 6),
  ];
  print('The 9 cells to search: ${cells.join(' ')}');
}

In Dart: A record, (lonRange, lon), picks the range and the coordinate, and a collection-for builds the nine cells inside a list literal.

Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart

What every language printed

Cells that hold the rider:
  precision 4: tdr1
  precision 5: tdr1v
  precision 6: tdr1v9
  precision 7: tdr1v9q
  precision 8: tdr1v9qp
Close points, short prefixes:
  tdr1vxyn and tdr4j8n1 share 3 characters
  s0000001 and 7zzzzzzy share 0 characters
The 9 cells to search: tdr1v6 tdr1vd tdr1vf tdr1v3 tdr1v9 tdr1vc tdr1v2 tdr1v8 tdr1vb

A second program measures the cells and the pairs:

Cell sizes at the rider's latitude, and the pairs' distances Python · sizes/cell_sizes.py

# How big a geohash cell is at the rider's latitude, and how far apart the two pairs of close points are: on a
# sphere of the Earth's mean radius, with a cell's size worked out from the bits of each axis.
import math

R = 6_371_000  # metres
METRES_PER_DEGREE = math.pi * R / 180
lat = 12.97194  # the rider, in Bengaluru


def distance_m(lat1, lon1, lat2, lon2):
    """Great-circle distance with the haversine formula."""
    p1, p2, dl = math.radians(lat1), math.radians(lat2), math.radians(lon2 - lon1)
    a = math.sin((p2 - p1) / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2
    return 2 * R * math.asin(math.sqrt(a))


print(f"Cell size at latitude {lat}:")
for precision in range(4, 9):
    lon_bits, lat_bits = (5 * precision + 1) // 2, 5 * precision // 2  # longitude takes the odd bit
    w = 360 / 2**lon_bits * METRES_PER_DEGREE * math.cos(math.radians(lat))
    h = 180 / 2**lat_bits * METRES_PER_DEGREE
    size = f"{w / 1000:.1f} km x {h / 1000:.1f} km" if w >= 1000 else f"{w:.0f} m x {h:.0f} m"
    print(f"  precision {precision}: {size}")

print("The two pairs of close points:")
for pair in [(13.00763, 77.59369, 13.00799, 77.59369), (0.0002, 0.0002, -0.0002, -0.0002)]:
    print(f"  {pair[:2]} and {pair[2:]}: {distance_m(*pair):.0f} m apart")

Output

Cell size at latitude 12.97194:
  precision 4: 38.1 km x 19.5 km
  precision 5: 4.8 km x 4.9 km
  precision 6: 1.2 km x 0.6 km
  precision 7: 149 m x 153 m
  precision 8: 37 m x 19 m
The two pairs of close points:
  (13.00763, 77.59369) and (13.00799, 77.59369): 40 m apart
  (0.0002, 0.0002) and (-0.0002, -0.0002): 63 m apart

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 cell_sizes.py

Every two characters shrink the cell about a thousandfold: at precision 6 a cell here is 1.2 km by 0.6 km, and at 7 it is about 150 m across. The pairs are the trap. A long shared prefix means two points are close, but two close points may share almost nothing: the pair 40 m apart sits on either side of the edge of a 4-character cell and shares 3 characters, and where the equator meets the prime meridian, points 63 m apart share none. So a nearby search never reads only the rider’s own cell. It reads the cell and its 8 neighbours, then keeps the candidates within the radius.

Search the rider's cell and its 8 neighbours

Text description of the diagram

Nine geohash cells of precision 6, each about 1.2 km wide and 0.6 km high, arranged in three rows of three.

Top row, west to east: tdr1v6, tdr1vd, tdr1vf.
Middle row: tdr1v3, then tdr1v9, the rider's cell, then tdr1vc.
Bottom row: tdr1v2, tdr1v8, tdr1vb.

All nine cells share the prefix tdr1v here, but at the edge of a larger cell neighbouring cells can share far fewer characters. A nearby search reads the drivers of all nine cells and keeps those within the search radius.

GPS Coordinate Converter (Lat/Long, DMS, UTM, MGRS) Convert any coordinates or map link to a geohash and other formats, to check the cells of a real place.

Key idea

A geohash is a list of halvings, so a shared prefix means a shared cell; close points across a cell edge share little, which is why a search reads the rider’s cell and the cells around it.

Checkpoint

Check: Geohash halvings and prefixes

Question 1 of 2 After the first halving the rider's longitude range is 0 to 180. The rider is at longitude 77.59369. What does the next longitude halving do?
Choose one answer.

The latitude range is halved instead The range becomes 0 to 90 and the bit is 0, because 77.59369 is below the middle, 90 The range becomes 0 to 45 The range becomes 90 to 180 and the bit is 1

Show the answer: Question 1 of 2

Answer: The range becomes 0 to 90 and the bit is 0, because 77.59369 is below the middle, 90

Each halving compares the coordinate with the middle of its range: at or above it, the bit is 1 and the lower bound moves up; below it, the bit is 0 and the upper bound moves down. 77.59369 < 90, so the range becomes 0 to 90.
Question 2 of 2 Two drivers have the geohashes s0000001 and 7zzzzzzy. What do the two strings tell you about the distance between them?
Choose one answer.

Nothing on their own; they share no prefix, yet these two points are 63 m apart They are on opposite sides of the planet They are at least 1,000 km apart They are exactly 8 cells apart

Show the answer: Question 2 of 2

Answer: Nothing on their own; they share no prefix, yet these two points are 63 m apart

The first halvings split the world at the equator and the prime meridian, so points just either side of where they meet differ from the first character. That is why a search reads the rider's cell and its neighbours.

Practise: the cells around a cell

Write the neighbours of a geohash cell and run the sample tests:

Exercise · Medium · Python

Find the cells around a geohash cell

A nearby search looks up the rider's geohash cell and the cells around it. In cells.py, encode(lat, lon, precision) and bounds(cell) are written for you; bounds returns the cell's (south, north, west, east) edges in degrees. Write neighbours(cell): it returns the geohashes of the same length as cell for every cell that touches it, edge or corner, in any order.

Most cells have 8 neighbours.
Longitude wraps around: the cell east of one that ends at 180 degrees starts at -180.
Nothing lies north of 90 or south of -90 degrees, so a cell on the top or bottom row has only 5 neighbours.

For example, the neighbours of tdr1v9 are tdr1v2, tdr1v3, tdr1v6, tdr1v8, tdr1vb, tdr1vc, tdr1vd and tdr1vf.

Starter code · cells.py

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"


def encode(lat, lon, precision):
    """The geohash of a point, with `precision` characters."""
    lat_range, lon_range = [-90.0, 90.0], [-180.0, 180.0]
    out, value, bits, use_lon = [], 0, 0, True
    while len(out) < precision:
        rng, x = (lon_range, lon) if use_lon else (lat_range, lat)
        mid = (rng[0] + rng[1]) / 2
        if x >= mid:
            value, rng[0] = value * 2 + 1, mid
        else:
            value, rng[1] = value * 2, mid
        use_lon, bits = not use_lon, bits + 1
        if bits == 5:
            out.append(BASE32[value])
            value, bits = 0, 0
    return "".join(out)


def bounds(cell):
    """The cell's (south, north, west, east) edges in degrees."""
    lat_range, lon_range, use_lon = [-90.0, 90.0], [-180.0, 180.0], True
    for ch in cell:
        v = BASE32.index(ch)
        for shift in range(4, -1, -1):
            rng = lon_range if use_lon else lat_range
            mid = (rng[0] + rng[1]) / 2
            if (v >> shift) & 1:
                rng[0] = mid
            else:
                rng[1] = mid
            use_lon = not use_lon
    return lat_range[0], lat_range[1], lon_range[0], lon_range[1]


def neighbours(cell):
    """Geohashes of the same length for every cell that touches `cell`."""
    # Replace this line with your code.
    return []

The sample tests · test_cells.py

from cells import encode, neighbours


def test_a_city_cell():
    """an ordinary cell has 8 neighbours"""
    assert sorted(neighbours("tdr1v9")) == ["tdr1v2", "tdr1v3", "tdr1v6", "tdr1v8", "tdr1vb", "tdr1vc", "tdr1vd", "tdr1vf"]


def test_a_longer_cell():
    """the neighbours have the cell's own length"""
    assert sorted(neighbours("u4pruyd")) == ["u4pruy3", "u4pruy6", "u4pruy7", "u4pruy9", "u4pruyc", "u4pruye", "u4pruyf", "u4pruyg"]


def test_longitude_wraps():
    """cells that touch the 180th meridian have neighbours on the other side"""
    assert sorted(neighbours("rzzz")) == ["2pbn", "2pbp", "8000", "rzzw", "rzzx", "rzzy", "xbp8", "xbpb"]
    assert sorted(neighbours("8")) == ["2", "3", "9", "b", "c", "r", "x", "z"]


def test_nothing_beyond_the_poles():
    """a cell on the top or bottom row has 5 neighbours"""
    assert sorted(neighbours("zzz")) == ["bp8", "bpb", "zzw", "zzx", "zzy"]
    assert sorted(neighbours("000")) == ["001", "002", "003", "pbp", "pbr"]
    assert sorted(neighbours("gzz")) == ["gzw", "gzx", "gzy", "up8", "upb"]


def test_the_rider_and_the_driver():
    """a driver 40 m away across a cell edge is in one of the rider's neighbours"""
    rider, driver = encode(13.00763, 77.59369, 6), encode(13.00799, 77.59369, 6)
    assert rider != driver
    assert driver in neighbours(rider)

A hint

Take the cell's centre and its height and width from bounds(cell). The centre of a neighbour is one height north or south and one width east or west of it; encode that point with len(cell) characters. Skip points whose latitude is not between -90 and 90, and bring longitudes back into range with (lon + 180) % 360 - 180.

The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

Then check yourself on the three ideas above.

Cell edges, cell sizes and the 180th meridian, reproduced Pro: opens with a Pro, Premium or Ultimate pass

A cell index fails where cells meet and where the search reaches further than a cell. This part reproduces each failure with drivers you can count, and derives the rule for choosing a cell size from the search radius.

In this part:

Reproducing the miss at a cell’s edge
Choosing a precision from the radius, with numbers
Where the grid wraps and breaks

1 diagram · 1 runnable example (Python) · about 8 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Read a complete sample first: Design a unique ID generator

Moving drivers at scale: grids, quadtrees and hot cells, measured Pro: opens with a Pro, Premium or Ultimate pass

Ride-hailing and delivery systems index positions that change every few seconds. This part measures three ways of finding the nearest drivers among 50,000, then sizes the write path for a million drivers.

In this part:

A full scan, a grid and a quadtree, measured on 50,000 drivers
Sizing the location write path for a million drivers
Hot cells, and how each scheme copes

1 diagram · 1 runnable example (JavaScript) · about 8 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Choosing a scheme for three products, with a rubric Pro: opens with a Pro, Premium or Ultimate pass

The right scheme follows from the question each product asks of the map. This part works through three products and the numbers that decide each choice, then lists what an interview answer covers at each level.

In this part:

Ride matching: the nearest drivers, seconds old
Restaurant search: places that rarely move, with filters
Surge pricing and demand maps: cells with equal neighbours
Choosing for your own product
A rubric: what each level’s answer covers

about 7 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Interview questions

Fresher to mid · Warm-up

Two places have geohashes that share a long prefix. What does that tell you, and what does it not?

A geohash is built by halving longitude and latitude in turn, five halvings per character, so every prefix is a larger cell that contains the longer one. Two places whose geohashes share 7 characters lie in one cell about 150 m across, so they are close. The converse does not hold: two places a few metres apart on either side of a cell edge can share a short prefix, or none at all where the equator meets the prime meridian. That is why a nearby search reads the rider's cell and its 8 neighbours and then filters the candidates by true distance, instead of comparing prefixes.
Mid to senior

Your nearby-drivers search reads only the rider's geohash cell. Riders near cell edges see "no drivers nearby" while drivers wait 100 m away. Explain why, and fix it without scanning the city.

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Senior to staff

One million drivers send their position every 4 seconds, and riders must see the drivers within 2 km in under 50 ms. Design the store for driver locations: what lives in memory, how is it sharded, and what happens to drivers who stop reporting?

Model answer, Pro. First step and follow-ups
Mid to senior

Choose a cell scheme for each of three products, a ride-matching service, a restaurant search with filters and a surge-pricing map, and defend each choice.

Model answer, Pro. First step and follow-ups

Key takeaways

A geospatial index turns positions into cell keys that ordinary indexes store, then filters the candidates by true distance.
Geohash prefixes nest: a shared prefix means a shared cell, but close points can share no prefix at all.
Every nearby search reads the rider’s cell and its neighbours.
Quadtrees adapt cell size to density, S2 nests cells on a cube, and H3’s hexagons have six equally distant neighbours.

Terms in this lesson

geohash: A position written as base-32 characters by halving the longitude and latitude ranges in turn, five halvings per character. A longer geohash is a smaller cell inside the shorter one.
H3: A grid of hexagons, plus 12 pentagons, that covers the world at 16 resolutions. Every neighbour of a hexagon is the same distance from its centre.
haversine formula: A formula for the great-circle distance between two points on a sphere, computed from their latitudes and longitudes with the sines and cosines of half their differences.
quadtree: A tree that splits a square into four equal quarters, and each quarter again, only where it holds more points than a set limit, so its leaves are small where points crowd and large where they are sparse.
R-tree: A tree index of nested rectangles. Each node's box encloses the boxes or shapes below it, so a search descends only into boxes that overlap the area asked for; PostGIS's GiST indexes build one.
S2 cells: The hierarchy of cells S2 makes by projecting the sphere onto the six faces of a cube, numbered with 64-bit ids along a Hilbert curve, from whole faces down to leaf cells about 1 cm across.

References

H3 documentation: Overview of the H3 geospatial indexing system (H3 project)
H3 documentation: Tables of cell statistics across resolutions (H3 project)
H3 documentation: Aggregation (why hexagons) (H3 project)
H3 documentation: Indexing (aperture 7 and containment) (H3 project)
H3 documentation: H3 index representations (H3 project)
S2 Geometry: S2 cell hierarchy (S2 Geometry project)
S2 Geometry: overview (S2 Geometry project)
PostGIS documentation: ST_GeoHash (PostGIS Project)
Introduction to PostGIS: Spatial indexing (PostGIS Project)
Redis documentation: GEOADD (how geospatial indexes are stored) (Redis)
Redis documentation: Geospatial data type (Redis)
Elasticsearch documentation: Geohash grid aggregation (cell dimensions) (Elastic)
OpenStreetMap: Copyright and licence (OpenStreetMap Foundation)

Report a problem with this lesson

In this module: Search, geospatial and probabilistic data structures

Inverted indexes, analysers and BM25 ranking Free: 25 minutes
Search for Indian languages and mixed scripts Free intro, Pro: 4 of 25 minutes free
Typeahead: tries and top-k per prefix Free intro, Pro: 5 of 20 minutes free
Geospatial indexing: geohash, quadtrees, S2, H3 Free core, Pro depth: 8 of 25 minutes free
Bloom and cuckoo filters: membership at scale Free intro, Pro: 5 of 20 minutes free
HyperLogLog, Count-Min and heavy hitters Free intro, Pro: 5 of 20 minutes free
Vector search for system designers Free intro, Pro: 4 of 20 minutes free

Your country

Geospatial indexing: geohash, quadtrees, S2, H3

What you will learn

Before you start

What you will learn

Before you start

Why nearby search needs its own index

Four ways to cut the map into cells

Geohash names nested cells by halving the map

Practise: the cells around a cell

Find the cells around a geohash cell

Results of the sample tests

Cell edges, cell sizes and the 180th meridian, reproduced Pro: opens with a Pro, Premium or Ultimate pass

Moving drivers at scale: grids, quadtrees and hot cells, measured Pro: opens with a Pro, Premium or Ultimate pass

Choosing a scheme for three products, with a rubric Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Two places have geohashes that share a long prefix. What does that tell you, and what does it not?

Your nearby-drivers search reads only the rider's geohash cell. Riders near cell edges see "no drivers nearby" while drivers wait 100 m away. Explain why, and fix it without scanning the city.

One million drivers send their position every 4 seconds, and riders must see the drivers within 2 km in under 50 ms. Design the store for driver locations: what lives in memory, how is it sharded, and what happens to drivers who stop reporting?

Choose a cell scheme for each of three products, a ride-matching service, a restaurant search with filters and a surge-pricing map, and defend each choice.

Key takeaways

References

Related tools