高效大规模图遍历的数据库

Question

我有一个大型二分有向图数据集（约 2000 万个元素）。在当前的使用中，我运行的遍历算法每次运行约 500,000 个节点。这些算法有效，但历史上运行的是从文本文件加载到内存的数据。

文本文件似乎是一个不好的方法，所以我将数据作为邻接列表传输到 mongoDB 中，即。

{ _id: 1, children: [2, 3] }
{ _id: 2, children: [4] }
{ _id: 3, children: [5, 6, 7] }

这可行，但我觉得该模型对于我正在做的事情来说效率低下。在伪代码中，从 _id: 1 开始的广度优先搜索的查询结构如下所示：

children = getChildren(_id = 1)
for child in children
    grandchildren = getChildren(_id = child)
    // etc., either recursively or as a nested loop

我遇到的数据库问题是没有逻辑连接节点。每个查询都必须遍历索引树，如果我没记错的话，是 O(log N)。加载后，文本文件方法的复杂度为 O(1)，因为我可以制定一些简单的查找规则来直接指向节点子节点。

TL;DR 有没有一种方法可以使用数据库在 O(1) 时间内遍历大型网络？

Answer 1

您可以尝试使用Neo4J，一个NoSQL图形数据库。我没有使用过它，但它承诺高性能。

Answer 2

MongoDB 不是一个多用途数据库。您显然对使用专用的“专业”图形数据库感兴趣。将 MongoDB 用于此类图和相关搜索算法是不行的。

Answer 3

GraphScope

是一个快速、高效、高度可扩展的图查询系统，也许它就是您所需要的。 GraphScope是一个强大的分布式图计算平台，GAIA-IR是GraphScope中的交互式图查询引擎。 事实上，GAIA-IR 的性能优于 mongoDB（以及 Neo4j 通信版本）几个数量级。但这还不是全部 - GAIA-IR 提供了统一的中间表示层，这意味着可以轻松合并各种图查询语言。例如，GAIA-IR 已经支持最流行的图形查询语言 Gremlin 和 Cypher。

您可以参考这篇

文章

来了解GAIA-IR的设计以及如何部署和使用。 免责声明：我是 GraphScope 的作者。

Answer 4

在我们的一个项目中，我们有平均有 500 万个节点的循环有向图，我们能够使用 PostgreSQL 递归查询在 5 秒内完成完整的遍历。