Databases Reference
In-Depth Information
Figure 6-5. How a graph is physically stored in Neo4j
With fixed-sized records and pointer-like record IDs, traversals are implemented simply
by chasing pointers around a data structure, which can be performed at very high speed.
To traverse a particular relationship from one node to another, the database performs
several cheap ID computations (these computations are much cheaper than searching
global indexes, as we'd have to do if faking a graph in a nongraph native database):
1. From a given node record, locate the first record in the relationship chain by com‐
puting its offset into the relationship store—that is, by multiplying its ID by the
fixed relationship record size (remember, that's 33 bytes at the time of writing). This
gets us directly to the right record in the relationship store.
2. From the relationship record, look in the
second node
field to find the ID of the
second node. Multiply that ID by the node record size (nine bytes at the time of
writing) to locate the correct node record in the store.
Should we wish to constrain the traversal to relationships with particular types, then
we'd add a lookup in the relationship type store. Again this is a simple multiplication of
ID by record size (five bytes at the time of writing) to find the offset for the appropriate
relationship type record in the relationship store.
In addition to the node and relationship stores, which contain the graph structure, we
have the property store files. These store the user's key-value pairs. Recall that Neo4j,
being a property graph database, allows properties—name-value pairs—to be attached
