Graph Database Internals - Graph Databases - page 145

their graph and the actual records on disk are structurally dissimilar. Let's start our
exploration of physical storage by looking at the structure of nodes and relationships
on disk as shown in Figure 6-4 .
Figure 6-4. Neo4j node and relationship store file record structure
The node store file stores node records. Every node created in the user-level graph ends
up in the node store, the physical file for which is neostore.nodestore.db . Like most
of the Neo4j store files, the node store is a fixed-size record store, where each record is
nine bytes in length. Fixed-size records enable fast lookups for nodes in the store file:
if we have a node with id 100 , then we know its record begins 900 bytes into the file.
Based on this format, the database can directly compute a record's location, at cost
O(1) , rather than performing a search, which would be cost O(log n) .
The first byte of a node record is the in-use flag. This tells the database whether the
record is currently being used to store a node, or whether it can be reclaimed on behalf
of a new node (Neo4j's .id files keep track of unused records). The next four bytes
represent the ID of the first relationship connected to the node, and the last four bytes
represent the ID of the first property for the node. The node record is pretty lightweight:
it's really just a couple of pointers to lists of relationships and properties.
Correspondingly, relationships are stored in the relationship store file, neostore.rela
tionshipstore.db . Like the node store, the relationship store consists of fixed-sized
records—in this case each record is 33 bytes long. Each relationship record contains the
IDs of the nodes at the start and end of the relationship, a pointer to the relationship
type (which is stored in the relationship type store), and pointers for the next and pre‐
vious relationship records for each of the start and end nodes. These last pointers are
part of what is often called the relationship chain .