Databases Reference
In-Depth Information
Figure 6-1
shows how a nonnative approach to graph processing works. To find Alice's
friends we have first to perform an index lookup, at cost
O(log n)
. This may be acceptable
for occasional or shallow lookups, but it quickly becomes expensive when we reverse
the direction of the traversal. If, instead of finding Alice's friends, we wanted to find out
who is friends with Alice, we would have to perform multiple index lookups, one for
each node that is potentially friends with Alice. This makes the cost far more onerous.
Whereas it's
O(log n)
cost to find out who are Alice's friends, it's
O(m log n)
to find out
who is friends with Alice.
Index-Free Adjacency Leads to Lower-Cost “Joins”
With index-free adjacency, bidirectional joins are effectively precomputed and stored
in the database as relationships. In contrast, when using indexes to fake connections
between records, there is no
actual
relationship stored in the database. This becomes
problematic when we try to traverse in the “opposite” direction from the one for which
the index was constructed. Because we have to perform a brute-force search through
the index—which is an
O(n)
operation—joins like this are simply too costly to be of any
practical use.
Index lookups are fine for small networks, such as the one in
Figure 6-1
, but too costly
for complex queries over larger graphs. Instead of using index lookups to make rela‐
tionships concrete and navigable at query time, graph databases such as Neo4j with
native graph processing capabilities use index-free adjacency to ensure high-
performance traversals.
Figure 6-2
shows how relationships eliminate the need for index
lookups.
Figure 6-2. Neo4j uses relationships, not indexes, for fast traversals
Recall that in a general-purpose graph database relationships can be traversed in either
direction (tail to head, or head to tail) extremely cheaply. As we see in
Figure 6-2
, to
find Alice's friends using a graph, we simply follow her outgoing
FRIEND
relationships,
