Graph Database Storage Models: Native vs Non-Native

Introduction

Graph databases store and query data modeled as vertices and edges.
How a system physically persists and traverses this graph structure has profound consequences for query performance, scalability, and operational characteristics.
The core architectural distinction in graph database storage is between native and non-native approaches.
A native graph storage engine is purpose-built so that vertices and edges are first-class citizens on disk, with direct physical pointers or adjacency structures between adjacent elements.
A non-native approach layers a graph abstraction on top of a general-purpose storage engine (relational tables, document stores, key-value stores) and translates graph operations into that engine's primitives.

This distinction is not merely academic.
It determines whether a multi-hop traversal executes in time proportional to the local neighborhood size or proportional to the total dataset.
Understanding the tradeoffs is essential for engineers choosing or building graph data infrastructure.

Native Graph Storage

Index-Free Adjacency

The defining property of native graph storage is index-free adjacency — a term popularized in the context of Neo4j, though the underlying concept applies broadly to native designs.
Each node record contains a direct physical pointer (an offset or a fixed-size record ID) to its first relationship record.
In Neo4j's implementation, each relationship record contains pointers to the next relationship for both its start and end nodes, forming doubly-linked lists of relationships around each node.
Other native engines may use different adjacency representations, such as compressed sparse row (CSR) layouts, but the key property is the same: traversal from one node to an adjacent node requires following a fixed number of pointer dereferences, with no global index lookup required.

This means that the cost of traversing a single edge is O(1) with respect to the total size of the graph.
A k-hop traversal touching m edges costs O(m), regardless of whether the graph contains thousands or billions of nodes.
This is the fundamental performance guarantee that native storage provides.

Physical Record Layout

Neo4j 3.x's store files illustrate the native approach concretely.
The node store uses fixed-size 15-byte records, each containing:

• An in-use flag
• The ID of the node's first relationship
• The ID of the node's first property
• A label pointer
• Flags for dense node handling

The relationship store uses fixed-size 34-byte records, containing:

• The IDs of the start and end nodes
• A relationship type pointer
• Pointers to the next and previous relationship records for both the start node's chain and the end node's chain
• A first-property pointer

Note: Neo4j 4.x and later introduced a block-based store format with different physical layouts; the figures above apply to the 3.x store format.
The underlying principle — fixed-size records enabling direct offset calculation — is preserved across versions.

Fixed-size records are critical.
Because every record is the same width, the physical offset of record N is simply N * record_size.
This transforms record IDs into direct file offsets, eliminating the need for a B-tree or hash index to locate a record.
The pointer-chasing pattern maps naturally to memory-mapped I/O, where frequently accessed neighborhoods stay in the OS page cache.

Advantages

• Traversal performance scales with the query, not the dataset. Neighborhood lookups are constant-time per hop.
• Predictable latency. Pointer dereferences have uniform cost, avoiding the logarithmic overhead of index probes.
• Compact relationship representation. Doubly-linked chains encode adjacency without redundant copies of node IDs in a global index.

Disadvantages

• Write amplification on high-degree nodes. Inserting a relationship requires updating pointers in linked-list chains. For very high-degree ("dense") nodes, these chains become long, and sequential scans through them degrade. Neo4j mitigates this with a secondary grouping structure for dense nodes.
• Garbage and fragmentation. Deleting nodes or relationships creates holes in fixed-size record files. Compaction or reuse strategies are necessary.
• Limited flexibility. The storage engine is tightly coupled to the graph model. Supporting additional access patterns (full-text search, range scans on properties) typically requires layering secondary indexes on top, partially negating the native purity.
• Distribution complexity. Physical pointers encode local file offsets, making it difficult to repartition a native graph across machines without invalidating or remapping those pointers.

Non-Native Graph Storage

A non-native graph database uses an existing storage engine and translates graph operations into that engine's primitives.
Common backing stores include:

• Relational tables: Nodes in one table, edges in another, with foreign keys. JanusGraph on top of Apache Cassandra or HBase is a widely deployed example.
• Quad-based stores: Amazon Neptune stores data as quads (Subject, Predicate, Object, Graph) with multiple index orders, enabling graph traversal without a dedicated pointer structure.
• Key-value stores: Adjacency lists serialized as values keyed by vertex ID.
• Document stores: Each vertex document embeds or references its edges.

Note on TigerGraph: TigerGraph is often classified as a native graph engine because it uses a proprietary MPP (massively parallel processing) storage layer with physical adjacency structures, and it is listed here as a point of comparison.
It is listed here as a point of comparison but should not be conflated with JanusGraph-style non-native architectures.

How Traversal Works

Without physical pointers between records, traversing an edge requires an index lookup.
To find all neighbors of vertex V, the engine must query an index on the edge table (or edge column family) for rows where source = V.
This lookup typically costs O(log N) for a B-tree index or O(1) amortized for a hash index, where N is the total number of edges in the system.

For a single hop, this overhead may be negligible.
Over a k-hop traversal, the cost compounds: each hop requires a separate index probe, and the total cost depends on both the traversal width and the global index size.
Under memory pressure, these index probes translate into random I/O across large index structures, whereas native pointer chasing confines I/O to the local neighborhood's pages.

Advantages

• Leverage mature storage infrastructure. B-tree implementations, LSM compaction, replication, and backup tooling from the backing store is inherited directly.
• Flexible data modeling. Adding non-graph access patterns (aggregations, range queries, full-text search) is straightforward because the backing store already supports them.
• Horizontal scalability. Distributed key-value and wide-column stores provide well-understood partitioning and replication.
• Operational familiarity. Teams already operating Cassandra or PostgreSQL can adopt a graph layer without introducing a new storage subsystem.

Disadvantages

• Traversal cost is data-dependent. Each hop involves an index probe whose cost grows (at least logarithmically) with total data size.
• Higher per-hop latency. Even with warm caches, an index lookup involves more instructions and more cache lines than a pointer dereference.
• Join-like overhead. Multi-hop queries resemble multi-way joins, inheriting the planning complexity and potential for intermediate result explosion found in relational engines.

Walkthrough

The following walkthrough compares how a 2-hop neighbor query executes under both models.
The query: "Find all friends-of-friends of node A."

Native Storage (Pointer Chasing)

1. Read node record for A at offset (A.id * node_record_size).
2. Follow A's first_relationship pointer to relationship R1.
3. Walk R1's linked list to collect all relationships of A.
   For each relationship Ri:
     a. Read the "other node" ID from Ri (the neighbor B).
     b. Read node record for B at offset (B.id * node_record_size).
     c. Follow B's first_relationship pointer.
     d. Walk B's relationship chain to collect B's neighbors.
4. Deduplicate collected 2nd-hop node IDs.
5. Return result set.

Cost model: Steps 3–3d touch only the records physically adjacent in the relationship chains of A and each B.
No global index is consulted.
Total I/O is proportional to deg(A) + sum(deg(Bi)), independent of total graph size.

Non-Native Storage (Index Lookup)

1. Query edge index for all edges where source = A.
   This performs a B-tree probe: O(log E) where E = total edges.
2. For each returned neighbor B:
     a. Query edge index for all edges where source = B.
        Another B-tree probe: O(log E).
3. Deduplicate collected 2nd-hop node IDs.
4. Return result set.

Cost model: Each hop requires an index probe costing O(log E).
Total index probes: 1 + deg(A).
Under cold-cache conditions, each probe may require multiple random disk reads through index internal nodes.
As E grows into the billions, the tree depth increases and buffer pool pressure on index pages rises.

Practical Implications

For small graphs (millions of edges), the difference in per-hop cost may be undetectable because index pages fit in memory.
For large graphs (billions of edges) with deep traversals (4+ hops), native storage can provide order-of-magnitude latency improvements.
Conversely, non-native systems that need to support mixed workloads (graph traversal plus analytical aggregation plus text search) may accept the per-hop overhead in exchange for operational simplicity and flexible querying.

The Blurring Line

Modern systems increasingly blur the native/non-native boundary.
Neo4j has added secondary indexes and analytical capabilities that go beyond pure pointer-chasing.
JanusGraph introduced vertex-centric indexes to accelerate traversal of high-degree vertices within its non-native model.
Dgraph has used posting-list-based adjacency representations backed by an LSM-tree key-value store (Badger in earlier versions; its storage architecture has evolved across releases and should be verified against current documentation).
The architectural choice is better understood as a spectrum than a binary classification, with the tradeoff axis running between traversal-optimized locality and general-purpose flexibility.

Key Points

• Native graph storage achieves O(1) per-hop traversal cost through index-free adjacency, using physical pointers between fixed-size node and relationship records.
• Non-native graph storage translates graph operations into index lookups on a general-purpose backing store, incurring O(log N) cost per hop for B-tree indexes.
• The performance gap between native and non-native models widens as graph size and traversal depth increase, particularly under memory pressure.
• Non-native approaches inherit the operational maturity, horizontal scalability, and flexible access patterns of their backing stores.
• Native systems face challenges with high-degree nodes, record fragmentation, and the difficulty of distributing pointer-based structures across machines.
• Fixed-size records are the mechanism that converts record IDs into direct file offsets, enabling index-free record lookups in native engines.
• The distinction is a spectrum: modern systems combine elements of both approaches (vertex-centric indexes, secondary indexes, hybrid storage layouts) to balance traversal speed and query flexibility.

References

Robinson, I., Webber, J., and Eifrem, E. "Graph Databases: New Opportunities for Connected Data." O'Reilly Media, 2nd Edition, 2015.

Angles, R. and Gutierrez, C. "Survey of Graph Database Models." ACM Computing Surveys, Vol. 40, No. 1, Article 1, 2008.

Bonifati, A., Fletcher, G., Voigt, H., and Yakovets, N. "Querying Graphs." Synthesis Lectures on Data Management, Morgan & Claypool, 2018.

Deutsch, A., et al. "Graph Pattern Matching in GQL and SQL/PGQ." Proceedings of the ACM SIGMOD International Conference on Management of Data, 2022.

Sahu, S., Mhedhbi, A., Salihoglu, S., Lin, J., and Ozsu, M. T. "The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing." The VLDB Journal, Vol. 29, 2020.