1.7.2　Neo4j底层存储结构

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

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

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

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

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

节点和关系分别采用固定长度存储，图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）。动态存储记录是可以扩展的，如果一个属性长到一条动态存储记录仍然无法完全容纳时，可以申请多个动态存储记录以便在逻辑上进行连接。