主要參考書籍：graph database
近期工作中要做一些圖譜的應(yīng)用，于是這幾天就調(diào)研了下圖數(shù)據(jù)庫，最后就有了本文。ps：本人第一次做圖譜相關(guān)的應(yīng)用，具體怎么構(gòu)建也還不清楚，大家有什么資料、建議歡迎私信、留言的。

圖領(lǐng)域的問題

整個圖領(lǐng)域，所有要解決問題都能分為兩大類：

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（離線分析）

另一種分類是從采用的技術(shù)上，3 種主要的圖數(shù)據(jù)模型：

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

市面上大多數(shù)圖數(shù)據(jù)庫都是基于 property graph 來做的。

圖數(shù)據(jù)庫

看圖數(shù)據(jù)庫的時候，我們從兩個技術(shù)點(diǎn)切入：

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？
如果每個節(jié)點(diǎn)直接指向關(guān)聯(lián)的節(jié)點(diǎn)，相當(dāng)于每個節(jié)點(diǎn)都有一個自己的局部索引，比起全局索引來說，成本更低，因此速度也更快

分析

native graph storage

index-free adjacency 是圖數(shù)據(jù)庫相比于傳統(tǒng)的 mysql 的優(yōu)勢的核心 key，那么圖數(shù)據(jù)庫用什么結(jié)構(gòu)去存儲 index-free adjacency 是關(guān)鍵設(shè)計(jì)點(diǎn)。

圖片

架構(gòu)上生層是對外訪問的 api，右邊是事務(wù)管理，左邊有 cache 等，下面我們看下 disk 上存儲的結(jié)構(gòu)：

圖片

neo4j 在磁盤上會分不同的 store file 存儲

• neostore.nodestore.db：存儲 node
• neostore.propertystore.db：存儲屬性
• neostore.relationshipstore.db：存儲關(guān)系

一個重要的設(shè)計(jì)點(diǎn)是 store 中存儲的 record 都是固定大小的，固定大小帶來的好處是：因?yàn)槊總€ record 的大小固定，因此給定 id
就能快速進(jìn)行定位。
具體結(jié)構(gòu)是：

圖片

上圖第一個是 node record 的結(jié)構(gòu)：

• 1byte：in-use flag，表明該 node 是否在使用
• 4byte：第一個 relation id
• 4byte：第一個 property id
• 5byte：label 信息（可能直接 inline 存儲）
• 1byte：reversed

下面是 relation record 的結(jié)構(gòu)：
剛開始是開始和結(jié)束節(jié)點(diǎn)的 node id，接著是 relation type pointer，然后開始和結(jié)束節(jié)點(diǎn)的前驅(qū)和后繼 relation id

更形象一點(diǎn)的圖

圖片

一個可能的搜索過程是：對于給定的一個 node record，可以通過 id 進(jìn)行簡單的偏移計(jì)算得到 node，然后通過 relation_id 定位到 relation record，然后得到 end node id，通過偏移計(jì)算得到 node

雙向存儲

還有一個問題：圖中節(jié)點(diǎn)的關(guān)系是有方向的，怎么記錄這種方向呢？如果方向是雙向的，我們難道要存儲兩個 relation 嗎？

看例子：

圖片

這種 partner 的關(guān)系天然就是雙向的，但是我們存儲的時候，難道要存儲兩個關(guān)系嗎，如下圖：

答案是：以任意一個節(jié)點(diǎn)為開端，另一個為尾端，即存儲成為單向的關(guān)系

在 neo4j 中任意的關(guān)系都有一個 start node 和一個 end node，而且 start node 和 end node 都會有個關(guān)聯(lián)的雙向鏈表，這個雙向鏈表中就記錄了從該節(jié)點(diǎn)出去和進(jìn)入的所有關(guān)系，一個實(shí)例是：

圖片

至此我們就對圖數(shù)據(jù)庫有了個大概的了解了，后續(xù)的分析會隨著項(xiàng)目的推進(jìn)持續(xù)輸出。

待完成

下面是今后需要跟進(jìn)的一些工作

• 性能測試
• 分布式方案
• Titan 調(diào)研
• ....

參考

neo4j 底層存儲結(jié)構(gòu)分析 (1)
Modelling Data in Neo4j: Bidirectional Relationships