前言
4store是一个RDF分布式存储和检索系统，其项目主页地址为http://4store.org/。 虽然源码都公开了，但是因为文档太稀缺，注释太少，再加上稍显混乱的C语言结构，让人很难去了解其实现细节。笔者和小伙伴两个人坚持看了一阵子，终于有些顿悟，打算做一个系列的学习笔记分享，以帮助那些同样对4store实现感兴趣的同学(估计是小小小众的)来一起入门。废话不多说，第一篇文章我们来对4store的整体存储结构做个概述，这样看起代码来会有个整体的脉络。至于各个数据结构的细节，会在后续文章中逐个详细分析。
资源id的保存
首先来看一个turtle [http://www.w3.org/TR/turtle/] 格式的RDF三元组：
<http://rdf.ali.com/ns/m.7727> <http://rdf.ali.com/ns/rdf-schema#vname> "Pisen/品胜" .
解析的时候这三列就对应了subject, predicate, object。此外4store中还多存储了一个model列，对应于RDF中的命名图或默认图。所以一个RDF三元组在4store中是以一个四元组[m, s, p, o]的格式来表示的。任何一个四元组当中的元素，在4store中都被称作资源，对应唯一的64bit的资源id(rid)。资源可以分为三种，分别是URI, literal, blank node，rid的最高两位bit表示资源类型，例子中的subject和predicate都属于URI类型，object则属于literal类型。对于URI类型和literal类型的资源，都有源字符串。rid到源字符串的映射关系，是通过fs_rhash来存储的。rhash的结构如下：
rhash在保存字符串时有多重策略，disp字段表示了存储的策略。如果字符串小于等于15个字符串，直接保存到hash entry的str[]里面，如果超过15个字符，则字符串内容保存到lex文件中，hash entry里面保存offset， 另外对于URI类型的资源来说，会对频繁出现的字符串前缀编码，保存到prefix文件中，hash entry中的pstr字段保存prefix code。
四元组的保存
四元组的保存有两个维度，一个是在model维度，保存这个model下的所有三元组，另一个是在predicate维度，保存这个predicate关联的model, subject, object。我们先来看model维度的存储结构。
model维度的结构
结构图如下：
大致来说，一个model下的所有三元组[s, p, o]会分块保存到文件中，不同的块之间通过指针链接起来。
predicate维度的结构
结构图如下：
4store中会将每个predicate关联的[m,s,o]都记下来，为了支持s和o两个维度的快速查找，分别对s和o建了trie树索引。其中trie树每层的分支数为4（每层使用rid的两位），trie树的叶子节点指向pairs数组中属于该p & s或者p & o的首个元素。
粗略的概述就到此结束了，相信大家和我们一样，在很多细节的地方都还有很多疑问，没关系，后续的文章我们会逐个细细分析，敬请期待。
由 udpwork.com 聚合
|
评论: 0
|
要! 要! 即刻! Now!