1.6 Neo4j的体系结构

本节将从数据库的底层设计揭开Neo4j数据库的神秘面纱，了解Neo4j为了实现图的存储所采用什么样的体系结构，揭秘为什么图数据库基于复杂联系的查询相比关系型数据库要更快。

Neo4j最初的设计动机是为了更好地描述实体之间的联系。现实生活中，每个实体都与周围的其他实体有着千丝万缕的关系，这些关系里存在着大量的潜在信息。但是传统的关系型数据库更加注重刻画实体内部的属性，实体与实体之间的关系主要通过外键来实现。因此，在查询一个实体的关系时需要join操作，特别是深层次的关系查询需要大量的join操作，而join操作通常又非常耗时。随着现实世界中关系数据的急剧增加，导致关系型数据库已经逐渐地难以承载查询海量数据深层次关系需要大量数据库表操作带来的运算复杂性，Neo4j在这样的情况下应运而生。

1.6.1 免索引邻接

Neo4j有一个重要的特点，就是用来保证关系查询的速度，即免索引邻接属性，数据库中的每个节点都会维护与它相邻节点的引用。因此每个节点都相当于与它相邻节点的微索引，这比使用全局索引的代价要小得多。这就意味着查询时间和图的整体规模无关，只与它附近节点的数量成正比。在关系型数据库中使用全局索引连接各个节点，这些索引对每个遍历都会增加一个中间层，因此会导致非常大的计算成本。而免索引邻接为图数据库提供了快速、高效的图遍历能力。

对比图1-14和图1-15，可以明显地看出关系型数据库与Neo4j在查找关系时的区别。

图1-14 RDBMS中关系查询示意图

图1-15 Neo4j中关系查询示意图

图1-14展示了在RDBMS（关系型数据库）中的查询方式。要查找Alice所购买的东西，首先要执行关系表的索引查询，时间成本为O(log(n)),n 为索引表的长度。这对于偶尔的浅层次查询是可以接受的，但是当查询的层次变深或者是执行反向查询时代价将会变得不可接受了。如果相较于查询Alice购买的东西，要查询某件商品被哪些人购买了（推荐引擎中常用的一个场景），将不得不使用暴力方法来遍历整个索引，时间复杂度则将增长到O(n)。除非我们再建立一个从商品到用户的索引表，但是该方法将会占用许多额外空间，并且使索引变得难以维护。

如果我们再考虑一个更复杂的场景，Alice购买过的商品被哪些人购买过（推荐引擎中查找有共同爱好的人），找到Alice购买过的商品的时间成本为O(log(n))，找到每个商品被哪些人购买的时间成本为O(n)，假如Alice购买过m（m远小于n）个商品，那么总的时间复杂度即为O(mnlog(n))。即使再建立一个方向索引表，时间复杂度也为O(mn)。

图1-15展示了在同样的场景下Neo4j的查询方式。使用免索引近邻机制，每个节点都有直接或间接指向其相邻节点的指针。要查找Alice买过的东西，只需要在Alice的关系链表中遍历，每次的遍历成本仅为O(1)。要查找一个商品被哪些人购买了，只要跟随指向该商品的关系来源即可，每次的遍历成本也是O(1)。更复杂的，要查找Alice购买过的东西被哪些人购买过，时间复杂度也仅为O(m)，其中m远小于n。这相较于RDBMS的时间复杂度还是占有绝对的优势。

免索引邻接针对RDBMS中的关系查询的两个缺点做了改进：

（1）免索引邻接使用遍历物理关系的方法查找，比起全局索引来说代价要小得多。查询一个索引一般的时间复杂度为O(log(n))，而遍历物理关系的时间复杂度仅为O(1)，至少对于Neo4j的存储结构来说是如此。

（2）当索引建立之后在试图反向遍历时，建立的索引就起不到作用了。我们有两个选择：对每个反向遍历的场景创建反向查找索引，或者使用原索引进行暴力搜索，而暴力搜索的时间复杂度为O(n)。这种代价相对于很多需要实时操作的场景来说是不可接受的。

利用免索引邻接机制，在图数据库上进行关系查询效率非常高，这种高效是建立在图数据库注重关系的架构设计之上的。

1.6.2 Neo4j底层存储结构

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

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

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

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

节点和关系在Neo4j中如图1-16所示。

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

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

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

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

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

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

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

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

    Node[0, used=true, rel=9, prop=-1]
    Node[1, used=true, rel=1, prop=0]
    Node[2, used=true, rel=2, prop=2]
    Node[3, used=true, rel=2, prop=4]
    Node[4, used=true, rel=4, prop=6]
    Node[5, used=true, rel=5, prop=8]
    Node[6, used=true, rel=5, prop=10]
    Node[7, used=true, rel=7, prop=12]
    Node[8, used=true, rel=8, prop=14]
    Node[9, used=true, rel=8, prop=16]
    Node[10, used=true, rel=10, prop=18]
    Node[11, used=true, rel=11, prop=20]

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+secondPrevRel Id+secondNextRelId+nextPropId。

● inUse, nextPropId：作用同上。

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

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

● relType：关系的类型。

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

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

同样的，“neostore.relationshipstore.db”中存储的记录也可以看作是如下的方式：

    Relationship[0, used=true, source=1, target=0, type=0, sPrev=1, sNext=-
    1, tPrev=3, tNext=-1, prop=1]
    Relationship[1, used=true, source=2, target=1, type=1, sPrev=2, sNext=-1, tPrev=-
    1, tNext=0, prop=3]
    Relationship[2, used=true, source=3, target=2, type=2, sPrev=-1, sNext=-1, tPrev=-
    1, tNext=1, prop=5]
    Relationship[3, used=true, source=4, target=0, type=0, sPrev=4, sNext=-
    1, tPrev=6, tNext=0, prop=7]
    Relationship[4, used=true, source=5, target=4, type=1, sPrev=5, sNext=-1, tPrev=-
    1, tNext=3, prop=9]
    Relationship[5, used=true, source=6, target=5, type=2, sPrev=-1, sNext=-1, tPrev=-
    1, tNext=4, prop=11]
    Relationship[6, used=true, source=7, target=0, type=0, sPrev=7, sNext=-
    1, tPrev=9, tNext=3, prop=13]
    Relationship[7, used=true, source=8, target=7, type=1, sPrev=8, sNext=-1, tPrev=-
    1, tNext=6, prop=15]
    Relationship[8, used=true, source=9, target=8, type=2, sPrev=-1, sNext=-1, tPrev=-
    1, tNext=7, prop=17]
    Relationship[9, used=true, source=10, target=0, type=0, sPrev=10, sNext=-1, tPrev=-
    1, tNext=6, prop=19]
    Relationship[10, used=true, source=11, target=10, type=1, sPrev=11, sNext=-
    1, tPrev=-1, tNext=9, prop=21]
    Relationship[11, used=true, source=12, target=11, type=2, sPrev=-1, sNext=-
    1, tPrev=-1, tNext=10, prop=23]

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

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

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

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

1.6.3 Neo4j的遍历方式

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

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

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

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

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

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

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

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

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

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

1.6.4 Neo4j的存储优化

Neo4j支持存储优化（压缩和内联存储属性值），对于某些短字符的属性可以直接存储在属性文件中（neostore.propertystore.db）。在实际操作中，像邮政编码、电话号码这样的短字符串属性就可以直接内联到属性存储文件，而不是单独地放在另一个动态存储区，这样将大幅减少I/O操作并且增大吞吐量，因为只有一个文件需要访问。

除了可以内联属性值，Neo4j还可以对属性名称的空间严格维护，例如在社交网络中，有可能会有多个节点存在first_name和last_name这样的属性。如果将每个属性都逐字写入到磁盘上就会造成浪费。因此，替代方案是属性名称都通过属性索引文件从属性存储中间接引用。属性索引允许所有具有相同名称的属性共享单个记录，因而Neo4j可以节省相当大的空间和I/O开销。

即使现在的磁盘访问速度已经很快了，但是CPU访问磁盘仍然比CPU直接访问高速缓存要慢得多。因此，Neo4j也采用了缓存策略，保证那些经常访问的数据可以快速地被多次重复访问。Neo4j高速缓存的页面置换算法是基于最不经常使用的页置换（LFU, Least Frequently Used）缓存策略，根据页的常用程度进行微调。也就是说即使有些页面近期没有使用过，但是因为以前的使用频率很高，那么在短期之内它也是不会被淘汰的。该策略保证了缓存资源在统计学上的最优配置。