Adjacency Lists

A graph storage choice with no single right answer.

Adjacency matrix: N x N boolean array. M[i][j] = 1 iff edge from i to j.

• Pros: O(1) edge lookup.
• Cons: O(N²) space — useless for sparse graphs.
• Used: small dense graphs.

Adjacency list: per node, a list of neighbors.

• Pros: O(degree) traversal, O(N + E) space.
• Cons: edge lookup is O(degree).
• Used: most graph DBs.

Edge list (CSR for static graphs):

• Two arrays: offsets[N+1], targets[E].
• offsets[i] = start index in targets[] for node i.
• Compact, cache-friendly.
• Good for read-heavy / batch graph algorithms.

Neo4j storage:

• Each node: pointer to first relationship.
• Each relationship: pointers to (source, target, prev_rel, next_rel) — doubly-linked relationship list per node.
• "Index-free adjacency": traversing a relationship = pointer dereference. O(1) per hop.

Trade-off vs SQL:

• SQL with FK + index: edge lookup ~ B-tree height (4-5 ops).
• Graph DB: 1 pointer (constant).
• For deep traversals (5+ hops), graph DB is 10-100x faster.

For 100M+ edge graphs:

• Use Compressed Sparse Row (CSR) for static analytics.
• Batch updates separately, periodically merge into CSR.

Property storage:

• Inline: small properties (id, name) inline in the node.
• External: large properties (text, blobs) in separate file referenced by pointer.

Caching:

• Nodes/edges visited by traversal often have locality.
• Page cache + targeted in-memory caches help.