Store records and the relationship chain

Build a graph database (Neo4j / Dgraph-style) (16 scenes)

Scene 04 · Store records and the relationship chain

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.

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

Diagram

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.

Sources

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.

Implementation

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

Not sure what to ask? Tap a question — the staff engineer answers in the chat panel.

PreviousIndex-free adjacency: follow pointers NextYou still need an index to start