Designing Google Maps: Geospatial Indexing and Routing Algorithms

TL;DR (Core Architecture): Designing Google Maps requires separating the system into three distinct systems: Map Rendering (Pre-computed vector tiles via CDNs), Geospatial Search (QuadTree/Geohash indexing in Elasticsearch/PostGIS), and Navigation Routing (Graph pre-computation using contraction hierarchies and A* search).

"Design Google Maps" is one of the most encompassing system design questions asked at Google, Uber, and Meta. It tests your knowledge of specialized data structures and graph algorithms that are rarely used in standard CRUD web apps.

Back-of-the-envelope Estimation

Let's understand the scale of planetary data.

Metric	Value	Justification
Active Users	1 Billion+ DAU	Global scale, generating extreme read traffic for map tiles and routing.
Road Graph Size	Tens of Terabytes	Billions of road segments (edges) and intersections (nodes). Requires distributed graph processing (Pregel/Spark).
Map Tiles Storage	~50-100 PetaBytes	3D models, satellite imagery, and vector grids across 21 zoom levels globally.

High-Level Architecture

Rendering architecture diagram...
Mermaid Source Code
graph TD
    A[Mobile Client] --> B(API Gateway / Edge POPS)
    
    B -- Fetch Map Tiles --> C[Global CDN Cache]
    C -.-> D[Object Storage - S3 / GCS]
    
    B -- "Search 'Coffee'" --> E(Geospatial Search Service)
    E --> F[(Elasticsearch / QuadTree Index)]
    
    B -- Get Directions --> G(Navigation Routing Service)
    G --> H[(In-Memory Graph Cache - Redis/C++)]
    H -.-> I[Graph Pre-Computation Batch Workers]

Deep Dive: The Three Pillars of Google Maps

1. Geospatial Indexing: Finding the Nearest Coffee Shop

If a user searches for "Coffee" near them, you cannot execute a SQL query: SELECT * FROM places WHERE type='coffee' AND lat > X AND lat < Y. Standard B-Trees cannot efficiently index two-dimensional localized data.

The Solution: Space-Filling Curves & Trees. We must boil 2D space down into 1D strings that databases can index.

• Geohash: Divides the world into an alphanumeric grid grid. Two locations that are close to each other will share the same prefix (e.g., 9q8yy and 9q8yf). We can use a standard database index with a LIKE '9q8%' query.
• QuadTrees (Recommended): A tree structure where each node (representing a square of the map) has exactly four children. If a square contains more than 100 places, we subdivide it into 4 smaller squares. This dynamically handles the difference in density between Manhattan and the Sahara Desert.

2. Navigation Routing: The A* Graph Problem

The world's road network is a massive directed weighted graph. Nodes are intersections; Edges are roads. Edge weights are the expected travel time.

Using Dijkstra's algorithm to find the shortest path from NY to LA on a graph with billions of edges takes hours, not milliseconds.

The Solution: Pre-computation and A (A-Star).*

1. The Heuristic (A):* A* improves Dijkstra by adding a heuristic (e.g., "straight-line distance to the target"). It aggressively prioritizes searching roads that move physically closer to the destination, ignoring roads going the wrong way.
2. Contraction Hierarchies / Highway Prefixing: The backend batch processors run daily MapReduce jobs. They pre-compute the fastest paths between all major highway on-ramps. When routing NY to LA:
   • Your phone calculates local roads to the nearest NY highway.
   • It fetches the O(1) pre-computed highway route to the LA off-ramp.
   • It calculates local roads from the off-ramp to the destination. This reduces a billion-node search space down to a few thousand nodes.

3. Rendering the World: Vector Map Tiles

Downloading raw image files for every map movement consumes excessive bandwidth and prohibits 3D rotation.

The Solution: Vector Tiles. Instead of transmitting JPEGs, the server transmits Protocol Buffers containing mathematical instructions: "Draw a thick yellow line here with coordinate X1 to X2. Draw a green polygon for a park here." The mobile device's GPU executes these instructions to render the map natively at 60 FPS. To optimize, the world is sliced into 256x256 pixel grid "Tiles" at various Zoom Levels (0 to 21). When you pan the map, you simply download the specific Grid ID for your viewport from an Edge CDN.