精通Neo4j
上QQ阅读APP看书,第一时间看更新

1.7.2 Neo4j底层存储结构

如果说免索引邻接是图数据库实现高效遍历的关键,那么免索引邻接的实现机制就是Neo4j底层存储结构设计的关键。能够支持高效的、本地化的图存储以及支持任意图算法的快速遍历,是使用图数据库的重要原因。本节将深入探索Neo4j的底层存储结构。

从宏观角度来说,Neo4j中仅仅只有两种数据类型:

(1)节点(Node):节点类似于E-R图中的实体(Entity)。每一个实体可以有零个或多个属性(Property),这些属性以键值对的形式存在。属性没有特殊的类别要求,同时每个节点还具有相应的标签(Label),用来区分不同类型的节点。

(2)关系(Relationship):关系也类似于E-R图中的关系(Relationship)。一个关系有起始节点和终止节点。另外,与节点一样,关系也能够有自己的属性和标签。

节点和关系在Neo4j中的示意图如图1-18所示。

图1-18 Neo4j基本存储结构示意图

节点和关系分别采用固定长度存储,图1-19为Neo4j节点和关系存储文件的物理结构。

图1-19 Neo4j节点和关系存储文件的物理结构

节点存储文件用来存储节点的记录,文件名为neostore.nodestore.db。节点记录的长度为固定大小,如上图所示,每个节点记录的长度为9字节。格式为Node:inUse+nextRelId+ nextPropId。

● inUse:1表示该节点被正常使用,0表示该节点被删除。

● nextRelId:该节点的下一个关系ID。

● nextPropId:该节点的下一个属性ID。

我们可以将neostore.nodestore.db中存储的记录看作是如下方式:

Node[12,used=true,rel=11,prop=22]采用固定字节长度的记录,可以快速地查询到存储文件中的节点。如果有一个ID为100的节点,我们知道该记录在存储文件中的第900字节。基于这种查询方式,数据库可以直接计算一个记录的位置,其成本仅为O(1),而不是执行成本为O(log(n))的搜索。

关系存储文件用来存储关系的记录,文件名为neostore.relationshipstore.db。就像节点的存储一样,关系存储区的记录大小也是固定的。格式为:Relationship:inUse+firstNode+secondNode+relType+firstPrevRelId+firstNextRelId+secondPrevRelId+secondNextRelId+nextPropId。

● inUse,nextPropId:作用同上。

● firstNode:当前关系的起始节点。

● secondNode:当前关系的终止节点。

● relType:关系的类型。

● firstPrevRelId & firstNextRelId:起始节点的前一个和后一个关系的ID。

● secondPrevRelId & secondNextRelId:终止节点的前一个和后一个关系ID。

同样的,neostore.relationshipstore.db中存储的记录也可以看作是如下的方式:

Neo4j中有一个.id文件用来保持对未使用记录的跟踪,用来回收未使用的记录占用的空间。节点和关系的存储文件只关心图的基本存储结构而不是属性数据。这两种记录都使用固定大小的记录,以便存储文件内的任何记录都可以根据ID快速地计算出来。这些都是强调Neo4j高性能遍历的关键设计决策。节点记录和关系记录都是相当轻量级的:只由几个指向联系和属性列表的指针构成。

图1-20所示是Neo4j中的其他常见的基本存储类型,需要注意的是属性的存储,属性记录的物理存储放置在neostore.propertystore.db文件中。与节点和关系的存储记录一样,属性的存储记录也是固定长度。每个属性记录包含4个属性块和属性链中下一个属性的ID。属性链是单向链表,而关系链是双向链表。一个属性记录中可以包含任何Java虚拟机(JVM)支持的基本数据类型、字符串、基于基本类型的数组以及属性索引文件(neostore.propertystore.db.index)。属性索引文件主要用于存储属性的名称,属性索引的值部分存储的是指向动态内存的记录或者内联值,短字符串和短数组会直接内联在属性存储记录中。当长度超过属性记录中的propBlock长度限制之后,会单独存储在其他的动态存储文件中。

Neo4j中有两种动态存储:动态字符串存储(neostore.propertystore.db.strings)和动态数组存储(neostore.propertystore.db.arrays)。动态存储记录是可以扩展的,如果一个属性长到一条动态存储记录仍然无法完全容纳时,可以申请多个动态存储记录以便在逻辑上进行连接。

图1-20 Neo4j其他常见的物理结构