Build a graph database (Neo4j / Dgraph-style) (16 scenes)
Scene 03 · Index-free adjacency: follow pointers
Each node stores a direct pointer to its relationships, so following an edge is a pointer dereference — O(1) per hop, independent of total graph size — not a B-tree seek that gets slower as the database grows.
Previously
A first-class relationship is only useful if I can reach it without a lookup. Here's how: every node stores a direct pointer to its relationships, so a hop is a pointer dereference, not an index seek — that's index-free adjacency, the reason this whole category of database exists. But 'a pointer to its relationships' is vague. What does that record actually look like in memory?
Scene 03
Index-free adjacency: follow pointers
Diagram
The same social graph, but watch ONE hop in slow motion: Alice → Bob. It happens in three pointer follows — node.firstRel (Alice's record points to her first relationship), → rel (the relationship record, a precomputed join baked into the store), → rel.endNode (the relationship points straight at Bob). Each arrow is a pointer dereference: reading a memory address that's already written down, not searching for it. Following stored pointers like this — never consulting an index during the walk — is index-free adjacency: 'follow pointers, don't join tables.' The faint B-tree on the side is what a relational store does instead on every hop — a seek whose depth grows as the table grows. The inset shows the spine: a local hop lights up just the few nodes it touches.
Forget the whole graph for a moment. Watch a single hop, Alice → Bob, happen in slow motion. Alice's node record holds the address of her first relationship. We follow that pointer to the relationship record — a join already computed and stored. The relationship record holds the address of its end node. We follow that to Bob. Three reads of addresses that were already written down. No index was searched. The faint structure on the side is what a relational store does on the very same hop: descend a B-tree to find the matching row.
Implementation
Graph.expandOneHop
follow pointers — no index consulted
1def expand_one_hop(node):2 # follow 1: node record stores the address of its first rel3 rel = deref(node.firstRel) # land ON the rel record4 # follow 2: read the rel record (a precomputed join, baked in)5 end_addr = rel.endNode # the address it points at6 # follow 3: dereference that to land ON the neighbor node7 neighbor = deref(end_addr) # 3 follows total, no index8 return neighbor # O(1), independent of N
Relational.expandOneHop
seek an index for the matching row — O(log N) per edge
1def expand_one_hop(user_id):2 # no stored pointer — search the index for the join row3 rows = btree_seek(USER_FRIEND, key=user_id)4 # seek descends ceil(log_fanout(N)) levels — grows with the table5 neighbors = [r.friend_id for r in rows]6 return neighbors # O(log N), grows with size
Graph.kHopTraversal
k hops = k pointer chases — cost tracks the answer, not N
1def k_hop(start, k=5):2 frontier = {start}3 for _ in range(k): # one level per hop4 next = set()5 for node in frontier:6 # each expand is the 3-follow O(1) hop, no index7 next |= expand_one_hop(node)8 frontier = next9 return frontier # cost ~ nodes reached, not N
Relational.kHopTraversal
k hops = k index seeks, each O(log N) — pays the depth k×
1def k_hop(start_id, k=5):2 frontier = {start_id}3 for _ in range(k): # one self-join per hop4 next = set()5 for uid in frontier:6 # no stored pointer — seek the join index each time7 next |= btree_seek(USER_FRIEND, key=uid)8 frontier = next9 return frontier # k x O(log N) — grows as the table grows
Not sure what to ask? Tap a question — the staff engineer answers in the chat panel.