Spatial Indexing in System Design: QuadTree, GeoHash, and H3 Explained

Introduction

Suppose you are designing:

• Uber
• DoorDash
• Google Maps
• Pokémon Go
• Nearby Friends
• Food Delivery
• Ride Matching

Sooner or later, a simple question appears:

“Find everything near this location.”

At small scale, you can scan all records and compute distances.

At Uber scale, with millions of drivers and riders continuously updating their locations, that approach becomes impossible.

This is where spatial indexing comes in.

Spatial indexes allow us to organize the Earth’s surface into manageable regions so that nearby searches, aggregations, and heatmaps can be performed efficiently.

In this article, we’ll compare three popular approaches:

1. QuadTree
2. GeoHash
3. H3

and discuss when each one should be used.

Why Spatial Indexing?

Imagine storing every driver location as:

(driverId, latitude, longitude)

When a rider requests a ride, we need to find:

Nearest 10 drivers within 3 km

Without an index:

O(N)

We must scan all drivers.

With a spatial index:

O(log N)

or even better in practice.

Option 1: QuadTree

Core Idea

QuadTree recursively divides space into four quadrants.

           Root
        /  |  |  \
       NW NE SW SE

When a region becomes crowded, it splits into four smaller regions.

Large Cell
    ↓
Split
    ↓
4 Smaller Cells

Advantages

Efficient range queries

Adaptive to data density

Good for in-memory structures

Natural hierarchical organization

Problems

Pointer-heavy structure

Difficult to distribute

Hotspot regions become complex

Tree traversal overhead

Not friendly for Redis/Kafka partitioning

Typical Usage

QuadTree works well inside:

• Game engines
• GIS systems
• In-memory indexing

but is less common in modern distributed architectures.

Option 2: GeoHash

GeoHash takes a different approach.

Instead of building a tree structure, it converts latitude and longitude into a string.

Example:

9q8yy

Nearby locations often share the same prefix.

9q8
├── 9q8x
├── 9q8y
└── 9q8z

The longer the string:

Higher Precision

Why Engineers Love GeoHash

GeoHash is extremely simple.

You can directly use it as:

Redis Key
Database Index
Kafka Partition Key

Examples:

driver:9q8yy
restaurant:9q8yz

Prefix matching becomes location matching.

Advantages

Simple implementation

Easy Redis integration

Distributed-system friendly

Natural geo-sharding

Problems

Neighbor Problem

Two adjacent locations may belong to different prefixes.

A | B

Although physically adjacent:

GeoHash(A) != GeoHash(B)

A nearby search may need to query multiple prefixes.

Usually:

Current Cell
+ 8 Neighbor Cells

Uneven Cell Shapes

GeoHash cells are rectangular.

At different latitudes:

• Cell size changes
• Distances become distorted

Aggregation Is Awkward

Grouping by prefix works, but isn’t always clean.

Heatmaps and analytics become harder.

Option 3: H3

H3 was created by Uber.

Instead of rectangles, H3 divides Earth into hexagons.

Why Hexagons?

Hexagons provide:

• Uniform coverage
• Better neighbor relationships
• More balanced spatial representation

Every cell has:

H3 Index

such as:

8928308280fffff

which uniquely identifies the cell.

Hierarchical Resolution

H3 supports multiple resolutions.

Resolution 0
    ↓
Resolution 1
    ↓
Resolution 2
    ↓
...
    ↓
Resolution 15

Each cell can be expanded or rolled up.

Fine-grained
    ↓
Aggregation
    ↓
Coarse-grained

Why Uber Likes H3

Neighbor Queries

Find nearby cells:

kRing(cell, k)

No GeoHash boundary headache.

Aggregation

Perfect for:

• Heatmaps
• Driver density
• Demand forecasting
• Regional statistics

Example:

Orders per H3 Cell

instead of:

Orders per GeoHash Prefix

Distributed Systems

H3 IDs are excellent keys.

Kafka Partition
Redis Key
Database Shard

Example:

h3:8928308280fffff

Handling Data Skew

Popular cities:

• NYC
• San Francisco
• London

generate huge traffic.

H3’s hierarchical structure makes hotspot management easier than GeoHash.

Typical Uber Architecture

Driver GPS
      │
      ▼
Convert to H3
      │
      ▼
Kafka
      │
      ▼
Flink Streaming
      │
      ▼
Pre-Aggregation
      │
      ▼
Redis

Store multiple resolutions:

res=10
res=9
res=8
...
res=5

When users zoom out:

Read coarse cells

When users zoom in:

Read detailed cells

This creates a smooth map experience.

QuadTree vs GeoHash vs H3

Which One Should You Choose?

Use QuadTree

When:

• Mostly in-memory
• GIS applications
• Dynamic spatial partitioning

Use GeoHash

When:

• Simplicity matters
• Redis indexing
• Geo-sharding

Use H3

When:

• Large-scale geo systems
• Heatmaps
• Aggregation
• Ride-sharing
• Food delivery
• Modern distributed architectures

Final Thoughts

Spatial indexing is one of those topics that quietly appears behind many large-scale systems.

GeoHash made geo-partitioning practical.

H3 pushed the idea further by introducing hierarchical hexagonal cells that support efficient neighbor queries, aggregation, and distributed processing.

If you’re preparing for system design interviews, understanding the trade-offs between QuadTree, GeoHash, and H3 is often more valuable than memorizing APIs, because these structures directly influence scalability, latency, and data distribution decisions.