neo4j/neo4j — pull request #1907 by tinwelint (2014-02-04 21:00:43+00:00)
Title: Splits relationship chains by type and direction

Changes how relationships for a node are stored on disk. Node and
relationship records are virtually untouched, and a new type of records
(and store) sits in between a node and its relationships acting as a
node-centric index for type and direction of the relationships.

Previously the logical layout has been that a node has one long chain of
relationships connected to it, where relationships of all types and
directions were mixed in the same chain. Loading relationships of a
particular type and direction could not be made efficiently since the
whole chain had to be loaded. Simplified like this:

NODE->REL1->REL2->REL3...

This commit introduces RelationshipGroup(Store/Record) which sits in
between node and its relationships like so:

NODE->GROUP_A->GROUP_B->GROUP_C->...
/ \ | |
OUT IN OUT IN
/ | | |
REL1 REL2 REL3 REL7
| | |
v v v
REL4 REL6 REL8
| | |
v v v
... ... ...

which removes to need to load irrelevant relationships when knowing their
type and or direction. Furthermore, backpointers on all relationship
records that are first in any chain are used to store the number of
relationships in that chain, allowing for O(1) counting of relationships,
even based on type and direction.

Nodes with few relationships will bypass the relationship group index
and instead switch on a certain number of relationships. This to remove the
overhead of the relationship group records for a small number of
relationships. The dense node threshold is configurable and defaults to 50.

This commit also bumps the store format to 0.A.2 and requires a store
migration, which will happen automatically if configuration settings to
allow it are in place.