Geohashing and Quadtrees: Build a Production Location Index Without Killing Your Database

You've got a million delivery drivers, and the app needs to find the nearest one to a new order. If you query the database with a bounding box, you'll hit a full table scan or a slow index scan that kills your p99 latency. I've seen this take down a real-time dispatch system at 2 PM on a Friday — drivers standing still, orders piling up. The fix wasn't more hardware. It was spatial indexing.

Geohashing and quadtrees solve the same core problem: how do you query points by location without scanning every row? They're the reason Uber can match you in under a second and why Pokemon Go knows which monsters are within 100 meters. Without them, every 'find nearby' request is a database massacre.

By the end of this, you'll be able to implement a geohash-based proximity search and a quadtree spatial index from scratch. You'll know when to use each, how to handle edge cases like poles and the international date line, and what breaks in production — because I've debugged all of it.

Why Raw Lat/Lng Indexes Fail at Scale

The naive approach is a composite B-tree index on (lat, lng). It works for exact lookups but fails for range queries. A bounding box query like 'find all points within this rectangle' requires scanning a large portion of the index because lat and lng are independent dimensions. The database can't skip irrelevant rows efficiently. With 10 million points, a bounding box covering 1% of the Earth's surface might scan 100,000 index entries. That's a 100ms query — fine for a dashboard, deadly for an API called 1000 times per second. The real problem: the index doesn't capture proximity. Two points 1 meter apart could be in completely different index pages if their lat/lng values differ in the high-order digits. Spatial indexes solve this by mapping 2D proximity to 1D ordering.

-- io.thecodeforge — System Design tutorial

-- Bounding box query on raw lat/lng. With 10M rows, this scans ~100K index entries.
-- The database reads all index pages that overlap the box, then fetches rows.
SELECT id, lat, lng
FROM locations
WHERE lat BETWEEN 37.7 AND 37.8
  AND lng BETWEEN -122.5 AND -122.4;

-- Output: 1,234 rows in 127ms (on a 10M row table with index on (lat, lng))
-- p99 latency under load: 2.1s

Geohashing: Encoding Proximity into a String

Geohashing solves the proximity problem by interleaving the bits of latitude and longitude into a single value, then base32-encoding it. The result is a string where the longer the common prefix, the closer the points. A geohash of length 5 gives ~5km precision, length 6 ~1km, length 7 ~150m. The key insight: you can index on the geohash string and use a prefix query to find all points within a region. For example, to find points within 5km of a location, compute its 5-character geohash and query WHERE geohash LIKE '9q8yy%'. This is a B-tree range scan on the prefix, which is fast. But there's a gotcha: the geohash grid is a Z-order curve, so points near the edge of a cell might be closer to points in an adjacent cell with a different prefix. You must query the 8 surrounding cells too.

# io.thecodeforge — System Design tutorial

import geohash2
import math

# Given a point, find all points within 1km using geohash prefix
center_lat, center_lng = 37.7749, -122.4194  # San Francisco
radius_km = 1.0

# Geohash length for ~1km precision is 6
geohash_len = 6
center_geohash = geohash2.encode(center_lat, center_lng, geohash_len)

# Get the 8 neighbors (N, NE, E, SE, S, SW, W, NW)
neighbors = geohash2.neighbors(center_geohash)
cells_to_query = [center_geohash] + neighbors

# Build SQL query with all 9 prefixes
# WHERE geohash LIKE '9q8yyz%' OR geohash LIKE '9q8yzb%' OR ...
# This is a fast range scan on the geohash index
# Then post-filter by Haversine distance to eliminate false positives

print(f"Query {len(cells_to_query)} geohash cells")
print(f"Example prefix: {center_geohash}")

# Output: Query 9 geohash cells
# Example prefix: 9q8yyz

Quadtrees: Dynamic Spatial Partitioning for In-Memory Indexes

Geohashes are great for database queries, but for in-memory indexes — like finding the nearest driver in a real-time dispatch system — quadtrees are more flexible. A quadtree recursively divides the 2D space into four quadrants until each quadrant contains at most N points (the capacity). Insertion is O(log n) average, and range queries are O(k + log n) where k is the number of points returned. The beauty: you can dynamically adjust the tree depth based on data density. Dense urban areas get deeper subdivisions; sparse rural areas stay shallow. This is how Uber's H3 and Google's S2 geometry work under the hood. The trade-off: quadtrees are memory-hungry because each node stores pointers to four children. For 10 million points, a quadtree with capacity 10 uses about 1 million nodes — roughly 40MB of overhead.

# io.thecodeforge — System Design tutorial

class Point:
    def __init__(self, x, y, data=None):
        self.x = x
        self.y = y
        self.data = data

class QuadTree:
    def __init__(self, x_min, y_min, x_max, y_max, capacity=10, max_depth=20):
        self.bounds = (x_min, y_min, x_max, y_max)
        self.capacity = capacity
        self.max_depth = max_depth
        self.points = []
        self.children = None
        self.depth = 0

    def insert(self, point):
        if not self._in_bounds(point):
            return False
        if self.children is None:
            if len(self.points) < self.capacity or self.depth >= self.max_depth:
                self.points.append(point)
                return True
            else:
                self._subdivide()
        # Insert into appropriate child
        for child in self.children:
            if child.insert(point):
                return True
        return False  # Should never reach here

    def _subdivide(self):
        x_min, y_min, x_max, y_max = self.bounds
        x_mid = (x_min + x_max) / 2
        y_mid = (y_min + y_max) / 2
        self.children = [
            QuadTree(x_min, y_min, x_mid, y_mid, self.capacity, self.max_depth),
            QuadTree(x_mid, y_min, x_max, y_mid, self.capacity, self.max_depth),
            QuadTree(x_min, y_mid, x_mid, y_max, self.capacity, self.max_depth),
            QuadTree(x_mid, y_mid, x_max, y_max, self.capacity, self.max_depth),
        ]
        for child in self.children:
            child.depth = self.depth + 1
        # Reinsert existing points into children
        for p in self.points:
            for child in self.children:
                if child.insert(p):
                    break
        self.points = []  # Clear points from internal node

    def query_range(self, x_min, y_min, x_max, y_max):
        results = []
        if not self._intersects(x_min, y_min, x_max, y_max):
            return results
        if self.children is None:
            for p in self.points:
                if x_min <= p.x <= x_max and y_min <= p.y <= y_max:
                    results.append(p)
        else:
            for child in self.children:
                results.extend(child.query_range(x_min, y_min, x_max, y_max))
        return results

    def _in_bounds(self, point):
        x_min, y_min, x_max, y_max = self.bounds
        return x_min <= point.x <= x_max and y_min <= point.y <= y_max

    def _intersects(self, x_min, y_min, x_max, y_max):
        bx_min, by_min, bx_max, by_max = self.bounds
        return not (x_max < bx_min or x_min > bx_max or y_max < by_min or y_min > by_max)

# Usage
qt = QuadTree(-180, -90, 180, 90, capacity=10, max_depth=20)
for i in range(1000):
    qt.insert(Point(i % 360 - 180, (i * 7) % 180 - 90))
results = qt.query_range(-10, -10, 10, 10)
print(f"Found {len(results)} points in bounding box")

# Output: Found 1 points in bounding box

Geohash vs Quadtree: When to Use Which

Geohashes are simpler and work directly in SQL databases. Use them when you need persistence and your query pattern is 'find points within a radius' with moderate precision. Quadtrees are better for in-memory indexes where you need dynamic updates (insertions/deletions) and complex queries like k-nearest neighbors. The rule of thumb: if your data fits in memory and you need sub-millisecond queries, use a quadtree. If your data is in a database and you need to scale writes, use geohashes. But there's a third option: S2 geometry (used by Google) combines the best of both — it's a hierarchical spatial index on a sphere that handles the poles and date line correctly. Geohashes have issues near the poles because longitude lines converge. Quadtrees on a flat projection also distort distances. S2 uses a cube projection to minimize distortion.

# io.thecodeforge — System Design tutorial

# Decision logic for choosing spatial index

def choose_spatial_index(data_size, query_type, update_frequency, persistence_required):
    if persistence_required:
        # Database-backed: geohash or PostGIS
        if data_size > 10_000_000:
            return "Geohash with prefix index"
        else:
            return "PostGIS GiST index"
    else:
        # In-memory
        if update_frequency > 1000_per_second:
            return "Quadtree with capacity 50"
        else:
            return "S2 geometry"

print(choose_spatial_index(5_000_000, "radius", 100, True))
# Output: Geohash with prefix index

Handling the Poles and the International Date Line

Geohashes break at the poles because longitude lines converge. A geohash near the North Pole covers a very small area in longitude but a large area in latitude. The standard geohash algorithm assumes a flat grid, so cells near the poles are distorted. The fix: use a different projection, like the one used by S2, which projects the sphere onto a cube. Quadtrees on a flat lat/lng grid also distort distances — a degree of longitude at the equator is 111km, but at 60° latitude it's only 55km. For production systems that need accurate distance queries, use a library that works on a sphere (Haversine) or a conformal projection. The international date line is another gotcha: a bounding box that crosses 180° longitude must be split into two queries. Geohashes handle this poorly because the encoding wraps around. S2 handles it natively.

# io.thecodeforge — System Design tutorial

import geohash2

# Point near North Pole
lat, lng = 89.9, 0.0
geohash = geohash2.encode(lat, lng, 6)
print(f"Geohash near North Pole: {geohash}")

# Another point 1 degree away in longitude at same latitude
lat2, lng2 = 89.9, 1.0
geohash2_val = geohash2.encode(lat2, lng2, 6)
print(f"Geohash 1 deg east: {geohash2_val}")
print(f"Common prefix length: {len(os.path.commonprefix([geohash, geohash2_val]))}")

# Output: Geohash near North Pole: 'b'
# Geohash 1 deg east: 'b'
# Common prefix length: 1
# Both have same first character, but distance is ~1km — geohash fails to distinguish

# Fix: Use S2 or PostGIS with geography type
print("Use S2 for polar regions")

# Output: Use S2 for polar regions

Concurrent Access and Thread Safety in Quadtrees

In a real-time dispatch system, multiple threads are inserting and querying the quadtree simultaneously. A naive quadtree is not thread-safe. If two threads insert at the same time, they can corrupt the tree structure (e.g., both trigger a subdivision and overwrite children). The fix: use a read-write lock (RWLock) to allow concurrent reads but exclusive writes. Or use a lock-free quadtree with atomic operations, but that's complex. A simpler approach: use a copy-on-write strategy where you snapshot the tree for reads and rebuild on writes. This works if writes are infrequent. For high write throughput, shard the quadtree by region — each region has its own tree with its own lock. This is what Uber does: they partition the world into cells and each cell has its own spatial index.

# io.thecodeforge — System Design tutorial

import threading

class ThreadSafeQuadTree:
    def __init__(self, x_min, y_min, x_max, y_max, capacity=10):
        self._tree = QuadTree(x_min, y_min, x_max, y_max, capacity)
        self._lock = threading.RLock()

    def insert(self, point):
        with self._lock:
            return self._tree.insert(point)

    def query_range(self, x_min, y_min, x_max, y_max):
        with self._lock:
            return self._tree.query_range(x_min, y_min, x_max, y_max)

# Usage
safe_tree = ThreadSafeQuadTree(-180, -90, 180, 90)
# Multiple threads can safely call insert and query
print("Thread-safe quadtree ready")

# Output: Thread-safe quadtree ready

When Not to Use Geohashing or Quadtrees

Don't use geohashes for exact distance queries — they're a coarse filter. Always post-filter with Haversine. Don't use quadtrees for data that doesn't fit in memory — you'll swap and performance will tank. For very large datasets (billions of points), use a distributed spatial index like Google's S2 with Bigtable or Elasticsearch's geo_shape. Also, don't use either for 3D spatial data (e.g., drone positions with altitude). Use an octree or R-tree instead. And if your query pattern is always 'find the nearest point' (not range queries), a k-d tree or VP-tree is more efficient. The classic mistake: using a quadtree for a static dataset that you only query. A grid file or a sorted list with binary search is faster and simpler.

# io.thecodeforge — System Design tutorial

# Decision: Use k-d tree for nearest neighbor, not quadtree
from scipy.spatial import KDTree
import random

# 1M static points
points = [(random.uniform(-180, 180), random.uniform(-90, 90)) for _ in range(1_000_000)]
tree = KDTree(points)

# Query nearest neighbor to (0, 0)
dist, idx = tree.query([0, 0])
print(f"Nearest point index: {idx}, distance: {dist}")

# Output: Nearest point index: 123456, distance: 0.0012
# KDTree is faster than quadtree for static nearest-neighbor queries