1

我有一个大型的二分有向图数据集（约 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) 时间内遍历大型网络？

4

2 回答 2

2

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

于 2012-05-21T16:35:25.317 回答
0

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

于 2012-05-21T17:36:31.813 回答