Store records and the relationship chain

A node record holds a pointer to its first relationship, and each relationship record is a node in a doubly-linked list for both of its endpoints with back-pointers to its start and end nodes — so 'a node's edges' is literally a walkable chain, and fixed-size records turn record-id into a byte offset with no index needed.

Previously

Index-free adjacency promised O(1) hops; now we've seen the machinery — fixed-size records addressed by offset, and a doubly-linked chain of relationships hanging off each node. Walking and mutating that chain is cheap. But there's a hidden assumption: that we already KNOW which node to stand on. How did we find Alice in the first place?

Scene 04

Store records and the relationship chain

Watch
Try it
Predict
Capture

What to watch for

Last scene we said 'the node points to its relationships.' Here's what that actually IS in storage. Alice's node record is one fixed-width box; inside it, a firstRel pointer aims at a relationship record. Follow the path: read firstRel, land on record 100, then follow that record's endNode back-pointer to Bob. That's ONE hop — three pointer follows, no index touched. The relationship records to the right are joined by prev/next links: a chain you can walk.

Alice's NODE RECORD (a fixed-width box, ~15 B) holds a firstRel pointer into a DOUBLY-LINKED RELATIONSHIP CHAIN — a row of fixed-width relationship records (~34 B each) joined by prev/next links, each carrying start/end node back-pointers. Two ideas live here.
STORE RECORD (FIXED-SIZE): because every record is the same width, record-id × size = its byte offset, so the engine jumps straight to a record with no index.
DOUBLY-LINKED RELATIONSHIP CHAIN: a node's edges are a list you can walk forward (next) and backward (prev), and insert into or delete from in place.
The animated path walks one hop as node.firstRel → rel → rel.endNode — three pointer follows.

Implementation

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

RelStore.fetch

find a record by id — pure arithmetic, no index

1def fetch(record_id):
2    # every relationship record is REL_SIZE bytes wide
3    offset = record_id * REL_SIZE   # id IS the address
4    return store_file.read_at(offset, REL_SIZE)

RelStore.one_hop

one hop = three pointer follows: firstRel → rel → endNode

1def one_hop(node):
2    rid = node.first_rel        # 1) read the firstRel pointer
3    rel = fetch(rid)            # 2) land on the relationship record
4    other = rel.end_node        # 3) follow the back-pointer
5    return other                #    no index touched on any step

RelChain.prepend

add an edge as the new head — splice two links, O(1)

1def prepend(node, new_rel):
2    old_head = node.first_rel
3    new_rel.next = old_head
4    new_rel.prev = None
5    if old_head: old_head.prev = new_rel
6    node.first_rel = new_rel   # re-point the node record

Sources

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

Scene 04 of 16, in the The store act — Store records, index-free adjacency, the CSR trade.. Fixed-size store records (node ~15 B, relationship ~34 B) mean record-id × size = byte offset with no index, and each relationship sits in a doubly-linked list for BOTH its endpoints — so a node's edges are a chain you can walk, insert into, and delete from in place.

Up next. Everything so far assumed we were already standing on Alice. But 'start from the user named Alice' is a lookup by VALUE, and pointer-chasing can't do that — it can only follow edges from a node you already hold. So the very first step of every query needs something index-free adjacency explicitly does NOT provide.

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