Index-free adjacency

Deep dive

How it works

In: node id u (and edge-list inserts (src, dst)) · Out: the neighbours of u, visited one by one · State: head[u] (first edge id) and per edge dst, next · Cost: one array read for head[u], then one dependent read per edge: O(deg(u)); insert O(1)

1. Allocate edge records in arrival order; each holds dst and next, the id of the next edge of the same source (NONE ends the chain).
2. Insert (s, d): write the new record with next = head[s], set head[s] to its id. No search, no rebalancing.
3. Neighbours of u: e = head[u]; while e != NONE: yield dst[e], e = next[e].
4. Two hops: run step 3 for each neighbour; deduplicate with a sort or hash set.
5. For "followers of u" keep a second structure over reversed edges; a directed edge needs two lists.
6. Neo4j shares one relationship record between both endpoints, with prev/next ids per endpoint (doubly linked), so unlinking on delete is O(1) given the id. A node's chain mixes types and directions: walk and filter.

Code

Three layouts on one random follow graph: linked chains, a sorted edge table with binary search (B-tree stand-in), CSR. It asserts that 2-hop sets and followers(0) agree, then times them.

use std::{hint::black_box, time::Instant};
const NONE: u32 = u32::MAX;

trait Adj {
    fn build(n: usize, edges: &[(u32, u32)]) -> Self; // edges = (src, dst), arrival order
    fn each<F: FnMut(u32)>(&self, u: u32, f: F);
}

/// (a) index-free adjacency: node -> first edge; edge -> next edge of the same node.
struct Linked { head: Vec<u32>, dst: Vec<u32>, next: Vec<u32> }
impl Adj for Linked {
    fn build(n: usize, edges: &[(u32, u32)]) -> Self {
        let (mut head, mut dst, mut next) = (vec![NONE; n], vec![], vec![]);
        for (i, &(s, d)) in edges.iter().enumerate() {
            dst.push(d);
            next.push(head[s as usize]); // insert at the chain head: O(1), no search
            head[s as usize] = i as u32;
        }
        Linked { head, dst, next }
    }
    fn each<F: FnMut(u32)>(&self, u: u32, mut f: F) {
        let mut e = self.head[u as usize];
        while e != NONE { f(self.dst[e as usize]); e = self.next[e as usize]; } // one dependent load per edge
    }
}

/// (b) edge table sorted by (src, dst); binary search on src stands in for a B-tree index.
struct Table { e: Vec<(u32, u32)> }
impl Adj for Table {
    fn build(_: usize, edges: &[(u32, u32)]) -> Self { let mut e = edges.to_vec(); e.sort_unstable(); Table { e } }
    fn each<F: FnMut(u32)>(&self, u: u32, mut f: F) {
        let mut i = self.e.partition_point(|x| x.0 < u);
        while i < self.e.len() && self.e[i].0 == u { f(self.e[i].1); i += 1; }
    }
}

/// (c) CSR: targets of node u are tgt[off[u]..off[u+1]].
struct Csr { off: Vec<u32>, tgt: Vec<u32> }
impl Adj for Csr {
    fn build(n: usize, edges: &[(u32, u32)]) -> Self {
        let mut off = vec![0u32; n + 1];
        for &(s, _) in edges { off[s as usize + 1] += 1; }
        for i in 0..n { off[i + 1] += off[i]; }
        let (mut at, mut tgt) = (off.clone(), vec![0; edges.len()]);
        for &(s, d) in edges { tgt[at[s as usize] as usize] = d; at[s as usize] += 1; }
        Csr { off, tgt }
    }
    fn each<F: FnMut(u32)>(&self, u: u32, mut f: F) {
        for &d in &self.tgt[self.off[u as usize] as usize..self.off[u as usize + 1] as usize] { f(d); }
    }
}

fn one<G: Adj>(g: &G, u: u32) -> Vec<u32> { let mut v = vec![]; g.each(u, |d| v.push(d)); v.sort_unstable(); v }
fn two<G: Adj>(g: &G, u: u32) -> Vec<u32> { // friends-of-friends candidates
    let mut v = vec![]; g.each(u, |a| g.each(a, |b| v.push(b))); v.sort_unstable(); v.dedup(); v
}

struct Rng(u64);
impl Rng { fn next(&mut self) -> u64 { self.0 ^= self.0 << 13; self.0 ^= self.0 >> 7; self.0 ^= self.0 << 17; self.0 } }

fn run<G: Adj>(name: &str, n: usize, edges: &[(u32, u32)], rev: &[(u32, u32)], qs: &[u32]) -> (Vec<Vec<u32>>, Vec<u32>) {
    let (fwd, bwd) = (G::build(n, edges), G::build(n, rev));
    let (mut sink, t) = (0u64, Instant::now());
    for &q in qs { fwd.each(q, |d| sink += d as u64); }
    let h1 = t.elapsed().as_nanos() as f64 / qs.len() as f64;
    let t = Instant::now();
    for &q in &qs[..qs.len() / 10] { fwd.each(q, |a| fwd.each(a, |b| sink += b as u64)); }
    let h2 = t.elapsed().as_nanos() as f64 / (qs.len() / 10) as f64;
    let (mut hub, mut cnt, t) = (0u64, 0u64, Instant::now());
    for _ in 0..20 { bwd.each(0, |d| { hub += d as u64; cnt += 1; }); } // followers of node 0, the celebrity
    let h3 = t.elapsed().as_nanos() as f64 / cnt as f64;
    black_box((sink, hub));
    let hubcol = if cnt / 20 > 1000 { format!("followers(0): {} edges, {h3:.1} ns/edge", cnt / 20) } else { String::new() };
    println!("{name:7} following {h1:5.0} ns  2-hop {h2:6.0} ns  {hubcol}");
    let outs = qs[..500].iter().map(|&u| two(&fwd, u)).collect();
    (outs, one(&bwd, 0))
}

fn main() {
    let (n, m) = (1_000_000usize, 8_000_000usize);
    for skew in [false, true] {
        let mut r = Rng(0x9E3779B97F4A7C15);
        let edges: Vec<(u32, u32)> = (0..m).map(|_| {
            let s = (r.next() % n as u64) as u32;
            let u = (r.next() >> 11) as f64 / (1u64 << 53) as f64;
            let d = if skew { (u * u * u * n as f64) as u32 } else { (u * n as f64) as u32 }; // skew: few hubs get most follows
            (s, d)
        }).collect();
        let rev: Vec<_> = edges.iter().map(|&(s, d)| (d, s)).collect();
        let qs: Vec<u32> = (0..200_000).map(|_| (r.next() % n as u64) as u32).collect();
        println!("-- {} (n={n}, m={m})", if skew { "skewed destinations" } else { "uniform" });
        let a = run::<Linked>("linked", n, &edges, &rev, &qs);
        let b = run::<Table>("table", n, &edges, &rev, &qs);
        let c = run::<Csr>("csr", n, &edges, &rev, &qs);
        assert!(a == b && b == c, "layouts disagree"); // 2-hop sets and followers(0) identical
    }
}

Measured on this Mac (Apple M4 Pro), release build, three runs, 200,000 random sources:

Caveat: the table is a flat array (about 23 probes), not a B+ tree; a real tree would beat this stand-in. CSR gains from independent queries overlapping their cache misses; a chain cannot.

Complexity and constants

• Following-list: linked O(deg) loads, each a likely miss (records sit in insert order, not node order); table O(log m + deg), deg part sequential; CSR two loads, then sequential.
• Memory per direction, from the code: linked 4 B/node + 8 B/edge, table 8 B/edge, CSR 4 B/node + 4 B/edge: 68, 64 and 36 MB for 1M nodes and 8M edges.
• Edge test (a, b): chain and CSR scan deg(a); table O(log m); CSR with sorted rows O(log deg). Mutuals need sorted lists; chains are newest-first, so sort first.
• Dominant cost: the dependent random read; prefetch cannot help a chain.

Efficiency

• Cost: measured on this Mac (Apple M4 Pro), in RAM: 1-hop about 17 ns (CSR) vs about 300 ns (chain or binary search); 2-hop about 0.2 µs vs 2-4 µs. Bound: memory latency for chains, bandwidth for scans. On disk each pointer may be a page read; not measured here.
• Levers:
  • CSR for the read-mostly part — about 17x on 1-hop (measured) — updates arrive in batches.
  • Rewrite edge records in node order — chain becomes a sequential run (not measured) — rare rewrites.
  • Page and cap long lists — TAO caps a query at typically 6,000 edges (Bronson 2013) — supernodes.
  • Test membership from the shorter side — TAO picks the direction by assoc count (same paper) — one endpoint high-degree.
  • Cache hot lists — TAO overall read hit rate 96.4% (same paper) — reads dominate.
• Naive → standard → state of the art:
  • Scan the edge table per query · O(m)
  • Indexed edge table(s) on src and on dst · O(log m + deg), a few page touches
  • CSR plus a small delta for new edges, or sharded (id, type) lists behind a cache (TAO) · 17 ns in memory (measured); a cache hit per list at scale

Implementation notes

• u32 ids and a sentinel; node and edge arrays separate.
• Delete: free-list of edge ids; unlinking needs the previous pointer (the singly linked code above would rescan the chain).
• Chains are newest first: "recent follows" comes free, other orders do not.
• Write both directions in one transaction or by one writer.
• In SQL: PRIMARY KEY (src, dst) plus an index on (dst, src); hops become index-only scans.

Pitfalls

• Sharding: a reference cannot point to another machine. TAO stores an edge on the shard of id1 and its inverse on the other endpoint's shard; the two writes can cross shards and the inverse may be briefly missing.
• Supernodes: a celebrity's followers is one chain of scattered reads (55-80 ns/edge measured vs under 1). Page and cap it; skip it in 2-hop suggestions.
• Fragmentation: deletes leave holes; without compaction chain order drifts from memory order.
• Mixed types in one chain slow "followers only"; keep lists per (node, type, direction).

Variants and alternatives

Follow graph (following, followers-of, mutuals, 2-hop suggestions): start with edges(src, dst) and an index on (dst, src) in one database; when it outgrows one machine, move to per-user lists keyed (user, direction) behind a cache, sharded by user, capping list length and skipping celebrity accounts in suggestions. Pointer-chained records only pay off on one machine that also needs other graph queries.

In production

• Neo4j: chained relationship records; its block format keeps dense nodes in a B+ tree sorted by type and direction (Operations Manual).
• Facebook TAO: sharded association lists over MySQL plus a cache; 99.8% of requests are reads in the published workload.
• petgraph (Graph adjacency list, Csr) for in-process graphs.

Implementations

Sources

• Bronson et al., TAO: Facebook's Distributed Data Store for the Social Graph, USENIX ATC 2013 (§3.4 association lists, §4.1 sharding, §5.2 MySQL mapping, §5.4 high-degree objects). paper
• Neo4j source, NodeRecordFormat, RelationshipRecordFormat, RelationshipRecord (5.0 branch). code
• Neo4j Operations Manual, store formats. docs
• petgraph documentation, petgraph::csr::Csr. docs