NoSQL学习——图数据库Neo4j（三）图存储、索引与性能

Kelmory 11/24/2021 NoSQLNeo4j

# 图的存储

在之前的一章中，我们看到了其他数据库如RDBMS和MongoDB对图的存储方式。这些存储方式尽管能够使得相关的数据库处理一定的图数据，但当面对深度遍历和更多的结点与边时，其性能就会存在下降的问题。因此，Neo4j采用了一些与这些数据库完全不同的存储模型，专用于图的存储。这种存储方式的另一个优点是减少了每个结点和边的存储空间大小。

在Neo4j的存储中，结点之间的关系存储得到了原生的支持，因此结点之间的索引是通过预先存储的双向连接实现的。由于这一特性，这种组织方式比全局索引更加节省空间，且可通过并行的方式进行查询。

如同其他数据库系统一样，Neo4j的图数据存储在磁盘的文件上，其中，结点、关系、属性、标签、类型等都有自己的存储文件和系统指定的id，这些数据有着固定的长度。结构和属性类的数据是分开存储的，以此减少遍历图的时候扫描的数据。

# 结点的存储

首先查看结点的存储文件neostore.nodestore.db，其ID存储在neostore.nodestore.db.id文件中。这个文件中存储着所有结点的数据，每个结点使用15字节存储，因此计算文件内node的偏移的方法是： $offset = 15 * node_id$ 。15字节结构如下所示

inUse nextRelId nextPropId labels extra
|1B  |4B       |4B        |5B    |1B   |
0    1         5          9     14     15

inUse表示该节点是否在用（与部分动态的删除有关）；nextRelId表示d第一个与结点相关的关系的ID，可以配合对应的offset寻找关系的数据位置；nextPropId表示第一个属性的Id，在此之后在属性的文件内检索其他属性即可；labels是一个5字节的区域，用于查找neostore.nodestore.labels及其id的对应文件。至此，我们可以看到，由于4Byte（1 word）的存储空间能够表示 $2^32$ 个值，这种组织方式能够适应非常大量的结点和关系存储。

# 关系的存储

关系的存储同样采用一个文件neostore.relationshipstore.db及其对应的id文件。与结点存储类似，边的存储使用34个字节为固定长度。其结构如下：

inUse firstNode secondNode relationshipType firstPrevRelId firstNextRelId secondPrevRelId secondNextRelId nextPropId firstInChainMarker
|1B  |4B       |4B        |4B              |4B            |4B            |4B             |4B             |4B        |1B                |
0    1         5          9                13             17             21              25              29         33                 34

可以看到，关系的存储相较于结点，主要复杂在有两组用于查询上一个+下一个关系的id，且需要关联两个节点的Id。与labels类似，关系的结构中存储了relationshipType用于分类关系。

在关系存储中，firstPrevRelId指的是关系的出度节点的上一个关系，secondPrevRelId则指的是关系的入度节点的上一个关系。因此，使用关系存储可以保证遍历到两个方向上的结点的所有关系。

# 属性、标签与类型存储

属性存储同样使用了固定尺寸记录，一条简单属性只需要通过neostore.propertystore.db内部存储，复杂的属性如长字符串和数组类则可能存储在neostore.propertystore.db.arrays内部。

标签的存储位于neostore.nodestore.labels及相关的id文件内。与之相似的，关系的类型存储在neostore.relationshiptypestore.db及相关的id、names为后缀的文件内。

# 执行与性能解析

类似RDBMS，Neo4j的执行也是通过执行计划器（query planner）将查询转化为实际执行的指令树。在指令树中，起点是指令树的叶子节点（用于从存储引擎中获取数据），通过执行剩余阶段（过滤、扩展、组合灯）逐层将叶子节点合并，得到最后的结果。执行计划的选出是通过数据库维护的统计数据完成的，通过比较不同标签的节点数量、关系的类型、索引的选择和结点的起止位置来选取。

在实际执行中，通过在查询语句前加入PROFILE来查看执行计划。Neo4j会返回类似Spark的按阶段解释，在每个阶段中只包含一个操作，并伴随有一些统计数据，包括Rows（操作扫描的数据记录数）、EstimatedRows（根据统计得出的预估数量）、DBHits（在需要直接读写磁盘的操作中，操作磁盘上记录的数量，包括修改结点或边或标签或关系、删除节点、获取等等）。

查询的执行通常从一个或一组结点开始，除非指明关系（边）的id。在节点查询时会尽量根据标签、已有的索引减少扫描的记录数量。有了profiler的帮助，我们就可以比较获得相同结果的不同查询之间的性能差距。通常，在更早的阶段组合进行MATCH的查询会有更好的性能，因为能够在更早的阶段过滤掉无关数据。

# 索引

下面对Neo4j的索引做简要说明：

索引的建立方法是执行：CREATE INDEX ON:<label>(<property>)，删除方法是：DROP INDEX ON:<label>(<property>)。
索引可以建立在单一的或组合的属性上，其行为与关系型数据库类似。

# 事务

由于采用相似的文件存储和索引，Neo4j支持类似RDBMS的ACID事务。Neo4j主要通过锁的方法来确保事务的原子性、独立性和一致性；在持久性上，通过写前日志（Write Ahead Logging），包括重做日志和取消日志，来增强持久性。由于采用了日志系统，Neo4j的错误恢复是通过操作状态机实现的，即通过日志中的操作和初始数据（如快照点）恢复数据。

Kelforest

Choose mode