Graph Databases

You're building a social network. A user wants to see "friends of friends who also like hiking." Sounds simple enough. In SQL:

SELECT DISTINCT fof.name
FROM friendships f1
JOIN friendships f2 ON f1.friend_id = f2.user_id
JOIN user_interests ui ON f2.friend_id = ui.user_id
WHERE f1.user_id = 42 AND ui.interest = 'hiking'
AND f2.friend_id NOT IN (SELECT friend_id FROM friendships WHERE user_id = 42);

With 1 million users and 50 million friendships, this query takes 30+ seconds. Now add "friends of friends of friends", a 3-hop traversal. The SQL query becomes a monster of nested JOINs, and the execution time jumps to minutes.

LinkedIn encountered this when building their "People You May Know" feature. Twitter faced it when computing follower recommendations. Facebook needed it for their social graph. 2 billion nodes and hundreds of billions of edges.

The problem isn't that SQL databases are slow. The problem is that relational databases store relationships as foreign keys in tables, and traversing those relationships requires expensive JOIN operations that get exponentially worse with each hop.

Graph databases store relationships differently. Instead of a foreign key that says "this row is connected to that row in another table," a graph database stores a direct pointer from one node to another. Traversing a relationship is a pointer lookup. O(1), regardless of the total size of the graph.

That "friends of friends who like hiking" query? Milliseconds in Neo4j.

A graph database stores data as three things:

Nodes. Entities. A person, a product, a city, a bank account. Each node has a label (type) and properties (key-value attributes).

Edges (Relationships). Connections between nodes. "Alice FOLLOWS Bob," "Alice PURCHASED Product-123," "NYC IS_IN USA." Each edge has a type and optional properties (like a timestamp or weight).

Properties. Key-value pairs on both nodes and edges. A person node might have {name: "Alice", age: 30}. A PURCHASED edge might have {date: "2025-01-15", amount: 99.99}.

(Alice:Person {age: 30}) -[:FOLLOWS {since: "2024-01"}]-> (Bob:Person {age: 25})
(Alice:Person) -[:PURCHASED {amount: 99}]-> (Widget:Product {category: "electronics"})
(Bob:Person) -[:FOLLOWS]-> (Carol:Person)
(Carol:Person) -[:FOLLOWS]-> (Alice:Person)

The key idea: relationships are stored as physical pointers between nodes, not as rows in a separate table. When Neo4j stores that Alice follows Bob, it literally creates a direct link from Alice's node to Bob's node in the storage engine. To traverse from Alice to Bob, the database follows one pointer. No index lookup, no table scan, no hash join.

This is called index-free adjacency, the most important concept in graph database design. It means the cost of traversing a relationship is constant, regardless of the total size of the graph. A graph with 100 million nodes traverses a single edge just as fast as a graph with 100 nodes.