一直以為neo4j是使用十字連結清單(Orthogonal List)來存儲圖資料的,後面跟蹤源代碼發現并不是,因為
十字連結清單是:
結點中單獨存放“入邊”、“出邊”兩個指針分别指向結點的第一個入邊出邊(注意這裡的“第一個”指有順序可以按結點的實體id來排列,因為這會影響到後續邊上的“同弧頭”的指向)
邊上兩個指針域名,一個指向現該邊同終點的下一條邊,一個指向與該邊同起點的下一條邊
而neo4j中的結構更像是鄰接表, 其并沒有把入邊,出邊分開存儲,它在結點中隻放了一個指向第一個關系的指針,順着這第一個關系周遊連結清單得到該結點的所有關系,如果需要指定得到某個結點的入度或出度,需要周遊所有關系通過判斷邊上的起點終點是否和中心結點相等來判斷方向:
代碼如下(org\neo4j\kernel\impl\api\store\StoreNodeRelationshipCursor.java):
public boolean next()
{
while ( relationshipId != NO_NEXT_RELATIONSHIP.intValue() )
{
relationshipRecordCursor.next( relationshipId, relationshipRecord, FORCE );
// If we end up on a relationship record that isn't in use there's a good chance there
// have been a concurrent transaction deleting this record under our feet. Since we don't
// reuse relationship ids we can still trust the pointers in this unused record and try
// to chase a used record down the line.
try
{
// Direction check
if ( relationshipRecord.inUse() )
{
if ( direction != Direction.BOTH )
{
switch ( direction )
{
case INCOMING:
{
if ( relationshipRecord.getSecondNode() != fromNodeId )
{
continue;
}
break;
}
case OUTGOING:
{
if ( relationshipRecord.getFirstNode() != fromNodeId )
{
continue;
}
break;
}
default:
throw new IllegalStateException( "Unknown direction: " + direction );
}
}
// Type check
if ( !allowedTypes.test( relationshipRecord.getType() ) )
{
continue;
}
return true;
}
}
finally
{
// Pick next relationship
if ( relationshipRecord.getFirstNode() == fromNodeId )
{
relationshipId = relationshipRecord.getFirstNextRel();
}
else if ( relationshipRecord.getSecondNode() == fromNodeId )
{
relationshipId = relationshipRecord.getSecondNextRel();
}
else
{
throw new InvalidRecordException(
"While loading relationships for Node[" + fromNodeId + "] a Relationship[" +
relationshipRecord.getId() + "] was encountered that had startNode:" + " " +
relationshipRecord.getFirstNode() + " and endNode: " +
relationshipRecord.getSecondNode() + ", i.e. which had neither start nor end node " +
"as the node we're loading relationships for" );
}
// If there are no more relationships, and this is from a dense node, then
// traverse the next group
if ( relationshipId == NO_NEXT_RELATIONSHIP.intValue() && isDense )
{
relationshipId = nextChainStart();
}
}
}
return false;
}