The road network is a graph. Intersections are nodes, road segments are edges, weights are travel time. A CS textbook covers that in two sentences. What the textbook skips is how you store a graph with hundreds of millions of nodes and query it in milliseconds.

The Naive Approach Breaks Fast#

A normalized relational schema works: intersections table, road_segments table with from_id, to_id, travel_time_seconds. Routing algorithms traverse edges. Each traversal step is a query on road_segments filtered by from_id.

Even with an index on from_id, doing this millions of times per route is too slow. The round-trip cost of individual SQL queries kills you.

CSR Format#

Real routing systems load the graph into memory using Compressed Sparse Row (CSR) format. Two arrays: one holds all outgoing edges for every node concatenated, another holds where each node’s edges start in the first array.

Traversing from node X is a single array slice, edges[offsets[X]..offsets[X+1]]. No query. No disk I/O. Cache-friendly sequential memory access.

The whole road network of a country fits in a few gigabytes in CSR format. You load it once on startup and never touch the database during routing.

Hierarchical Layers#

You still can’t fit every local street globally. The solution is to split the graph into layers.

Motorways and trunk roads go into a highway layer, replicated everywhere. Local streets are partitioned geographically and only loaded for the first and last kilometer of a trip. Most long routes spend nearly all their path on the highway layer.

graph TD A[Highway Layer - globally replicated] --> B[Regional Layer - loaded on demand] B --> C[Local Streets - start and end of trip only] style A fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style B fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style C fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff

At Oracle#

We had a configuration dependency graph for network slices. Each NSSAI config pointed to parent configs it depended on. Traversal was slow until we noticed 95% of queries touched the same 200 top-level configs. We preloaded those into an in-process cache and fetched leaf configs on demand. Lookup time dropped from 2+ seconds to 30ms on 2 million config records. Same principle as the highway layer: hot shared data in memory, cold data fetched only when needed.

What I’m Learning#

The storage format matters as much as the algorithm. CSR turns graph traversal from repeated SQL queries into array reads. Hierarchical decomposition keeps globally shared data small and partitions local data by geography.

Have you worked with graph data at production scale, and how did you store adjacency?