Neo4j
A property-graph database with index-free adjacency and Cypher traversals.
Neo4j stores data as nodes connected by typed, directed relationships, each carrying properties. Fixed-size record files keep node and relationship records side by side, so traversing from one node to its neighbors is a pointer chase, not an index lookup — Neo4j calls this index-free adjacency. Cypher expresses queries as graph patterns the engine walks.
Property graph model
Nodes and relationships both carry arbitrary properties. Relationships are typed, directed, and stored as first-class records — not foreign keys resolved through an index.
Record store files
The store directory keeps fixed-size records (neostore): nodes, relationships, properties, each in its own file. A relationship record physically links the IDs of its two nodes plus the previous/next relationship of each.
Cypher traversals
MATCH (a:Person)-[:KNOWS*1..3]->(b) declares a pattern; the runtime expands frontiers over the record-linked graph, honoring direction and hop limits from the pattern.
Indexes where they belong
Starting points come from B-tree range indexes or Lucene full-text indexes; everything after the first hop uses adjacency pointers. Joins as repeated index lookups are what graph databases are built to avoid.
The logical model: a property graph
Relational models normalize entities into tables and connect them with foreign keys resolved at query time. A property graph stores the connection itself: an order KNOWS-product relationship is a physical record between two nodes, readable in one hop, with its own properties (quantity, since).
Recursive and variable-depth questions — friend-of-friend, dependency chains, shortest route — change cost class completely: SQL needs recursive CTEs with per-iteration joins; a traversal follows existing pointers.
// Cypher: colleagues-of-colleagues who like the same product
MATCH (me:Person {id: 1})-[:KNOWS*1..2]-(other:Person),
(other)-[:LIKED]->(p:Product)<-[:LIKED]-(me)
RETURN other, count(p) AS shared ORDER BY shared DESC LIMIT 5
The physical model: index-free adjacency
Each node record carries the address of its first relationship; each relationship record carries the addresses of the next/previous relationship for both of its endpoints. Traversing from a node to its neighbors is following these record pointers — no index is consulted per hop. That is what "index-free adjacency" means in Neo4j’s documentation, and it is why traversal cost tracks the size of the result frontier, not the size of the graph.
B-tree indexes still exist — for finding starting nodes by property value. The walkthrough below shows the traversal itself: a breadth-first expansion with a FIFO frontier, where direction comes from the pattern and the visited set guarantees termination on cyclic graphs.
Writes and durability
Writes go to a logical log before the record files are updated; recovery replays the log. Concurrent transactions lock the records they touch (write conflicts) while readers work on snapshots — document-level isolation vocabulary does not map cleanly here, and Neo4j’s manual describes its exact read-committed semantics per version.
Diagrams
[caption] One index lookup at the start; every later hop follows stored pointers.
A pattern query starts from indexed anchor nodes, then expands across relationship records via adjacency pointers until the pattern is satisfied.
| nodes visited | 6/6 |
| edges examined | 7/7 |
| shortest path to F | A→B→D→F (3 hops) |
| terminates on cycles | visited-set check — each node enqueued once |
All steps
- Start at A — The traversal begins at A. Frontier = {A}, visited = {A}. Direction matters: only outgoing relationships (FOLLOWS →) are walkable.
- Depth 1: expand {A} — FIFO order: each frontier node's outgoing edges are examined; newly discovered nodes join the next frontier. Examined 2 edges this layer, skipped 0 to already-visited nodes — a node is enqueued once, which is what makes BFS terminate on cyclic graphs.
- Depth 2: expand {B, C} — FIFO order: each frontier node's outgoing edges are examined; newly discovered nodes join the next frontier. Examined 3 edges this layer, skipped 1 to already-visited nodes — a node is enqueued once, which is what makes BFS terminate on cyclic graphs.
- Depth 3: expand {D, E} — FIFO order: each frontier node's outgoing edges are examined; newly discovered nodes join the next frontier. Examined 2 edges this layer, skipped 1 to already-visited nodes — a node is enqueued once, which is what makes BFS terminate on cyclic graphs.
Breadth-first traversal from A with directed edges and a FIFO frontier. Teaching model: generic BFS over 6 nodes; the Neo4j exhibit maps it to Cypher variable-length MATCH, where relationship direction and traversal limits are part of the query.
Generic BFS on a 6-node toy graph; Neo4j’s runtime adds its own expansion strategies and path evaluators on top of the same principles.
[caption] Generic BFS on a 6-node toy graph; Neo4j’s runtime adds its own expansion strategies and path evaluators on top of the same principles.
Expand a FIFO frontier from node A across directed relationships: direction per hop, visited-set termination, and the shortest-path property of BFS — the mechanics under Cypher variable-length patterns.