Definition:
Spatial Indexing Architecture is a data structure design that organizes geographic or multidimensional data to enable fast queries like “find all objects near this location” or “what intersects with this area.” Instead of checking every object one-by-one, spatial indexes divide space into hierarchical regions for efficient searching.
Think of it like organizing a library: instead of checking every book to find one about Paris, you use the catalog system that groups books by topic and location.
| Index Type | How It Works | Best For | Examples |
|---|---|---|---|
| R-Tree | Groups nearby objects in bounding boxes | General purpose, range queries | PostGIS, MongoDB |
| Quadtree | Recursively divides 2D space into 4 quadrants | 2D maps, collision detection | Game engines, GIS |
| KD-Tree | Binary tree splitting on alternating dimensions | Nearest neighbor search | Machine learning |
| Geohash | Encodes locations as strings, nearby = similar prefix | Distributed databases | Redis, Elasticsearch |
| S2 Geometry | Divides Earth’s surface into cells | Global-scale mapping | Google Maps, Uber |
Example:
Uber - Finding Nearby Drivers
Problem: User requests ride in San Francisco
- 5,000 drivers currently active in SF
- Need to find closest 10 drivers
- Must respond in < 100ms
Architecture: S2 Geometry + Geohash
┌────────────────────────────────────────────────┐
│ San Francisco (divided into cells) │
├────────────────────────────────────────────────┤
│ │
│ ┌──────┬──────┐ ┌──────┬──────┐ │
│ │ Cell │ Cell │ │ Cell │ Cell │ │
│ │ A1 │ A2 │ │ B1 │ B2 │ │
│ │ 🚗🚗 │ │ │ 🚗 │ 🚗🚗🚗│ │
│ └──────┴──────┘ └──────┴──────┘ │
│ │
│ ┌──────┬──────┐ ┌──────┬──────┐ │
│ │ Cell │ Cell │ │ Cell │ Cell │ │
│ │ C1 │ C2 │ │ D1 │ D2 │ │
│ │ 🚗 │ 🚗🚗 │ │ │ 🚗 │ │
│ └──────┴──────┘ └──────┴──────┘ │
│ │
│ 📍 User location in Cell B2 │
└────────────────────────────────────────────────┘