Databases Reference
In-Depth Information
query times are independent of the total size of the graph, and are instead simply pro‐
portional to the amount of the graph searched.
A nonnative graph database engine, in contrast, uses (global) indexes to link nodes
together, as shown in
Figure 6-1
. These indexes add a layer of indirection to each tra‐
versal, thereby incurring greater computational cost. Proponents for native graph pro‐
cessing argue that index-free adjacency is crucial for fast, efficient graph traversals.
To understand why native graph processing is so much more efficient
than graphs based on heavy indexing, consider the following. Depend‐
ing on the implementation, index lookups could be
O(log n)
in algo‐
rithmic complexity versus
O(1)
for looking up immediate relationships.
To traverse a network of
m
steps, the cost of the indexed approach, at
O(m log n)
, dwarfs the cost of
O(m)
for an implementation that uses
index-free adjacency.
Figure 6-1. Nonnative graph processing engines use indexing to traverse between nodes
