1.7.3　Neo4j的遍历方式

Neo4j每个节点记录都包含一个指向该节点的第一个属性的指针和联系链中第一个联系的指针。要读取一个节点的属性，从指向第一个属性的指针开始，遍历整个单向链表结构。要找到一个节点的关系，从指向的第一个关系开始，遍历整个双向链表，直到找到了感兴趣的关系。一旦找到了感兴趣关系的记录，我们就可以与使用和查找节点属性一样的方法查找关系的属性（如果该关系存在属性）。我们也可以很方便地获取起始节点和结束节点的ID，利用节点ID乘以节点记录的大小（9字节），就可以立即算出每个节点在节点存储文件中的具体位置，所需的复杂度仅为O(1)。

图1-21所示就是节点、关系、属性在Neo4j中的物理表现方式。图中直接看起来可能不是那么直观，可以想象关系是属于两个节点的，但是一个关系也不应该在记录中出现两次，这样会造成内存的浪费。因此两个双向链表之间会有指针，一个是起始节点可见的列表关系，另一个是结束节点可见的列表关系。每一个列表都是双向链表，因此我们可以在任何一个方向上进行快速遍历和高效地插入和删除。

图1-21　在Neo4j中的物理存储方式

下面通过一个例子来讲解Neo4j遍历关系和节点的详细过程。假如在Neo4j中存储了A、B、C、D、E 5个节点和R1、R2、R3、R4、R5、R6、R7 7个关系，它们之间的关系如图1-22所示。

图1-22　Neo4j中的一个关系结构示意图

假如要遍历图中节点B的所有关系，只需要向NODEB-NEXT方向遍历，直到指向NULL为止，可以从图1-23中看出节点B的所有关系为R1、R3、R4、R5。

图1-23　Neo4j中的图遍历方式

通过固定大小的存储记录和指针ID，只要跟随指针就可以简单地实现遍历并且高速执行。要遍历一个节点到另一个节点的特定关系，在Neo4j中只需要遍历几个指针，然后执行一些低成本的ID计算即可，这相较于全局索引的时间复杂度要低很多，这就是Neo4j实现高效遍历的秘密。

●　从一个给定节点定位关系链中第一个关系的位置，可以通过计算它在关系存储的偏移量来获得。跟获得节点存储位置的方法一样，使用关系ID乘以关系记录的固定大小，即可找到关系在存储文件中的正确位置。

●　在关系记录中，搜索第二个字段可以找到第二个节点的ID。用节点记录大小乘以节点ID可以得到节点在存储中的正确位置。