图数据库奥秘初探

主要参考书籍:graph database 近期工作中要做一些图谱的应用,于是这几天就调研了下图数据库,最后就有了本文。ps:本人第一次做图谱相关的应用,具体怎么构建也还不清楚,大家有什么资料、建议欢迎私信、留言的。

图领域的问题

整个图领域,所有要解决问题都能分为两大类:

  1. Technologies used primarily for transactional online graph persistence, typically accessed directly in real time from an application(在线处理)
  2. Technologies used primarily for offline graph analytics, typically performed as a series of batch steps(离线分析)

另一种分类是从采用的技术上,3 种主要的图数据模型:

  1. property graph
  2. Resource Description Framework (RDF) triples
  3. hypergraphs

市面上大多数图数据库都是基于 property graph 来做的。

图数据库

看图数据库的时候,我们从两个技术点切入:

  1. The underlying storage
  2. The processing engine

图片

像 Titan 使用的不是 native 存储,后端可以使用

  • Apache Cassandra
  • Apache HBase
  • Oracle BerkeleyDB

而 neo4j 用的就都是 native graph storage and native graph processing

此处解释下什么叫 native graph storage 和 native graph processing

native graph processing

如果存储具有 index-free adjacency 属性,则称为具有 native processing属性。

那什么叫 index-free adjacency? 如果每个节点直接指向关联的节点,相当于每个节点都有一个自己的局部索引,比起全局索引来说,成本更低,因此速度也更快

分析

native graph storage

index-free adjacency 是图数据库相比于传统的 mysql 的优势的核心 key,那么图数据库用什么结构去存储 index-free adjacency 是关键设计点。

图片

架构上生层是对外访问的 api,右边是事务管理,左边有 cache 等,下面我们看下 disk 上存储的结构:

图片

neo4j 在磁盘上会分不同的 store file 存储

  • neostore.nodestore.db:存储 node
  • neostore.propertystore.db:存储属性
  • neostore.relationshipstore.db:存储关系

一个重要的设计点是 store 中存储的 record 都是固定大小的,固定大小带来的好处是:因为每个 record 的大小固定,因此给定 id 就能快速进行定位。 具体结构是:

图片

上图第一个是 node record 的结构:

  • 1byte:in-use flag,表明该 node 是否在使用
  • 4byte:第一个 relation id
  • 4byte:第一个 property id
  • 5byte:label 信息(可能直接 inline 存储)
  • 1byte:reversed

下面是 relation record 的结构: 刚开始是开始和结束节点的 node id,接着是 relation type pointer,然后开始和结束节点的前驱和后继 relation id

更形象一点的图

图片

一个可能的搜索过程是:对于给定的一个 node record,可以通过 id 进行简单的偏移计算得到 node,然后通过 relation_id 定位到 relation record,然后得到 end node id,通过偏移计算得到 node

双向存储

还有一个问题:图中节点的关系是有方向的,怎么记录这种方向呢?如果方向是双向的,我们难道要存储两个 relation 吗?

看例子:

图片

这种 partner 的关系天然就是双向的,但是我们存储的时候,难道要存储两个关系吗,如下图:

那肯定是不需要的,这种存储就是一种浪费,那到底 neo4j 中是怎么存储 partner 这种双向关系的呢?

答案是:以任意一个节点为开端,另一个为尾端,即存储成为单向的关系

在 neo4j 中任意的关系都有一个 start node 和一个 end node,而且 start node 和 end node 都会有个关联的双向链表,这个双向链表中就记录了从该节点出去和进入的所有关系,一个实例是:

图片

图片来自:neo4j 底层存储结构分析 (1) 上图中 B 节点的 prev 和 next 我们就能看到在这个链表中,B 有时候是 start node 有时候是 end node。

至此我们就对图数据库有了个大概的了解了,后续的分析会随着项目的推进持续输出。

待完成

下面是今后需要跟进的一些工作

  • 性能测试
  • 分布式方案
  • Titan 调研
  • ....

参考

neo4j 底层存储结构分析 (1) Modelling Data in Neo4j: Bidirectional Relationships

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯游戏云的专栏

游戏差异更新—BSDiff算法解析

差异更新即在软件更新时只更新差异化的部分,以达到用最小的下载量完成软件的更新需求。该思想由来已久,从刚接触电脑时的操作系统、应用软件快速更新功能或填补漏洞,到迭...

22.3K9
来自专栏HBStream流媒体与音视频技术

采集音频和摄像头视频并实时H264编码及AAC编码

5827
来自专栏web前端教室

javascript中那些可以连成片的点

JavaScript的提高,是一点一滴的提高,这些点滴连接成线,进而连接成为一个面。 这个“面”的知识你都会了之后,会首先从某个点上形成突破再提高,然后这些再提...

2066
来自专栏带你撸出一手好代码

使用测试用例来约束自己的代码

写测试代码这种事情 ,以前只在网上和书上看到过, 自己从来没有写过。 每当看到那些世界顶级程序员编写的技术书籍中出现“测试用例”“测试代码”的字样或者一些行业的...

3676
来自专栏程序猿DD

程序员你为什么这么累【续】:编码习惯之异常处理

导读: 程序员你为什么这么累? 我的编码习惯 - 接口定义 我的编码习惯 - Controller规范 我的编码习惯 - 日志建议 对于大型IT系统,最怕的事情...

36611
来自专栏Jerry的SAP技术分享

腾讯AI开放平台的接口调用指南

最近无意发现腾讯AI开放平台上提供了大量好玩的人工智能云服务,而且是完全免费的。只需要用QQ号登录即可。这么好的东西,作为一个程序员,当然要试试了!

1.5K2
来自专栏黑白安全

Po主是谁?通过新浪微博图片反查上传者信息

链接为 https://wxt.sinaimg.cn/thumb300/9d0d09ably1fsn7m0jyzzj20m80cidgm.jpg 的图

1342
来自专栏cs

用列图

1734
来自专栏吉浦迅科技

DAY53:阅读Profiler Counter Function

Each multiprocessor has a set of sixteen hardware counters that an application c...

832
来自专栏腾讯开源的专栏

高效使用lua作为业务开发语言的秘诀在这里!

导语 你还在使用c++开发UE4吗?会不会感觉太慢了?会不会感觉编译一次就可以去楼下喝杯咖啡了?会不会感觉总是提心吊胆,搞不好什么时候就crash了?现在不用...

5692

扫码关注云+社区

领取腾讯云代金券