图形数据库如何在磁盘上存储数据

Question

我看过这些文件：

• TurboGraph
• GraphChi
• 比沙德并行处理器
• G-商店
• NXgraph
• GridGraph

...and还有其他几个。我对数据库很陌生(除了把它们用于web应用程序而不了解它们的内部结构)，所以我对如何使用磁盘存储没有太多的基础。

总的来说，我想知道这些文件是如何在文件系统中存储图形的。在简短地浏览它们时，它们提到将相关的子图从磁盘加载到内存中，以便进行有效的更新/查询。其中一些文件将边缘存储在一组文件中(称其为“碎片”)，而顶点则存储在另一组文件中(称为“间隔”)。有些有多个不同的ID，如TurboGraph中的"record (RID)“和”顶点ID“(图1)。

然而，我还没有看到一个完整的概述，所有的部分是如何结合在一起的。想知道能不能解释一下。

具体地说：

1. 如何将数据构造为图形数据库的文件(在较高级别上)。
2. 当查询/更新时，必须将内容加载到一个较高级别的内存中。

到目前为止，我还不清楚需要加载到内存中的是什么，以及ID的具体用途是什么。我不确定每个页面(通常是>= 1MB )是否被加载到内存中并以某种方式进行解析，还是逐行扫描，或者类似的东西(基本上不确定文件是如何解析/扫描的，是否被解析成某种内存中的数据结构，或者是否可以直接遍历文件字节)。我不知道这些身份证是干什么用的。在RDBMS中，ID有时是每个表的递增整数，而没有其他含义。在这些论文中，ID似乎更多地与页面中顶点的位置以及某种类型的偏移等有关。另外，有些论文还为一个顶点存储了一条很大的单行(似乎是这样)，它的所有边(一个邻接列表)，但是我想知道每个顶点是否有数千条或数百万条边，该怎么办。如果你能指出需要寻找的相关特征，那么做进一步的研究将有助于使这个问题变得更加清晰。

非常感谢你抽出时间，我希望这是有意义的。

图1。

Answer 1

我相信图表的每一种实现都会因其如何从磁盘上写入和读取而有所不同。

在Manish的图:同步复制、事务处理和不信任图数据库第2页2.2节中，数据存储讨论介绍如下：

Dgraph存储在一个名为Badger的可嵌入键值数据库中，用于磁盘上的数据输入输出。獾是一种基于LSM树的设计，但与其他设计不同的是，它可以选择地将值与键分开存储，从而生成一个小得多的LSM树，从而降低写入和读取放大。

你问：

1. 如何将数据构造为图形数据库的文件

数据由主谓组存储到投递列表中。任何包含边缘列表的节点都会将该列表存储在一个单独的投递列表中，直到它达到某个大小的阈值，并且需要在两个或多个列表中拆分。这可以理解为，任何一对一的关系边或谓词都保存在自己的列表中，一对多的关系边或谓词被分组在一起，并将链接uid或对象值保存到列表中。主要内容是獾将值与键分开存储，以生成一棵更小的树，从而提高读写性能。

1. 当查询/更新时，必须将内容加载到一个较高级别的内存中。

Manish刚刚发布了一个关于内存管理的博客文章，可以比我自己更好地解释这个方面。