You still need an index to start — index-free adjacency covers EXPAND, not SEEK

Every query is two phases — SEEK the anchor once with an ordinary index (O(log N)), then EXPAND with index-free adjacency (O(1) per edge) — so 'index-free' never meant 'no indexes', and a MATCH on an unindexed property silently degrades the SEEK into a full scan of every node of that label.

Previously

The doubly-linked chain lets us EXPAND from a node we hold — but we still had to find Alice. That first step, the SEEK, needs an ordinary index; index-free adjacency never covered it. Pull that index out and watch the start node turn into a full scan. So the store has TWO jobs with two cost models — and that raises a deeper storage question we've dodged.

Scene 05

You still need an index to start

Watch
Try it
Predict
Capture

What to watch for

Last scene we walked a node's relationship chain — but we ASSUMED we were already standing on Alice. How did we get there? Watch the two phases. First the SEEK: a plain B-tree index on User.name lights up and jumps straight to Alice (the ringed node) — one O(log N) lookup, the same kind of index a relational store uses. Only now do we hold a node. Second the EXPAND: from Alice we follow relationship pointers — the index-free O(1) walk — hop by hop to her friends and their friends. Two phases, two completely different cost models.

The same social graph.
A query runs in two phases.
First the SEEK: an ordinary B-tree index on User.name is consulted to find the anchor — the node the query starts from, Alice (ringed).
Then the EXPAND: from Alice the engine follows relationship pointers — the index-free O(1)-per-hop walk from earlier scenes — lighting only the few nodes it reaches.
The toggle removes the index: with no index the SEEK can't jump to Alice, so it falls back to a full label scan that lights EVERY :User node before EXPAND can even begin.
The inset keeps the spine: SEEK lights one anchor, EXPAND a few.

Implementation

Highlighted lines are the ones running in the diagram right now.

Query.run

every query is two phases — SEEK the anchor, then EXPAND from it

1def run(label, prop, value, depth):
2    # phase 1: SEEK — find the start node by value (once)
3    anchor = seek_anchor(label, prop, value)
4    # phase 2: EXPAND — index-free pointer walk from it
5    return expand(anchor, depth)

Query.seek_anchor

find the start node by value — indexed, or a full label scan

1def seek_anchor(label, prop, value):
2    idx = index_for(label, prop)
3    if idx is not None:
4        return idx.lookup(value)      # O(log N) once
5    # no index → full label scan
6    for node in all_nodes_with(label):  # O(N) every query
7        if node[prop] == value:
8            return node

Index.create

what the toggle does: register a B-tree so seek_anchor can look up, not scan

1def create_index(label, prop):
2    btree = BTree()
3    for node in all_nodes_with(label):  # one-time build
4        btree.insert(node[prop], node)
5    catalog[(label, prop)] = btree    # now index_for() finds it
6    return btree

Query.expand

from the anchor, follow relationship pointers (index-free)

1def expand(anchor, depth):
2    frontier = [anchor]
3    for _ in range(depth):
4        nxt = []
5        for node in frontier:
6            rel = node.first_rel       # pointer, not an index
7            while rel is not None:     # O(1) per edge
8                nxt.append(rel.end_node)
9                rel = rel.next_rel
10        frontier = nxt
11    return frontier

Sources

Where this sits in Build a graph database (Neo4j / Dgraph-style)

Scene 05 of 16, in the The store act — Store records, index-free adjacency, the CSR trade.. Index-free adjacency only covers EXPAND (traversing from a node you hold); to SEEK the anchor — 'start from Alice' — you still need a regular index, and without one finding the start node is a full label scan over every :User.

Up next. We've been drawing the relationship chain as a doubly-linked list because it's easy to insert and delete. But pointer-chasing across the heap is cache-hostile, and there's a rival layout — a packed array — that streams through memory beautifully but can't cheaply add an edge. Which one you pick depends entirely on whether your graph mutates or just gets read.

All 16 scenes in Build a graph database (Neo4j / Dgraph-style) · Every curriculum

Built with Arqly

Every scene in Build a graph database (Neo4j / Dgraph-style) builds on the one before it.All 16 Build a graph database (Neo4j / Dgraph-style) scenes