图数据库——Neo4j（一）内部结构特点

本篇主要分析介绍Neo4j的内部结构特点.

Neo4j主要通过构成图来存储数据，图中的数据包括节点、关系以及节点的属性和关系的属性，关系可以是双向的，也可以是只有单向的.

以下是它的一些特点

• 支持完整的ACID（原子性、一致性、隔离性和持久性）

• 支持常数级时间复杂度的图遍历

• 支持查询的数据导出为JSON和XLS格式

• 支持通过浏览器图形化界面形式访问

• 可以通过多种语言进行访问管理（Java、Python、Ruby、PHP、C#、Js）

原生处理（native processing）

关于原生处理能力的定义，《图数据库》里面提到，假如图数据库可存在免索引邻接（Index Free Adjacency）属性，那么就是具有原生处理能力. 这里的免索引邻接主要是对用非原生图数据库里使用的全局索引而言的，也就是每个节点都会维护其相邻节点的引用，这样可以提供快速高效的图遍历性能，拥有免索引邻接的图数据库引擎遍历整个图的复杂度为 O(n) $O(n)$，而使用索引的复杂度则是 O(nlogn) $O(n\log n)$，但是在实际中，如果遇到要删除一个有大量连接的节点，这时的操作代价就会非常高昂. 在 [1] 中提出ArangoDB提出了一种混合索引的方式，能够避免这类缺点.

原生图存储（native graph storage）

关于Neo4j的存储结构，Neo4j将图结构和属性数据等进行了分离，以此提供高性能的图遍历.

图中的节点和联系的存储文件都是固定大小的，每个记录长度为9字节，因此可以可以在 O(1) $O(1)$的时间复杂度下计算位置.

• 节点（指向联系和属性的单向链表，neostore.nodestore.db）：第一个字节，表示是否被使用的标志位，后面4个字节，代表关联到这个节点的第一个关系的ID，再接着的4个字符，代表第一个属性ID，后面紧接着的5个字符是代表当前节点的标签，指向该节点的标签存储，最后一个字符作为保留位.

• 联系（双向链表，neostore.relationshipstore.db）：第一个字节，表示是否被使用的标志位，后面4个字节，代表起始节点的ID，再接着的4个字符，代表结束个节点的ID，然后是关系类型占用5个字节，然后依次接着是起始节点的上下联系和结束节点的上下节点，以及一个指示当前记录是否位于联系链的最前面.

同时还有属性存储（neostore.propertystore.db）也是固定大小，每个属性记录包括4个属性块（一个属性记录最多容纳4个属性）和指向属性链中下一个属性的ID. 属性记录包括属性类型和指向属性索引文件的指针（neostore.propertysotre.db.index）. 同时属性记录中可以内联和动态存储，在属性值存储占用小时，会直接存储在属性记录中，对于大属性值，可以分别存储在动态字符存储（neostore.propertysotre.db.strings）和动态数组存储（neostore.propertysotre.db.arrays）中，由于动态记录同样由记录大小固定的记录链表组成，因此大字符串和大数组会占据多个动态记录.

缓存策略

参考资料：《图数据库》

[1]. Index Free Adjacency or Hybrid Indexes for Graph Databases

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 *许可协议进行许可。