What index-free adjacency means
Recall the promise from Chapter 0: a hop should be a pointer-follow, not a lookup. Here is how. Each node holds direct references to its relationships, so "give me Keanu's outgoing relationships" is reading an array — not scanning a table, not probing a B-tree. The marketing name is native graph storage; the data structure is just two adjacency lists per node.
Three ways to answer "what are this node's relationships?":
- Scan all relationships and filter by endpoint — O(E) every query. Terrible.
- B-tree index on
startNode— O(log E) per hop. This is roughly what a relational database does. - Index-free adjacency — precompute, per node, the list of its relationship ids. A hop is O(1) array access plus O(degree) to walk it. The graph database pays the build cost once at load, not on every query.
The phrase to internalize: the relationship is the index. There is no separate global node→relationship index; adjacency is baked into the structure.
outgoing[Keanu.id] = [rel#? (ACTED_IN→Matrix), rel#? (ACTED_IN→Reloaded), ...]
incoming[Matrix.id] = [rel#? (←Keanu), rel#? (←Carrie), rel#? (←Laurence), ...]
neighbors(Keanu, 'ACTED_IN', OUT)
= walk outgoing[Keanu.id], filter type, map to the OTHER endpoint
-> [Matrix, Reloaded, ...]
This is the single idea Neo4j is built on, and you are about to build it in a dozen lines. Outgoing relationships where this node is the startNode; incoming where it is the endNode. One pass over the relationship list at load time wires up the whole thing.