On-Disk Storage

Neo4j's classic format (simplified):

nodes.db:

• Fixed-size record per node (15 bytes).
• Pointers to: first relationship, first property, label bitmap.

relationships.db:

• Fixed-size record per relationship (34 bytes).
• Pointers to: source node, target node, prev rel of source, next rel of source, prev rel of target, next rel of target, type, first property.

properties.db:

• Fixed-size record + variable-size value (in a separate file for large values).

Why fixed records? Direct addressing: record N is at offset N * record_size. No B-tree lookup needed for ID-based access.

Trade-off: deletes leave gaps. Compaction reuses or shrinks.

Index-free adjacency:

• Traversing an edge = pointer dereference.
• 5-hop traversal = 5 pointer dereferences.
• Compare to SQL: 5 B-tree lookups (4-5 ops each = 20-25 ops).

Modern variants:

• LSM-based (DGraph): pull from RocksDB/Badger.
• Cassandra-based (JanusGraph): wide rows for adjacency.
• In-memory (Memgraph, TigerGraph): every node + edge in RAM.

Trade-offs:

• In-memory: fastest queries, hardware-bound dataset size.
• LSM: scales with disk; higher latency.
• Custom record-oriented (Neo4j): middle ground.

Sharding for scale:

• By node ID range (simple but hot spots).
• By community (graph partitioning algorithms — METIS, Louvain).
• By label (sometimes).

Cross-shard queries are expensive. Many graph DBs cap dataset to single-machine size for performance.

Replication:

• Read replicas (eventually consistent).
• Write to leader, replicate WAL.

Backup:

• Filesystem snapshot (LVM, ZFS).
• Or app-level: serialize all nodes + edges + properties.