本文将阐述Neo4j的数据存储模型以及二进制存储文件的格式，所述内容基于**Neo4j 3.5.13 Community**版本。

存储模型

基础概念

图数据库有两个Native特性：

  • Native Storage：区别在于底层的数据存储格式是否Graph-like，简而言之即以图的形式存储图，Native Storage通过将节点和关系写入到“相近”的位置来保证高效地存储。使用外部存储时认为是Non-Native，比如Titan使用HBase、Cassandra等其他DB来存储数据。
  • Native Processing：Native与Non-Native的重要区别在于存储是否具有 index-free adjacency属性。所谓的index-free adjacency是指每个节点直接指向关联的节点，即每个节点都有自己的局部索引，这样相较于全局索引更加快速高效。

Neo4j属于Native Graph，因此在了解存储结构时可以发现节点和关系的数据记录均包含了邻接信息。

模型图解

上图表现了各种存储文件是如何在磁盘上交互的。每个节点（Node）记录包含了它的第一个属性的ID以及关系链中的第一个边（Relationship）的ID。在读取节点的属性时，我们可以沿以指向第一个属性的指针为起始的单向链表结构进行遍历。在查询节点相关的边时，我们可以从节点中指向第一条边（如上图中的”LIKE”）的指针开始，获取到第一条边后我们可以沿着指定节点（起始节点或终止节点）相关的双向边链表进行遍历直到找到我们感兴趣的边。找到指定的边记录后，我们可以使用与节点属性相同的单向链接列表结构来读取边的属性（如果有），或者我们也可以检查它通过ID关联的起始节点和终止节点记录，这些ID与节点记录长度相乘可以快速得出每个节点在存储文件中的偏移量。

存储文件

Neo4j的存储文件默认情况下位于NEO_HOME/data/databases/graph.db目录下，存储文件将在第一次运行Neo4j时生成。这里仅讨论与数据存储相关的内容，不含索引、事务、日志以及其他辅助内容。

基本存储格式

Neo4j的各个存储文件在形式上基本保持一致，可以分为如下三大基本类别：

  • ID类型

    基本上每个存储文件都会伴随一个以.id为结尾的ID文件。这是由于Neo4j的落盘数据单元记录（Record）都是定长的，记录的id与记录所在文件的位置（偏移量）成正比（这样能够通过id直接获取到数据），而存储时会分配一整块数据（多余以0填充），同时考虑数据的删除情况，为了加速ID的分配并且充分利用存储空间，ID文件内存储了当前下一个可用的最大ID以及可以重用的ID列表。ID文件不是必须的，在启动时会从数据文件中重新计算出最大ID。

  • 定长记录

    这种存储文件每一个Record的长度是固定的（定死，无法更改），并且一个Record对应一份内容。通常它们不包含头部信息，从0开始记录第一个Record，并且每个Record通常没有Header。

  • 动态记录

    动态的存储文件每一个Record的长度也是固定的，但是通常可以进行配置更改，多个Record对应一份内容，同一份内容的Record以链表指针形式关联。通常它们会将第一个记录作为文件的头部信息，存储相关元数据（通常是Record的长度），并且每个Record会有8byte长度的Header。目前有三种动态记录：

    • DynamicArrayStore：存储数组（基本类型、String、Geometries）
    • DynamicStringStore：存储字符串
    • SchemaStore：存储Schema

文件对应的存储内容

文件名 存储格式 存储的内容
neostore 定长记录 数据存储的元信息
neostore.id ID 类型
neostore.labeltokenstore 定长记录 标签自身以及标签名称首记录id
neostore.labeltokenstore.id ID 类型
neostore.labeltokenstore.db.names 动态记录 标签名称字符串
neostore.labeltokenstore.db.names.id ID 类型
neostore.nodestore.db 定长记录 节点数据
neostore.nodestore.db.id ID类型
neostore.nodestore.db.labels 动态记录 无法内联的节点标签id数组
neostore.nodestore.db.labels.id ID 类型
neostore.propertystore.db 定长记录 属性数据
neostore.propertystore.db.id ID 类型
neostore.propertystore.db.index 定长记录 属性名自身以及属性名字符首记录id
neostore.propertystore.db.index.id ID类型
neostore.propertystore.db.index.keys 动态记录 属性名称字符串
neostore.propertystore.db.index.keys.id ID类型
neostore.propertystore.db.strings 动态记录 无法内联的字符串型属性值
neostore.propertystore.db.strings.id ID类型
neostore.propertystore.db.arrays 动态记录 无法内联的数组型属性值
neostore.propertystore.db.arrays.id ID类型
neostore.relationshipstore.db 定长记录 边数据
neostore.relationshipstore.db.id ID类型
neostore.relationshiptypestore.db 定长记录 边类型名自身以及边类型名字符首记录id
neostore.relationshiptypestore.db.id ID类型
neostore.relationshiptypestore.db.names 动态记录 边类型名称字符串
neostore.relationshiptypestore.db.names.id ID类型
neostore.relationshipgroupstore.db 定长记录 超级节点的边分组信息
neostore.relationshipgroupstore.db.id ID类型
neostore.schemastore.db 动态类型 Schema信息，如索引、约束
neostore.schemastore.db.id ID类型

核心内容的存储

下面将针对各个核心概念对应的存储文件进行具体的介绍。

注意本文在论述时所描述的第一个Bit是从大端开始，例如0x80 [1 0 0 0 , 0 0 0 0] 的第一个Bit为1.

元信息的存储

首先通过结构最简单的元信息存储入手。元信息的存储文件名为neostore，格式为定长记录，它也有一个对应的ID文件，但它并没有实际的用途，因为里面各项内容是固定的。每个Record的结构如下：

  • inUse（1 byte）：标识该record是否可用
  • data（8 bytes）：record的数据

目前一共有15条record如下所示：

  1. Creation time
  2. Random number for store id
  3. Current log version
  4. Last committed transaction id
  5. Store format version
  6. First property record containing graph properties
  7. Last committed transaction containing constraint changes
  8. Transaction id most recent upgrade was performed at
  9. Time of last upgrade
  10. Checksum of last committed transaction
  11. Checksum of transaction id the most recent upgrade was performed at
  12. Log version where the last transaction commit entry has been written into
  13. Byte offset in the log file where the last transaction commit entry has been written into
  14. Commit time timestamp for last committed transaction
  15. Commit timestamp of transaction the most recent upgrade was performed at

字符串存储示例

节点的Label、边的类型均是字符串，同时字符串也是最常见的属性格式，因此先介绍一下长字符串的存储，同时也能够对动态类型有进一步的了解。单个Record的内容如下所示：

  • high（1 byte）：
    • [ x _ _ _ , _ _ _ _ ] 第1个bit标记是否是起始记录（0表示起始）
    • [ _ _ _ x , _ _ _ _ ] 第4个bit标记是否可用
    • [ _ _ _ _ , x x x x ] 第5-8个bit为next_block_id的高4位
  • data_size（3 bytes）：record中有效数据的长度
  • next_block_id（4 bytes）：下一条记录的id的低位，加上高位中的4个bit，block_id一共36bit
  • data：存储数据

前8个bytes作为一条Record的Header，这个结构对于所有的动态类型数据来说都是一致的。对于String来说，通常在别的记录中获取头部Record的id之后，根据链表指针遍历获取所有相关Records，拼接所有Records中的data部分然后用UTF-8编码即可得到存储的String值。

需要注意存储文件可能有Header，每一条Record也可能有Header，所有data拼接后还可能有Header（例如存储数组时，第一条Record中data的前几个bit存储了数组的元信息），不要混淆了。

节点数据的存储

节点数据的存储是由主存储文件、label相关存储文件以及属性相关存储文件来配合完成的。属性的存储将在最后统一说明。

主存储

节点主存储文件为neostore.nodestore.db，定长类型的记录文件，每一个Record代表一个节点，Record内容如下所示：

  • high（1 byte）：
    • [ x x x x , _ _ _ _ ] 第1-4个bit为next_prop_id的高4位
    • [ _ _ _ _ , x x x _ ] 第5-7个bit为next_rel_id的高3位
    • [ _ _ _ _ , _ _ _ x ] 第8个bit标识是否可用
  • next_rel_id（4 bytes）：节点关联的第一条边的id的低位，加上高位中的3个bit，rel_id一共35个bit
  • next_prop_id（4 bytes）：节点关联的第一个属性的id的低位，加上高位中的4个bit，prop_id一共36个bit
  • labels（5 bytes）：存储label信息，前4个byte为低位，最后一个1个byte为高位，需要进行移位计算
  • extra（1 byte）：[ _ _ _ _ , _ _ _ x ] 目前只用到最后一个bit，用于标识是否dense（超级节点）

可以发现边的id长度为35bit，也就是340亿左右，属性的id长度为36bit约680亿，这是边和属性数量的上限（好像商用版本没有这个限制？）。

存储label信息的5个byte在移位取得真实值后，第1个bit标识了是否是内联。如果是内联的则第2-4个bit表示label的数量，剩下的36个bit使用除法均分给每个label，代表label的id；如果不是内联的，则低位的36个bit表示第一个动态label记录的id。

label存储

label的存储涉及3个文件，对于label自身来说它是一个Token（id + String），类似的还有属性的key和边的类型，Token的存储基本保持一致：1个record长度为5 bytes的定长类型存储文件存储标识自己以及字符串表达的头记录ID（36 bits），加上1个动态类型存储字符串，对于label来说它们两个分别是neostore.labeltokenstore.db和neostore.labeltokenstore.db.names。

此外由于Node可以包含多个label，在label较多的情况下需要存储label id的数组，即neostore.nodestore.db.labels，它是一个DynamicArrayStore。

边数据的存储

边存储由主存储文件、边分类相关存储文件、边类型相关存储文件（Token类型，见前文对Token类型存储的描述）以及边属性的存储。

主存储

边的主存储文件为neostore.relationshipstore.db，定长类型的记录文件，每一个Record代表一条边，Record内容如下所示：

  • high（1 byte）：

    • [ x x x x , _ _ _ _ ] 第1-4个bit为next_prop_id的高4位
    • [ _ _ _ _ , x x x _ ] 第5-7个bit为first_node_id的高3位
    • [ _ _ _ _ , _ _ _ x ] 第8个bit标识是否可用

  • first_node_id（4 bytes）：边关联的第一个节点id的低位，加上high中的3个bit，node_id一共35个bit

  • second_node_id（4 bytes）：边关联的第二个节点id的低位，加上mid中的3个bit，node_id一共35个bit

  • mid（2 bytes）：

    • [ _ x x x , _ _ _ _ , _ _ _ _ , _ _ _ _ ]：第2-4个bit为second_node_id的高3位
    • [ _ _ _ _ , x x x _ , _ _ _ _ , _ _ _ _ ]：第5-7个bit为first prev relationship id的高3位
    • [ _ _ _ _ , _ _ _ x , x x _ _ , _ _ _ _ ]：第8-10个bit为first next relationship id的高3位
    • [ _ _ _ _ , _ _ _ _ , _ _ x x , x _ _ _ ]：第11-13个bit为second prev relationship id的高3位
    • [ _ _ _ _ , _ _ _ _ , _ _ _ _ , _ x x x ]：第14-16个bit为second next relationship id的高3位

  • type（2 bytes）：边的类型id

  • first prev relationship id（4 bytes）：第一个节点相关的前一条边id的低位，加上mid中的3个bit，rel_id一共35个bit

  • first next relationship id（4 bytes）：第一个节点相关的后一条边id的低位，加上mid中的3个bit，rel_id一共35个bit

  • second prev relationship id（4 bytes）：第二个节点相关的前一条边id的低位，加上mid中的3个bit，rel_id一共35个bit

  • second next relationship id（4 bytes）：第二个节点相关的后一条边id的低位，加上mid中的3个bit，rel_id一共35个bit

  • next_prop_id：边关联的第一个属性的id的低位，加上high中的4个bit，prop_id一共36个bit

  • first-in-chain-markers（1 byte）：

    • [ _ _ _ _ , _ _ x _ ] ：第7个bit标识是否第一个节点的第一条边
    • [ _ _ _ _ , _ _ _ x ] ：第8个bit标识是否第二个节点的第一条边

    注：之所以存标识而不用prev id等于空值来判断是否是第一条边是因为第一条边的prev id区域存储的其实是整个链表结构的长度

边的存储格式与之前所述的存储模型关联性很强，可以看到在边中存储了两端节点的id以及两条双向链表。

group存储

由于链表这种数据结构当节点关联的边很多时容易成为性能瓶颈（超级节点）， 因此关联的边超过一个阈值时，neo4j会对边进行分组以提高性能，分组的变换示意图如下所示：

分组的依据是边的类型，每个Group指向3条链表（IN、OUT、LOOP，LOOP表示指向自己的边），这样在查询指定类型、指定方向的边时可以缩短遍历的路径。分组存储的文件为neostore.relationshipgroupstore.db，它存储的内容是group的信息，边的存储结构并不改变，只是相关链表的指向被修改。Group record的内容如下所示：

  • head（1 byte）：
    • [ _ x x x , _ _ _ _ ] ：第2-4个bit为first_out_id的高3位
    • [ _ _ _ _ , x x x _ ] ：第5-7个bit为next_id的高3位
    • [ _ _ _ _ , _ _ _ x ] ：第8个bit标识是否可用
  • high（1 byte）：
    • [ _ x x x , _ _ _ _ ] ：第2-4个bit为first_loop_id的高3位
    • [ _ _ _ _ , x x x _ ] ：第5-7个bit为first_in_id的高3位
  • type（2 bytes）：边类型id
  • next_id（4 bytes）：同节点下一个group的id的低位，加上head中的3bit一共35bit
  • first_out_id（4 bytes）：Group中所属节点第一条指出边id的低位
  • first_in_id（4 bytes）：Group中所属节点第一条指入边id的低位
  • first_loop_id（4 bytes）：Group中所属节点第一条自指向边id的低位
  • owning node（5 bytes）：所属节点的id，最后一个byte为高位，需要移位计算出真实值

属性的存储

属性的存储由主存储文件、属性key相关存储文件（Token类型，见前文对Token类型存储的描述）以及存储属性值中较长的字符、数组的2个动态记录格式文件配合完成。长字符串值存储文件名为neostore.propertystore.db.strings，数组值存储文件名为neostore.propertystore.db.arrays，动态格式的存储见前文字符串存储示例。

属性的主存储文件名为neostore.propertystore.db，属性的Record的长度是定长记录格式中最长的，达到41 bytes，Record内容如下所示：

  • high（1 byte）：
    • [ x x x x , _ _ _ _ ] ：第1-4个bit为prev_id的高4位
    • [ _ _ _ _ , x x x x ] ：第5-8个bit为next_id的高4位
  • next_id（4 bytes）：节点或边的下一条属性记录id的低位，加上高位中的4个bit，property_id一共36bit
  • prev_id（4 bytes）：节点或边的上一条属性记录id的低位，加上高位中的4个bit，property_id一共36bit
  • payload（8 bytes x 4）：4个存储数据的payload

不同类型的属性会有不同的格式、占用不同的payload个数，一个record中也可能存储多个属性。单个属性的第一个payload格式为：

  • […] […] […] […] [ _ _ _ _ , x x x x ] [ _ _ _ _ , _ _ _ _ ] [ _ _ _ _ , _ _ _ _ ] [ _ _ _ _ , _ _ _ _ ]：标识属性的类型
  • […] […] […] […] [ _ _ _ _ , _ _ _ _ ] [ x x x x , x x x x ] [ x x x x , x x x x ] [ x x x x , x x x x ]：标识属性key的id

目前支持的属性类型有17种：

  • 基本类型：BOOL、BYTE、SHORT、CHAR、INT、LONG、FLOAT、DOUBLE
  • STRING、ARRAY两种类型根据长度可能直接存储（inline），也可能指向动态存储的记录
  • 空间几何类型：POINT
  • 时间类型：DATE、LOCALTIME、LOCALDATETIME、TIME、DATETIME、DURATION（Duration是neo4j自己实现的而不是java 8的Duration）

每种属性在payload中如何存储请参考org.neo4j.kernel.impl.store.PropertyStore的javadoc。