Internals
CSR format
How edges are stored for fast traversal
KiteDB uses Compressed Sparse Row (CSR) format to store graph edges. CSR is a standard format for sparse matrices: each node's neighbors are stored next to each other, so traversal is fast and the memory overhead is small.
The problem with naive edge storage
Consider a graph with 100,000 nodes and 1 million edges.
100K × 100K = 10 billion entries
Actual edges: 1M (0.01% used)
99.99% of the matrix is empty space
Problem: pointer chasing. Each hop goes to a random memory location.
Cache miss ~100 ns
Cache hit ~1 ns
1,000 edges × 100 ns = 100 μs spent waiting on RAM
The CSR solution
CSR stores all edges in two flat arrays: offsets and destinations. Edges are found by array index rather than by following pointers, and the arrays only hold edges that exist.
Graph
Concatenate every node's destinations:
Record where each node's edges start:
Highlighted: node A's edges, and the two offsets that bound them.
How traversal works
Finding a node's neighbors takes two array lookups:
Who does A connect to?
start = offsets[0] = 0
end = offsets[1] = 2
destinations[0:2] = [B, C]
Who does D connect to?
start = offsets[3] = 4
end = offsets[4] = 4
destinations[4:4] = [] (no edges)
Algorithm
start = offsets[node]
end = offsets[node + 1]
return destinations[start:end]
Why it's fast: memory layout
Linked listscattered
Random locations, so each hop can miss the cache.
CSRcontiguous
Sequential addresses, so the CPU prefetcher can load ahead.
Bidirectional edges
KiteDB stores edges in both directions, so traversal is fast either way:
Out-edgesA → B
out_offsets = [0, 2, 3, 4, 4]
out_dst = [B, C, D, A]
Who does A follow?
In-edgesA ← C
in_offsets = [0, 1, 2, 3, 4]
in_src = [C, A, A, B]
Who follows A?
Tradeoff: 2× edge storage, in exchange for O(1) traversal in both directions.
Edge types and sorting
Real graphs have different edge types (follows, likes, knows). KiteDB stores edge types in a parallel array, sorted within each node:
0 = KNOWS
1 = LIKES
Edges are sorted by (etype, dst) within each node, so:
- Binary search finds a specific edge type
- Scanning stops once it passes the wanted type
- Getting A's KNOWS edges doesn't scan all of A's edges
Edge existence check
To check if edge A→B exists with type KNOWS:
function hasEdge(src: NodeID, etype: EdgeType, dst: NodeID): boolean { const start = offsets[src]; const end = offsets[src + 1]; // Binary search for etype within [start, end) const typeStart = binarySearchStart(etypes, start, end, etype); const typeEnd = binarySearchEnd(etypes, start, end, etype); // Binary search for dst within type range return binarySearch(destinations, typeStart, typeEnd, dst);}// Complexity: O(log k) where k = number of edges from srcPerformance comparison
| Operation | CSR | Linked list |
|---|---|---|
| Start traversal | O(1) – two array lookups | O(1) – follow pointer |
| Iterate k neighbors | O(k) – sequential read | O(k) – but cache misses |
| Edge existence | O(log k) – binary search | O(k) – linear scan |
| Cache behavior | Excellent – prefetcher works | Poor – random access |
Next steps
- Snapshot and delta – how CSR fits into the storage model
- Key index – how node lookups work
- Performance – optimization techniques