Neo4j存储原理与数据结构

落日映苍穹つ 2024-03-31 14:08 21阅读 0赞

Neo4j存储原理  
  本文主要针对数据在磁盘上的存储对Neo4j的存储原理进行简单介绍。Neo4j数据库文件被持久化到磁盘存储中以获得长期的持久性。 默认情况下，数据文件存储在Neo4j目录下的data /databases/graph.db中（v3.x+）

其中：

nodestore\* 存储图中节点相关的信息  
relationship\* 存储图中关系相关的信息  
property\* 存储图中的key/value属性信息  
label\* 存储图中与索引相关的标签数据  
  由于Neo4j是一个No Schema的数据库，且数据库的内部只有点，关系，属性和索引等，因此Neo4j使用固定的记录长度来持久化数据，并通过这些文件中的偏移量来快速进行数据的插入和查询。 下表展示了Neo4j为存储的Java对象类型使用的固定大小:

### Store File | Record size | Contents ###

// in_use(byte)+next_rel_id(int)+next_prop_id(int)+labels(5)+extra(byte)
            public static final int RECORD_SIZE = 15;            
            // [    ,   x] in use bit
            // [    ,xxx ] higher bits for rel id
            // [xxxx,    ] higher bits for prop id
            long nextRel = cursor.getInt() & 0xFFFFFFFFL;
            long nextProp = cursor.getInt() & 0xFFFFFFFFL;
    
            long relModifier = (headerByte & 0xEL) << 31;
            long propModifier = (headerByte & 0xF0L) << 28;
    
            long lsbLabels = cursor.getInt() & 0xFFFFFFFFL;
            long hsbLabels = cursor.getByte() & 0xFF; // so that a negative byte won't fill the "extended" bits with ones.
            long labels = lsbLabels | (hsbLabels << 32);
            byte extra = cursor.getByte();
            boolean dense = (extra & 0x1) > 0;

点的数据结构如下：

第1字节：InUse，使用状态，最后一位标识该节点是否删除，接着三位标识邻接边ID的高位，前四位标识属性ID的高位；  
第2~5字节：nextRedid，第一个连接的边的ID;  
第6~9字节：nextPropId，第一个属性的ID；  
第10~14字节：labels，存储指针的标签；  
第15字节：extra，保留位，存记录是否为dense，dense的意思是是否为一个supernode。  
关于点的数据结构这里需要注意的是：

只保存该点的第一个边的ID，用第一个字节的第5-7位表示关系ID的高位，额外2-5个字节保存关系ID的低位，也就是说Neo4j中边的ID用35位表示；这也就是为什么下文说的Neo4j中的点和关系的数量存储限制是235而不是232。  
仅保存该点的第一个属性的ID，用第一个字节InUse的前四个位表示点最后4个位表示属性ID的高位，额外用一个Int保存属性的地位，也就是说Neo4j中属性ID用36位表示；  
用最后一个B的最后一个位表示该点是否为超级点，即有很多边的节点；  
边的存储  
  边的固定长度为34字节，边的存储在文件neostore.relationshipstore.db中，边的数据结构代码片段如下：

// [    ,   x] in use flag
            // [    ,xxx ] first node high order bits
            // [xxxx,    ] next prop high order bits
            long firstNode = cursor.getInt() & 0xFFFFFFFFL;
            long firstNodeMod = (headerByte & 0xEL) << 31;
    
            long secondNode = cursor.getInt() & 0xFFFFFFFFL;
    
            // [ xxx,    ][    ,    ][    ,    ][    ,    ] second node high order bits,     0x70000000
            // [    ,xxx ][    ,    ][    ,    ][    ,    ] first prev rel high order bits,  0xE000000
            // [    ,   x][xx  ,    ][    ,    ][    ,    ] first next rel high order bits,  0x1C00000
            // [    ,    ][  xx,x   ][    ,    ][    ,    ] second prev rel high order bits, 0x380000
            // [    ,    ][    , xxx][    ,    ][    ,    ] second next rel high order bits, 0x70000
            // [    ,    ][    ,    ][xxxx,xxxx][xxxx,xxxx] type
            long typeInt = cursor.getInt();
            long secondNodeMod = (typeInt & 0x70000000L) << 4;
            int type = (int)(typeInt & 0xFFFF);
    
            long firstPrevRel = cursor.getInt() & 0xFFFFFFFFL;
            long firstPrevRelMod = (typeInt & 0xE000000L) << 7;
    
            long firstNextRel = cursor.getInt() & 0xFFFFFFFFL;
            long firstNextRelMod = (typeInt & 0x1C00000L) << 10;
    
            long secondPrevRel = cursor.getInt() & 0xFFFFFFFFL;
            long secondPrevRelMod = (typeInt & 0x380000L) << 13;
    
            long secondNextRel = cursor.getInt() & 0xFFFFFFFFL;
            long secondNextRelMod = (typeInt & 0x70000L) << 16;
    
            long nextProp = cursor.getInt() & 0xFFFFFFFFL;
            long nextPropMod = (headerByte & 0xF0L) << 28;
    
            byte extraByte = cursor.getByte();

边的数据结构如下：

第1字节：InUse，使用状态，最后一位标识该节点是否删除，接着三位标识邻接边ID的高位，前四位标识第一个属性ID的高位；  
第2~5字节：firstNode, 开始顶点的ID；  
第6~9字节：sencondNode，结束顶点的ID；  
第10~13字节：relationshipType，存储当前边的类型，同时包含当前边的终点、边的起点的前一个和后一个边、边的终点的前一个和后一个边的高位信息，也就是说，这32位当中只有最后16位才标识真正的类型，其他都是用来存储对应的边和点的高位信息；  
第14~17字节：firstPrevRelId，开始顶点的来源指向关系；  
第18~21字节：firstNextRelId，开始顶点的目标指向关系；  
第22~25字节：secondPrevRelId，结束顶点的来源指向关系；  
第26~29字节：secondNextRelId，结束顶点的目标向关系；  
第30~33字节：nextPropId，第一个属性的ID；  
第34字节：firstInChainMarker，关系链的第一个标识；  
关于边的数据结构，需要注意的是：

边保存了其对应的起点和终点的ID，可以看到点的ID跟边一样，也是35位；这算是最基本的字段；除此之外，还保持了起点对应的前一个和后一个关系，终点对应的前一个和后一个关系。这看起来就有点特别了，也就是说，对一个点的所有边的遍历，不是由点而是由其边掌控的；  
由于起点和终点的边都保存了，所以无论从起点开始遍历还是从终点开始都能够顺利完成遍历操作；  
与点一样，边也仅保存自身的第一个属性；  
最后，分别有个标识位来说明该边是否为起点和终点的第一条边。  
点和边的存储结构，直观标识如下图所示：  
存储结构  
属性的存储  
  属性的固定长度为 41 字节，存储在文件neostore.propertystore.db中，属性的代码片段如下：

public static final int DEFAULT_PAYLOAD_SIZE = 32;
    
    public static final int RECORD_SIZE = 1/*next and prev high bits*/
            + 4/*next*/
            + 4/*prev*/
            + DEFAULT_PAYLOAD_SIZE /*property blocks*/;
    // = 41

属性的数据结构如下：  
第1B：InUse，使用状态，标识是否删除；  
第2~3B：type，属性类型；  
第4~5B：keyIndexId，关键索引ID，指向neostore.propertystore.db.index  
第6~29B：propBlock，属性值，可能存储在字符串区neostore.propertystore.db.strings ，也可能存储在数组区neostore.propertystore.db.arrays ；  
第30~33位： nextPropId，属性的ID。

Neo4j存储限制  
  上一节我们介绍了，Neo4j实际使用3+4*8=35位保存点和边的ID，用4 + 4*8 = 36位保存属性ID。因此对应的存储限制分别为：

点和边：235 = 34,359,738,368  
属性：236= 68,719,476,736  
点类别：232 = 4294967296  
边类型：216 = 65536

https://neo4j.com/developer/kb/understanding-data-on-disk/  
https://zhuanlan.zhihu.com/p/83962186  
https://neo4j.com/docs/operations-manual/current/tools/neo4j-admin/neo4j-admin-store-info/  
https://www.bianchengquan.com/article/332247.html