How does Neo4j Traverse a graph using relationship ID's in nodestore file

0
votes

Something has confused me a lot I was Wondering If you could help me with this please According to Neo4j graph database book, there are 4 bytes in node store file contains the ID of the nodes relationship . If the node has 100 relationship (and all of them are the node's first relationship in the relationship chain) how does neo4j understand which id to choose??? for example I wrote Match(a:user{Name:'a')-[r:Has-skill]->(b:skill)

Imagine The user node has lot's of relationship but we are interested in [has_skill] relationship how does neo4j understand which id in related to this relationship?

1
neo4jgraph-databasesdatamodel

1 Answers

0
votes

The relationship chain that you are talking about is not the same as a "path". A node does not have more than one relationship that is the first in the chain.

The chain of relationships is a doubly-linked list that contains that Node's relationships. Given that Neo4J already has found the first user in the pattern, it will perform the following steps (or something similar):

  1. Follow the pointer from the node record to the first element of the linked list that contains all of that node's relationships (this first element is the "first relationship in the chain").
  2. For each element of the linked list:
    • Check if matches the criteria for the searched-for relationship (here, it would be that it has the type HAS_SKILL).
    • If it does match the criteria, the relationship is kept for future following; if it does not match, it is discarded.
    • Follow the pointer to the next element in the relationship linked-list (in the "chain"); if at the last element already, exit the loop.
  3. For each of the relationships retrieved by scanning the linked list, follow them to the node they point to and continue evaluating the pattern.

The actual algorithm may differ slightly; e.g. it may use depth-first traversal instead of breadth-first, or it may be optimized in a different way, but the end result is the same.

From Graph Databases, 2nd Edition by Ian Robinson, Jim Webber and Emil Eifrem, page 154:

To find a relationship for a node, we follow that node’s relationship pointer to its first relationship (the LIKES relation‐ ship in this example). From here, we then follow the doubly linked list of relation‐ ships for that particular node (that is, either the start node doubly linked list, or the end node doubly linked list) until we find the relationship we’re interested in.

Finally, @InverseFalcon points out that this will be implemented differently for densely-related nodes, by their estimate at around 50+ relationships. At this point, a slightly different structure is used which groups by types and direction so the cost to search through is reduced.