Native adjacency storage and index-free adjacency

Note: Company names, engineers, incidents, numbers, and scaling scenarios in this article are hypothetical — even when they resemble real ones. See the full disclaimer.

A four-hop fraud-ring query over an Indian payments graph takes about a second on Postgres and about ten milliseconds on Neo4j — same data, same query, two orders of magnitude apart. The gap is not query optimisation or hardware; it is one architectural choice about where edges live on disk. This chapter unpacks that choice — index-free adjacency — by building the storage layout from scratch and showing exactly where the 100× per-hop speedup comes from.

The thesis: a graph is just two tables, until you traverse it

The relational answer to "store me a graph" is so natural it barely deserves discussion. Two tables:

CREATE TABLE nodes (
  id          BIGINT PRIMARY KEY,
  label       TEXT NOT NULL,
  properties  JSONB
);

CREATE TABLE edges (
  src_id      BIGINT NOT NULL REFERENCES nodes(id),
  dst_id      BIGINT NOT NULL REFERENCES nodes(id),
  type        TEXT NOT NULL,
  properties  JSONB,
  PRIMARY KEY (src_id, dst_id, type)
);
CREATE INDEX edges_dst_idx ON edges (dst_id);   -- for reverse traversal

This is the schema every social network started with — Sociogram ran on it for years, ProfNet ran on it, every Indian payments network running on Postgres or MySQL today still runs on a variant of it. The schema is honest, the constraints are checked, the JSONB column lets you stuff arbitrary properties without an ALTER TABLE. Reads against single nodes are cheap. Aggregations across nodes are cheap. The whole machinery of relational query optimisation is at your disposal.

The query "give me the neighbours of node 42" looks like this:

SELECT n.* FROM nodes n
JOIN edges e ON e.dst_id = n.id
WHERE e.src_id = 42;

The Postgres planner descends the primary-key B-tree on edges to find the leaf page where (42, *) lives, scans the matching tuples, then for each dst_id does a primary-key lookup on nodes to fetch the row. Why this costs ~100 µs: a B-tree of, say, a billion edges is roughly 4 levels deep — three internal pages and one leaf. Each page touch is a buffer-pool lookup (cheap, but not free), plus a binary search within the page (a few hundred nanoseconds). The leaf scan reads a handful of consecutive tuples. Then for each neighbour, another B-tree descent on nodes. Add in latch acquisition, MVCC visibility checks, and the cost of returning rows through the executor, and you are at roughly 100 µs per hop on a warm cache. On a cold cache (an SSD page read), make that 200 µs.

So one hop is 100 µs. Two hops is 100 µs × fan-out. Three hops is 100 µs × fan-out². Four hops in a graph where the average node has ten neighbours is 100 µs × 10³ = 100,000 µs = 100 ms — and that ignores the cost of de-duplicating nodes you have already seen.

Native adjacency: the node knows where its edges live

The native-graph answer rejects the framing. Instead of two heap files plus an index that maps node IDs to edge rows, store the adjacency information inside the node record itself. Specifically, every node record on disk holds a single field: a file offset pointing to the first edge in its adjacency list. Every edge record holds pointers to: its source node, its destination node, the next edge in the sources adjacency list, and the *next* edge in the destinations adjacency list. The result is a doubly linked list of edges threaded through each node — every edge is a member of two such lists, one per endpoint.

This is the layout Neo4j has shipped since version 1.0. The on-disk files are named after their contents: neostore.nodestore.db holds fixed-size node records (15 bytes each in older versions, larger now), neostore.relationshipstore.db holds fixed-size relationship records (34 bytes each), and neostore.propertystore.db holds the variable-length property lists that hang off both. Because every record is fixed-size, the file offset of node n is just n × record_size — there is no need for an index from node ID to file location. Why fixed-size matters: the moment record sizes are variable, you need an index to find a record by ID, and you have just reintroduced the very B-tree probe you were trying to eliminate. Fixed-size records make ID-to-offset translation a multiplication, which the CPU does in a single cycle.

Walking from a node to a neighbour now looks like this. Read the node record at offset id × 15. Take its first-relationship pointer. Read the relationship record at that offset. The relationship record contains both endpoint IDs and pointers to the next relationship in each endpoint`s list. Follow the destination pointer (multiply by node record size, read) to land on the neighbour. No index lookups. Just two file-offset multiplications and two page reads. On a warm buffer cache, both pages are already in RAM, and a hop costs roughly 1 µs — dominated by the cost of the pointer dereference and the L2-cache miss on the page.

The speedup: 100× per hop, compounded

Put the two together and the gap is stark. A single hop in Postgres is roughly 100 µs; the same hop in Neo4j is roughly 1 µs. A factor of one hundred per hop. Multi-hop queries do not just inherit this speedup — they amplify it, because the relational query has to re-pay the index cost at every hop, while the native query continues pointer-chasing at the same rate.

Index-free adjacency, in code

The pseudo-code makes it concrete. Here is what one hop looks like in each world.

# Relational: every hop is an indexed lookup
def neighbours_postgres(conn, node_id):
    cur = conn.cursor()
    # Postgres planner: index seek on edges_pk_idx, then NL-join into nodes
    cur.execute("""
        SELECT n.id, n.label, n.properties
        FROM   nodes n
        JOIN   edges e ON e.dst_id = n.id
        WHERE  e.src_id = %s
    """, (node_id,))
    return cur.fetchall()       # ~100 µs warm, ~200 µs cold


# Native: every hop is a pointer chase
NODE_REC_SIZE = 15              # bytes (illustrative)
REL_REC_SIZE  = 34

def neighbours_neo4j(store, node_id):
    # Compute file offset directly; no index lookup
    node_off = node_id * NODE_REC_SIZE
    node = store.read_node(node_off)        # one page read

    neighbours = []
    rel_off = node.first_rel                # the pointer that lives in the node record
    while rel_off is not None:
        rel = store.read_rel(rel_off)       # one page read per edge
        # Decide which end of the edge is "us" so we walk the correct linked list
        if rel.src == node_id:
            other_id = rel.dst
            rel_off  = rel.next_src_edge
        else:
            other_id = rel.src
            rel_off  = rel.next_dst_edge
        neighbours.append(other_id)
    return neighbours                       # ~1 µs/edge warm

Notice the symmetry. The relational version asks the database "find me the rows where src_id = X", and the database descends a B-tree to answer. The native version already knows where the first edge lives — its file offset is a field in the node record — and walks a linked list from there. The same primitive (read_rel(offset)) handles every subsequent edge. Why this changes asymptotic feel: in the relational query, traversal cost is O(hops × log N) because each hop is a log N B-tree descent. In the native query, traversal cost is O(hops × degree) — proportional to the edges actually walked, not to the size of the database. Whether you have a thousand nodes or a billion, the per-edge cost is the same.

Trade-offs: writes, supernodes, and tabular queries

Native adjacency is not free. Three costs show up in production.

Write amplification. Inserting an edge in the relational schema is a single INSERT INTO edges plus an index-update — two B-tree pages dirtied. Inserting an edge in Neo4j requires (1) allocating a new relationship record, (2) updating the source nodes adjacency list (find the previous "first" edge, point it back to the new one, point the node to the new one), and (3) updating the destination nodes adjacency list the same way. Three records dirtied, with a strong locality penalty if the source and destination live on different pages — and they almost always do, because nodes are clustered by ID, not by neighbour. Why this matters at scale: a payments graph that ingests a million transactions per second pays this overhead a million times. Neo4j Enterprise added group-commit and parallel transaction logging to amortise the cost, and TigerGraph added a write-back cache layer on top of the same idea — but the fundamental write cost is higher than relational, and that is the price of read speed.

Supernodes. The doubly-linked-list-of-edges layout is fine when nodes have a few hundred edges. It becomes a concurrency disaster when one node has five million edges — the canonical Bollywood-actor-with-five-million-followers problem. Adding an edge to that nodes adjacency list means traversing or splicing into a linked list of five million entries, with locks held the whole time. Neo4j 3.0 introduced **dense-node optimisations** that switch supernodes from a single linked list to a per-relationship-type list (so traversal can skip irrelevant types) and eventually to a small per-type B-tree-like structure. JanusGraph mitigates differently by sharding each nodes edge list across the underlying Cassandra/HBase store so that the linked-list traversal is parallel. Either way, supernodes are the place where index-free adjacency`s simplifying assumption — that a degree-N adjacency is a single linked list — breaks, and engineering complexity creeps back in.

Tabular queries. "What is the average age of all our users?" is a one-line SQL query that scans the users table sequentially, and Postgres will do it in a few hundred milliseconds for ten million rows. The same query in Neo4j has to scan every node record, decode every property list (which lives in a separate file), filter by label, and aggregate — and the property list is variable-length, so there is no nice row-store SIMD. Native graph databases have steadily added secondary indexes (Neo4js schema indexes, JanusGraphs composite indexes) to accelerate label-and-property scans, but the sweet spot is genuinely traversal. If your workload is 90 % aggregations and 10 % traversals, you want Postgres. If it is 90 % traversals and 10 % aggregations, you want Neo4j. The interesting world is everywhere in between, which is why production graph stacks usually keep both — Postgres for the system of record, Neo4j or TigerGraph for the traversal index — and CDC-replicate from one to the other.

The native landscape

Four systems matter today, each occupying a slightly different point in the design space.

Neo4j is the canonical implementation — it shipped index-free adjacency in 2010, popularised the term, and remains the most widely deployed native graph database. Storage is on disk, with a buffer pool (page cache) sized like Postgres`s; the engine, query language (Cypher), and operational tooling are mature. The ecosystem includes hot-failover, role-based clustering, and a graph data science library. If you are starting a graph project today and have no other constraints, this is the default.

JanusGraph decouples the graph layer from the storage backend: you can run JanusGraph on top of Cassandra, HBase, BerkeleyDB, or ScyllaDB. The native-adjacency story holds when JanusGraph is configured with BerkeleyDB (single-node, fixed-size records); on Cassandra, the adjacency is "logical" — each nodes edge list is one Cassandra row, with edges stored as columns, and traversal is a Cassandra read rather than a pointer chase. This loses some single-hop latency but inherits Cassandras horizontal scalability, which is the trade Chirpline and others made for their early graph workloads.

TigerGraph is the speed extremist. It compresses node and edge records aggressively, runs traversal in massively parallel C++ kernels, and consistently benchmarks an order of magnitude faster than Neo4j on multi-hop queries. The catch is a more proprietary stack and a steeper learning curve for its query language (GSQL). It is the choice when you have a very large graph (tens of billions of edges) and need traversal latency at single-digit milliseconds.

Memgraph keeps the entire graph in RAM and uses a skiplist-of-records layout instead of a fixed-record file. The pointer-chase becomes a memory-pointer dereference (no buffer-pool indirection at all), pushing per-hop cost into the nanosecond range. Crash recovery uses a write-ahead log replayed on startup. The trade-off is RAM cost: a graph that fits comfortably on a 1 TB SSD might need a 256 GB RAM machine. For real-time recommendation engines and trading-graph analytics, the cost is justified.

WITH RECURSIVE ring AS (
  SELECT 42 AS node_id, 0 AS depth
  UNION ALL
  SELECT e.dst_id, r.depth + 1
  FROM   ring r JOIN edges e ON e.src_id = r.node_id
  WHERE  r.depth < 3
)
SELECT DISTINCT node_id FROM ring;

MATCH (asha {id: 42})-[*1..3]->(neighbour)
RETURN DISTINCT neighbour

Common confusions

• "Neo4j has no indexes at all." Wrong on two counts. Neo4j has no index for adjacency lookup — that is what "index-free adjacency" means. But Neo4j absolutely does have schema indexes on labels and properties, and you very much want them when you need to find a starting node by something other than its internal ID. The query MATCH (u:User {phone: '+91-9876543210'}) does an index seek into a B-tree-like structure to find Asha`s node, and then the pointer-chase begins. Index-free adjacency replaces the per-hop lookup, not the seed lookup.

• "Index-free adjacency means O(1) traversal." It means O(1) per edge, not per query. Walking a nodes 12 neighbours is 12 pointer chases — 12 µs warm. Walking a Bollywood actors 5 million followers is 5 million pointer chases — 5 seconds, no matter how clever the storage engine is. The big-O of a traversal is O(edges visited), not O(1). The win over relational is the constant factor (no log N B-tree probe per hop) and the asymptotic feel that the cost is independent of database size, not of degree.

• **"You cant do graph queries on Postgres, you need Neo4j."** You can — recursive CTEs in Postgres, MySQL 8+, and SQL Server have been doing graph traversal since 1999. For shallow traversals (1–2 hops) on a well-indexed edges table, Postgres often beats Neo4j on cold-cache queries because Postgress buffer pool and parallel workers are more mature. The relational design loses badly only on deep traversals (3+ hops with fan-out) where the per-hop B-tree probe compounds.

• "Native graph databases beat relational on writes too." They almost never do. Inserting an edge in Postgres is one INSERT plus one B-tree split (occasionally). Inserting an edge in Neo4j touches three records and two adjacency lists with the strong locality penalty that the source and destination usually live on far-apart pages. Bulk-loading a graph into Neo4j is roughly 2–5× slower than the same data into Postgres for exactly this reason — Neo4j ships a separate neo4j-admin import tool precisely to bypass the runtime adjacency-list maintenance during bulk loads.

• "Neo4j stores the property graph in JSON or BSON." No — Neo4j`s property store is a flat, fixed-block heap with property records that point to dynamic-array files for long strings and arrays. Properties are typed at the storage layer (boolean, int, double, string-pointer), not stored as a JSON blob. JanusGraph on Cassandra does effectively store properties as Cassandra columns, which is closer to a key-value layout than to JSON. The property-graph data model is a logical contract — the physical encoding varies dramatically across engines.

• "Memgraph is Neo4j on RAM." Memgraph is API-compatible with Neo4j (it speaks the Bolt protocol and Cypher), but its storage engine is fundamentally different — a skiplist of in-memory records with a write-ahead log for durability, not a fixed-record file mmaped from disk. The pointer-chase becomes a CPU-cache-friendly memory dereference, which is why Memgraph benchmarks deeper traversals at sub-microsecond per hop. The trade is RAM cost: a 1 TB graph needs a 1 TB+ RAM machine, while Neo4j with a smaller buffer pool just pages from SSD.

Going deeper

If you wanted the headline — "Neo4j stores adjacency as pointers, that is why traversal is fast" — you have it. The rest of this section is the engineering reality: how the on-disk layout actually looks, how dense-node optimisations work, what GC pauses look like in a JVM-based graph engine, and where the pointer model breaks down.

The exact Neo4j on-disk record layout

Neo4js neostore.relationshipstore.db is a heap of fixed-size records — 34 bytes each in versions 3.x–4.x, expanded slightly in 5.x to support longer reference IDs. The fields, in order, are: a 1-byte in-use flag, a 4-byte first-node ID, a 4-byte second-node ID, a 4-byte relationship-type ID, a 4-byte first-prev-rel pointer (the previous edge in the sources adjacency list), a 4-byte first-next-rel pointer (the next edge in the sources adjacency list), a 4-byte second-prev-rel pointer (previous in destinations list), a 4-byte second-next-rel pointer (next in destinations list), and a 4-byte first-property-record pointer. <span class="why">Why doubly linked rather than singly linked: deletion. Removing an edge from the middle of a singly linked list requires a forward scan from the head to find the predecessor — O(degree). With a doubly linked list, both neighbours are reachable from the deleted record in O(1), so deletion is constant-time. Neo4j explicitly chose the extra 4 bytes per record to make DELETE r` not pathological on supernodes.

A 4 + 4 = 8-byte ID gives Neo4j a 2^32 ≈ 4 billion record limit per store file in classic versions — which sounds like a lot until you realise Aadhaar has 1.4 billion records and the ProfNet graph has crossed 10 billion edges. Neo4j 5.x switched to 8-byte IDs ("id-reuse upgrade") to push this past the trillion-edge mark.

Dense-node optimisations: when the linked list breaks

The doubly-linked-list adjacency works beautifully for nodes with up to a few hundred edges. Above that threshold (Neo4j defaults to 50, configurable via dbms.relationship_grouping_threshold), Neo4j flips the node into dense-node mode: the nodes first_relpointer no longer points at a relationship record, but at a **relationship group record**. Each group record corresponds to one (relationship-type, direction) pair and points to the head of a linked list of relationships of that type and direction. <span class="why">Why this matters for query planning: when Cypher executesMATCH (a)-[:PAID]->(b), the planner walks the dense nodes relationship group records, finds the one for type=PAID and direction=outgoing, and starts walking only that list. On a Bollywood actor with 5 million FOLLOWS edges and 50 PAID edges, looking up the 50 PAID edges is now O(50), not O(5,000,050) — the FOLLOWS edges are skipped without touching them. The same node had been a serial-traversal nightmare in Neo4j 1.x.

TigerGraph takes a different path — it stores supernode adjacency as a sorted compressed array, parallelised across CPU cores, and routinely outperforms Neo4j on supernode queries by an order of magnitude. JanusGraph on Cassandra spreads supernode edges across multiple Cassandra rows (a "vertex-cut" partition) so traversal becomes parallel reads from multiple Cassandra replicas. Three different engineering responses to the same fundamental problem: pure linked-list adjacency does not survive the long tail of node degrees.

The page-cache story: pointer chase is not free if pages are cold

The 1 µs per hop number assumes a warm buffer cache. On a cold cache — the buffer pool is small, the graph is large, the access pattern is random — every pointer chase is a page fault that takes 50–200 µs on SSD or 5–10 ms on spinning rust. The compounding here is brutal: a 4-hop fan-out-10 traversal against a cold cache touches ~10,000 random pages, at 100 µs per page on SSD that is one full second — back to relational territory.

This is why Neo4js tuning manual obsesses about buffer pool size (dbms.memory.pagecache.size). The rule of thumb: budget enough RAM to hold the *adjacency* (node store + relationship store) entirely in cache. Properties can spill to disk because they are touched only when projected into results. For a 1-billion-edge graph that is 1 billion × 34 bytes = 34 GB of relationship store plus a few GB of node store — well within a single modern servers RAM budget. Below this threshold, native adjacency wins by 100×. Above it, the page-fault cost dominates and the gap closes to 5–10×.

What native adjacency can not optimise

Three workloads where index-free adjacency provides no advantage at all:

1. Single-record lookups by property. "Find the user with phone +91-9876543210." This is a B-tree probe in Postgres and a B-tree probe (against Neo4j`s schema index) in Neo4j. Roughly equal, with Postgres often slightly faster because its B-trees are battle-hardened.
2. Aggregations across all nodes of a label. "Count of all users." Postgres scans users sequentially in a row-store. Neo4j scans every node record in nodestore.db, filters by label, decodes the property block, and counts. Postgres wins by 3–5× on this kind of query for the same reason a column-store wins over a row-store on analytics: data layout for the workload matters.
3. Bulk insert of a non-graph dataset. "Load 100 million transactions into a table." Postgress COPY FROM does this in minutes; Neo4js LOAD CSV is 5–10× slower because of the per-record adjacency-list bookkeeping. The bulk-import tool (neo4j-admin database import) bypasses this by writing the store files directly, but you cannot use it on a running database.

The honest framing is that native graphs win on multi-hop traversal latency, period. Every other workload has at least one relational engine that does it as well or better. This is why production graph stacks — PaisaBridges, BharatBazaars, BhojanBox`s — almost never run a single graph database in isolation. Postgres or MySQL stays as the system of record; Neo4j or TigerGraph is fed via CDC (Debezium, Maxwell) and serves only the queries that exploit its strength.

Why Pregel rejected this entire design

Querions [Pregel](https://research.google/pubs/pregel-a-system-for-large-scale-graph-processing/) (the system that became Apache Giraph and inspired GraphX) takes a completely different stance: forget the on-disk pointer graph, partition the vertices across machines, and run computations as **vertex-centric supersteps** where each vertex sends messages to its neighbours and the system synchronises between rounds. This is the right answer when the graph is too big for any single machines RAM, the workload is whole-graph computation (PageRank, connected components, single-source shortest path on a billion-node graph), and you can tolerate batch latency. The Pregel model and the index-free-adjacency model are not competitors — they are answers to different questions. Pregel says "I will look at every edge once." Neo4j says "I will look at the edges of one node, then expand from there." For interactive queries, Neo4j wins. For whole-graph analytics, Pregel-style systems (or modern equivalents like TigerGraph`s GSQL accumulators) win.

Where this leads next

• Traversal primitives as query building blocks — the next chapter, which builds Cypher and Gremlin operators (out, in, both, step, path) on top of the pointer-chase primitive.
• Property graphs vs RDF — the data model this chapter`s storage layout encodes; the previous step in this build.
• B-tree insertion, split, and merge — the relational primitive that index-free adjacency is designed to escape.
• Free-space management and fragmentation — fixed-record stores age, free-list management is the price you pay for not having an index.
• Deadlock detection with wait-for graphs — a different use of the graph data model: the wait-for graph that every transaction manager maintains internally.

The takeaway

Index-free adjacency is one of those architectural decisions that sounds incremental — "store a pointer in the node record" — and turns out to be the entire reason a category of database exists. The relational schema with nodes and edges is correct, queryable, and extensible; it is also irrecoverably slow at multi-hop traversal because the only way to answer "what are the edges of node X" is to look them up. Native engines refuse the lookup. They store the answer where the question gets asked — inside the node record itself — and the cost per hop falls by two orders of magnitude. That falling cost compounds over hops, which is why fraud-ring detection, recommendation cascades, and citation-graph BFS have moved from batch to interactive in the decade since Neo4j shipped its pointer-chasing storage engine.

The trade-offs are real. Writes are heavier because every edge update touches both endpoints. Supernodes are concurrency hotspots that need dense-node optimisations or vertex-cuts to handle. Tabular aggregations run faster on Postgres because Postgres has a sequential row-store and the graph engine does not. Modern systems mitigate all three — dense-node groups, secondary schema indexes, write-back caches, bulk-import tools — but the underlying tension never fully goes away. The right answer in production is almost always both: a relational system of record for tabular truth, a native graph alongside it for traversal-heavy queries, replicated through CDC. The next chapter looks at the traversal primitives those native engines expose — out, in, both, step, path — and how they compose into the query languages (Cypher, Gremlin, GSQL) you actually write against them.

References

1. Neo4j, Database internals: storage engine — neo4j.com/docs/operations-manual/current/database-internals/. Definitive on-disk layout reference.
2. Robinson, Webber, Eifrem, Graph Databases (2nd ed., OReilly, 2015), Chapter 6 — [graphdatabases.com](https://graphdatabases.com/). The canonical exposition of index-free adjacency, by Neo4js founders.
3. Neo4j blog, Graph databases for beginners: native vs non-native graph technology — neo4j.com/blog/native-vs-non-native-graph-technology/. The original "index-free adjacency" framing.
4. JanusGraph documentation, Storage backends overview — docs.janusgraph.org/storage-backend/. How a storage-agnostic graph engine maps adjacency onto Cassandra, HBase, and BerkeleyDB.
5. Apache TinkerPop, Why graphs? — tinkerpop.apache.org/docs/current/reference/. The reference Gremlin guide includes a clear treatment of when graph traversal beats relational joins.
6. Malewicz et al., Pregel: a system for large-scale graph processing, SIGMOD 2010 — research.google/pubs/pregel-a-system-for-large-scale-graph-processing/. The other influential graph-storage school: vertex-centric, not adjacency-centric.