Index-Free Adjacency and Physical Storage
You'll learn how native graph databases physically store relationships as direct pointers to achieve constant-time traversal without index lookups.
The Core Concept
In a native graph database, relationships aren't stored as foreign keys that need index lookups—they're stored as physical pointers directly connecting records. This is called index-free adjacency, meaning each node contains direct references to its adjacent neighbors stored right alongside it on disk.
Think of it like a web page with hyperlinks: clicking a link takes you directly to the next page instantly. You don't need to consult a phonebook (index) first to find where that page lives—the link is the address.
How It Works Physically
When you create a relationship between nodes, the database writes a direct disk pointer from one node's record to the other. When traversing from Node A to Node B:
- Read Node A's record from disk
- Follow the stored pointer directly to Node B's physical location
- Read Node B immediately—no index consultation needed
This is O(1) constant time per hop, regardless of graph size.
Contrast with Non-Native Approaches
In a relational database or non-native graph store, traversing "friends of friends" requires:
- Querying an index for Node A's relationships
- Retrieving matching rows
- Querying the index again for each friend's relationships
- Joining results
Each step requires index lookups that scale with data volume—O(log n) at best per hop.
Why It Matters
For deep traversals (6 degrees of separation, shortest paths, recommendation chains), the difference is dramatic. Native storage with index-free adjacency keeps traversal time proportional to the path length, not the database size.
Key Takeaway: Index-free adjacency stores relationships as physical pointers, enabling constant-time traversal from node to node without consulting indexes—the secret to graph databases' traversal speed.