Designing a Graph Database: Storage Engines, Query Optimization, and Traversal Patterns for Connected Data

Most data has relationships. A user follows another user. A product belongs to a category, which belongs to a taxonomy. A transaction links an account, a merchant, and a device fingerprint. Relational databases can model all of this, but the query cost grows with hop count. A two-hop join across millions of rows is fine. A six-hop query across a billion edges is not.

Graph databases exist to answer the specific question: how do nodes connect to each other, and how do you traverse those connections efficiently at scale? The answer requires different storage primitives, different query semantics, and different operational tradeoffs than what you get with a B-tree and SQL.

This article covers the internals: how graph data is stored, how query planners optimize traversals, what the production failure modes look like, and where the meaningful differences between systems actually are.

---

The Two Data Models: Property Graph vs RDF

Before choosing a storage engine, you need to commit to a data model.

Property graphs (used by Neo4j, Memgraph, Amazon Neptune in its property graph mode) represent data as nodes and edges, both of which can carry arbitrary key-value properties. A node might be (:User {id: "u1", name: "Alice"}). An edge might be -[:FOLLOWS {since: "2024-01-15"}]->. The model is schema-optional and maps naturally to how engineers think about domain objects.

RDF (Resource Description Framework) represents data as subject-predicate-object triples: <alice> <follows> <bob>. Properties are also triples: <alice> <name> "Alice". RDF databases (SPARQL endpoints, Amazon Neptune in RDF mode) are designed around the semantic web stack. They have formal ontology support via OWL and RDFS, which matters for knowledge graph applications but adds complexity for product engineers.

The practical difference: if you are building a social graph, a recommendation engine, or a fraud detection system, use a property graph. If you are building a knowledge base that needs to interoperate with external ontologies or reason over class hierarchies, RDF is worth the overhead.

---

Storage Engine Internals

Adjacency Lists vs Adjacency Matrices

The naive data structure question for any graph: do you store connectivity as an adjacency list or an adjacency matrix?

An adjacency matrix is an N x N boolean grid where M[i][j] = true means an edge from node i to node j. Lookup for a single edge is O(1). But space is O(N²), which is prohibitive for sparse graphs. Real-world graphs are almost always sparse: a social network with 100 million users where each user follows an average of 500 others has a density of 0.0000005%. An adjacency matrix for that graph would require roughly 10^15 bits of storage.

Adjacency lists store, for each node, the list of its neighbors. Space is O(N + E) where E is the number of edges. For sparse graphs, this is far more efficient. The tradeoff is that checking whether a specific edge exists requires scanning the neighbor list (O(degree) in the worst case) unless you add secondary indexing.

Production graph databases use adjacency lists as the baseline representation, then layer additional structures on top.

Index-Free Adjacency

Index-free adjacency is the key structural property that separates native graph databases from relational systems with graph extensions.

In a relational database, traversing from node A to its neighbors requires a join: look up rows in an edge table where the source column equals A’s ID. That join consults a B-tree index on the source column. The index lookup cost is O(log N) where N is the total number of edges in the table.

In a native graph database with index-free adjacency, each node record contains direct physical pointers to its adjacent edge records. There is no index lookup. Traversing from a node to its neighbors is O(1) per hop because you are following a pointer, not executing a query.

This makes the per-hop cost constant rather than logarithmic. For shallow traversals (one or two hops) the difference is modest. For deep traversals (six or more hops, as in fraud ring detection or recommendation chains), the difference compounds dramatically. A six-hop traversal with O(log N) per hop at N = 10 billion edges costs roughly 33 operations per step. The same traversal with index-free adjacency costs 1 operation per step.

The physical layout looks like this:

Node Record [id=u1]
  - properties: { name: "Alice" }
  - first_outgoing_edge: ptr -> Edge[e1]
  - first_incoming_edge: ptr -> Edge[e5]

Edge Record [id=e1]
  - type: FOLLOWS
  - properties: { since: "2024-01-15" }
  - source_node: ptr -> Node[u1]
  - target_node: ptr -> Node[u2]
  - next_outgoing_edge_from_source: ptr -> Edge[e2]
  - next_incoming_edge_to_target: ptr -> Edge[e7]

Traversal becomes a pointer walk: start at node u1, follow first_outgoing_edge to e1, read target_node to reach u2, follow next_outgoing_edge_from_source to e2, and so on. No index consulted, no B-tree descended.

The cost of this design: node and edge records must fit in a predictable, fixed-size format to make pointer arithmetic work. Property storage is typically offloaded to a separate variable-length store, with the fixed-size record containing just a pointer to the property data.

---

Query Optimization for Multi-Hop Traversals

The Supernode Problem

Before discussing query optimization, you need to understand the failure mode it is designed to avoid.

A supernode (sometimes called a “dense node”) is a node with an exceptionally high degree, far above the graph average. In a social graph, a celebrity account might have 50 million followers. In a product graph, a generic category node might have 10 million child nodes. Queries that traverse through a supernode unexpectedly expand into tens of millions of paths.

A Cypher query like:

MATCH (a:User)-[:FOLLOWS]->(b:User)-[:FOLLOWS]->(c:User)
WHERE a.id = 'alice'
RETURN c

seems harmless. But if any intermediate node b is a celebrity with millions of followers, the intermediate result set explodes. The query engine has to materialize and filter millions of paths before pruning.

Production systems deal with this through a combination of:

1. Degree-aware query planning: the query planner checks degree statistics and reorders traversal steps to start from low-degree nodes.
2. Explicit degree caps: many systems allow you to set a maximum degree to traverse through, skipping supernodes entirely.
3. Lazy evaluation: the traversal emits results as it finds them rather than materializing all paths before returning anything. This lets the application impose a LIMIT that causes early termination.

BFS vs DFS Traversal

The choice between breadth-first and depth-first traversal is not aesthetic. It has direct consequences for memory usage and query latency.

BFS (breadth-first search) explores all neighbors at depth 1 before any at depth 2. It finds the shortest path between two nodes if one exists. Memory usage scales with the frontier size at each layer, which can be large for dense graphs. BFS is the right default for shortest-path queries.

DFS (depth-first search) follows one path as far as possible before backtracking. Memory usage scales with the maximum depth, not the frontier width. DFS is better for reachability queries where you want to know whether any path exists, not the shortest one. It also terminates early once a path is found.

Here is a typed BFS implementation illustrating how a traversal engine builds the frontier:

interface GraphNode {
  id: string;
  properties: Record<string, unknown>;
}

interface GraphEdge {
  id: string;
  type: string;
  sourceId: string;
  targetId: string;
  properties: Record<string, unknown>;
}

interface GraphStore {
  getNode(id: string): GraphNode | null;
  getOutgoingEdges(nodeId: string, type?: string): GraphEdge[];
}

interface TraversalOptions {
  maxDepth: number;
  edgeTypes?: string[];
  maxDegreePerNode?: number;
}

function bfsTraversal(
  store: GraphStore,
  startId: string,
  options: TraversalOptions
): Map<string, number> {
  const visited = new Map<string, number>(); // nodeId -> depth
  const queue: Array<{ id: string; depth: number }> = [
    { id: startId, depth: 0 },
  ];

  visited.set(startId, 0);

  while (queue.length > 0) {
    const current = queue.shift()!;

    if (current.depth >= options.maxDepth) {
      continue;
    }

    const edges = store.getOutgoingEdges(current.id, options.edgeTypes?.[0]);
    const edgesToProcess = options.maxDegreePerNode
      ? edges.slice(0, options.maxDegreePerNode)
      : edges;

    for (const edge of edgesToProcess) {
      if (!visited.has(edge.targetId)) {
        visited.set(edge.targetId, current.depth + 1);
        queue.push({ id: edge.targetId, depth: current.depth + 1 });
      }
    }
  }

  return visited;
}

The maxDegreePerNode parameter is how you handle supernodes in application code when the query engine does not expose a degree cap.

Bidirectional BFS for Shortest Path

For shortest-path queries between two specific nodes, unidirectional BFS explores up to O(k^d) nodes where k is the average degree and d is the path length. Bidirectional BFS runs two simultaneous BFS frontiers from both ends and meets in the middle, reducing the search space to roughly O(2 * k^(d/2)). For graphs with average degree 20 and path length 6, that is the difference between 64 million node visits and 800.

function bidirectionalBFS(
  store: GraphStore,
  sourceId: string,
  targetId: string,
  maxDepth: number
): string[] | null {
  const forwardVisited = new Map<string, string | null>(); // nodeId -> parentId
  const backwardVisited = new Map<string, string | null>();

  forwardVisited.set(sourceId, null);
  backwardVisited.set(targetId, null);

  let forwardFrontier = [sourceId];
  let backwardFrontier = [targetId];

  for (let depth = 0; depth < maxDepth / 2; depth++) {
    const nextForward: string[] = [];

    for (const nodeId of forwardFrontier) {
      for (const edge of store.getOutgoingEdges(nodeId)) {
        if (!forwardVisited.has(edge.targetId)) {
          forwardVisited.set(edge.targetId, nodeId);
          nextForward.push(edge.targetId);
        }
        if (backwardVisited.has(edge.targetId)) {
          // Meeting point found: reconstruct path
          return reconstructPath(
            forwardVisited,
            backwardVisited,
            edge.targetId
          );
        }
      }
    }

    forwardFrontier = nextForward;

    const nextBackward: string[] = [];

    for (const nodeId of backwardFrontier) {
      for (const edge of store.getOutgoingEdges(nodeId)) {
        if (!backwardVisited.has(edge.targetId)) {
          backwardVisited.set(edge.targetId, nodeId);
          nextBackward.push(edge.targetId);
        }
        if (forwardVisited.has(edge.targetId)) {
          return reconstructPath(
            forwardVisited,
            backwardVisited,
            edge.targetId
          );
        }
      }
    }

    backwardFrontier = nextBackward;
  }

  return null;
}

function reconstructPath(
  forward: Map<string, string | null>,
  backward: Map<string, string | null>,
  meetingPoint: string
): string[] {
  const path: string[] = [];

  let current: string | null = meetingPoint;
  while (current !== null) {
    path.unshift(current);
    current = forward.get(current) ?? null;
  }

  current = backward.get(meetingPoint) ?? null;
  while (current !== null) {
    path.push(current);
    current = backward.get(current) ?? null;
  }

  return path;
}

---

Sharding Graph Data

Sharding a graph database is genuinely hard. The problem is that edges are the unit of access, and edges cross shard boundaries. If node A is on shard 1 and node B is on shard 2, traversing the edge A-B requires a cross-shard network call. Deep traversals accumulate these cross-shard calls, and latency compounds with each hop.

Random (hash-based) partitioning distributes nodes uniformly across shards by hashing the node ID. Write throughput is balanced. But traversals frequently cross shards, and for random graphs the expected number of cross-shard edges is (S-1)/S where S is the number of shards. With 10 shards, 90% of edges cross shard boundaries. Deep traversals become distributed fan-outs.

Community-based partitioning uses graph partitioning algorithms (METIS, Louvain clustering) to group tightly connected nodes onto the same shard, minimizing the number of cut edges. This dramatically improves traversal locality for queries that stay within a community. The cost: partitioning is expensive to compute and must be recomputed as the graph evolves. Hot communities cause hotspot shards. And it only helps if your query patterns align with community structure.

Replicated edges are the pragmatic middle ground for read-heavy workloads. When a node is accessed from multiple shards, store a replica of its adjacency list on each shard. Reads become local. Writes require coordinated updates across replicas, so you need a fan-out mechanism and accept eventual consistency on the replica data.

The honest production answer: if your query patterns can be bounded to local neighborhoods (e.g., “show the friends of this user”), community-based partitioning with replication of high-degree nodes is the best tradeoff. If your queries are global (e.g., “find any path between these two nodes”), sharding fundamentally limits you and you may need to accept higher latency or partition your query into bounded subgraph lookups.

---

Tradeoffs Table: Neo4j vs Amazon Neptune vs Memgraph

Dimension	Neo4j	Amazon Neptune	Memgraph
Storage model	Native property graph with index-free adjacency	Property graph (openCypher) and RDF (SPARQL)	Native in-memory property graph
Query language	Cypher (origin)	openCypher, Gremlin, SPARQL	Cypher with MAGE extensions
Latency profile	Low for deep traversals on warm data; higher on first access after GC	Higher p99 due to managed infrastructure overhead	Sub-millisecond for in-memory graphs
Scale ceiling	Sharded cluster supports billions of nodes; operational complexity scales with it	Serverless tier scales automatically; dedicated cluster for predictable workloads	Bounded by available RAM; disk-backed mode adds latency
Durability model	WAL + periodic checkpoints; ACID transactions	Multi-AZ replication with automatic failover	In-memory with periodic snapshotting; disk-backed mode for durability
Operational burden	High for self-managed; Enterprise includes clustering	Low for serverless; medium for provisioned clusters	Low for single-node; higher for HA setup
Best fit	Large-scale on-prem or VM deployments; long-term graph workloads	AWS-native teams who want managed infrastructure	Real-time graph analytics where sub-ms latency is required and data fits in memory
Weak points	Memory consumption for large property sets; complex upgrade paths	Cross-AZ latency for write-heavy workloads; cold-start on serverless	Data size bounded by RAM; persistence is secondary

---

Production Considerations

Cardinality estimation for query planning. Graph query planners need accurate statistics to choose optimal traversal order. Most systems maintain degree histograms per node label and edge type. If these statistics are stale (after a large import, for instance), the planner makes wrong decisions. Force a statistics refresh after bulk imports. In Neo4j, this is CALL db.stats.retrieve("GRAPH COUNTS") followed by a cache warm-up pass.

Write amplification on dense graphs. When a new edge is inserted between two nodes, the database must update the adjacency lists of both nodes. For supernodes with millions of edges, this update touches a large in-memory structure and may require rewriting a significant portion of the edge chain on disk. Batch edge insertions and consider using a staging table for bulk loads.

Memory management. Native graph databases keep the working set of nodes and edges in memory. A graph with 1 billion nodes at 32 bytes per node record requires 32 GB just for node storage, before edges or properties. Profile your working set against your expected query patterns. If your queries are localized (social graph traversal for individual users), you can get away with caching a fraction of the graph. If your queries are global (fraud ring detection that touches random parts of the graph), you need the full graph in memory or you will be hitting disk constantly.

Cycle detection. Graphs can have cycles, and traversal algorithms that do not track visited nodes will loop forever. The BFS implementation above tracks visited nodes in a Map. In production, that Map can grow to hundreds of millions of entries for global graph traversals. Consider bloom filters for approximate cycle detection at the cost of false positives, or impose strict depth limits and rely on the query engine’s built-in cycle handling.

Schema evolution. Graph schemas evolve organically: new node labels appear, edge types get added, properties are renamed. Because property graphs are schema-optional, nothing breaks at the database level when you add a new label. But your application code that pattern-matches on labels and properties will need migration. Treat schema changes as data migrations: add new properties alongside old ones, backfill, then remove old properties. Never rename a property in-place without a compatibility window.

Observability. The metrics that matter for graph workloads are different from relational workloads. Track traversal depth distribution (the 99th percentile depth tells you if queries are unexpectedly deep), cache hit ratio for node and edge records, cross-shard hop count for distributed deployments, and supernode hit rate (how often traversals pass through nodes with degree above your threshold). These four metrics will surface the pathological queries before they become incidents.

---

When a Graph Database Is Not the Answer

Graph databases solve a specific problem: traversal of connected data where hop count is high and path structure matters. They are not a better general-purpose database.

If your primary access pattern is looking up records by ID or filtering by attribute value, a relational database with proper indexing is simpler to operate and query. If your “graph” queries never go deeper than two hops, a join in Postgres with indexed foreign keys will outperform a graph database because it does not carry the operational overhead.

Graph databases pay off when: traversal depth regularly exceeds three hops, path structure is part of the query (not just reachability), and relationship properties are as important as node properties. Fraud ring detection, recommendation engines, knowledge graphs, and access control systems (hierarchical permissions) are the domains where graph databases consistently justify their complexity.

If you are uncertain, model your data in a relational schema first. If you find yourself writing queries with four or more self-joins, or if your query times are dominated by join operations on relationship tables, that is the inflection point where migrating to a property graph becomes defensible.

---

The fundamental insight of graph database design is that index-free adjacency changes the cost model for traversal from logarithmic to constant per hop. That single property explains why native graph databases exist as a distinct category: not because they are better at everything, but because for multi-hop traversal at scale, pointer-following beats index-consulting every time. The rest of the design decisions follow from managing the consequences of that storage layout.