What Are Graph Databases and Index-Free Adjacency?

Definition
Graph databases optimize for relationship-first workloads using nodes (entities) and relationships (edges) as first-class citizens. They use index-free adjacency where relationships are physical pointers, enabling O(1) traversal per hop regardless of graph size.
Index-Free Adjacency
Relational databases compute joins at query time by scanning indexes. Graph databases store relationships as physical pointers between nodes. Traversing from one node to its neighbors is O(1) (constant time) regardless of total graph size. Following 5 hops in a billion-node graph takes the same time as in a thousand-node graph because you only visit nodes on your path, not the entire dataset.
Performance and Transactions
Graph databases are OLTP systems (Online Transaction Processing: real-time operations like lookups and updates). They provide ACID guarantees (Atomicity, Consistency, Isolation, Durability) ensuring transactions either fully complete or fully rollback. Bounded traversals of 1-4 hops typically complete in single-digit to tens of milliseconds when the active subgraph fits in memory. Most graph databases use a schema-optional model: you can add new node types and relationship types without migrations, enabling rapid domain evolution.
When Graphs Excel
Ideal for: social networks (friends of friends), recommendation engines (users who bought X also bought Y), fraud detection (connected suspicious accounts), and knowledge graphs. A query like "find friends of friends within 3 degrees who like jazz" executes as a simple pattern match in milliseconds.
Limitations
Graph databases struggle with: global analytics across the entire dataset, high-throughput fan-out writes (writing to millions of targets), workloads with sparse relationships, or access patterns not involving traversal. Scaling is also challenging: most work best when the graph fits in memory on a single node.

💡 Key Takeaways

✓Index-free adjacency stores relationships as physical pointers enabling O(1) (constant time) traversal per hop regardless of graph size

✓Query performance proportional to subgraph touched, not total data. Visiting 1,000 nodes in billion-node graph = 1,000 operations

✓OLTP systems (real-time operations) with ACID guarantees (transactions fully complete or rollback); 1-4 hop traversals complete in single-digit to tens of ms

✓Schema-optional model allows adding new node and relationship types without migrations enabling rapid domain evolution

✓Ideal for social networks, recommendations, fraud detection, knowledge graphs where value comes from traversing connections

✓Poor fit for global analytics across entire graph, high-throughput fan-out writes, or workloads with sparse relationships

📌 Interview Tips

1Compare traversal: SQL "friends of friends of friends" requires 3 self-joins. Graph follows pointers: 100 friends x 100 x 100 = 1M operations, each O(1).

2Index-free adjacency: each node stores relationship pointers. Following edge = dereferencing memory address (nanoseconds), not scanning B-tree (microseconds).

3ACID in action: fraud detection query finds suspicious cluster and atomically flags all accounts in one transaction, or rolls back entirely if any step fails.

← Back to Graph Databases (Neo4j) Overview