巨大的图结构

Question

我正在开发一个应用程序，需要一种结构来在内存中表示一个巨大的图（节点数量在1000000到6000000之间，每个节点有100到600条边）。这些边的表示会包含一些关系的属性。

我尝试过使用内存映射、数组、字典和字符串来表示这个结构，但这些方法总是因为内存限制而崩溃。

我希望能得到一些建议，看看我该如何表示这个结构，或者类似的东西。

顺便说一下，我使用的是Python。

Answer 1

我怀疑你能否使用这种内存结构，除非你有很多内存可用：

假设你每个节点有600条指向其他节点的边，每个节点占用4个字节（也就是一个整数键），而每条边仅仅是指向的目标节点的键（每个4个字节）。

那么每个节点的原始数据就是4 + 600 * 4 = 2404字节，假设有6,000,000个节点，总共就需要超过14.4GB的内存。

这还不包括其他额外的开销或节点（或边）中的任何其他数据。

Answer 2

根据你的硬件资源，对于这么大的图来说，全部放在内存里可能不太现实。从图数据库的角度来看，有两个可能的选择：

• Neo4j - 这个数据库声称可以轻松处理数十亿个节点，而且已经开发了很长时间。
• FlockDB - 这是Twitter新发布的一个分布式图数据库。

既然你在用Python，你有没有看过Networkx? 如果你出于兴趣看过这个库，你加载这么大图的进展如何？

Answer 3

1. 如果每个节点有100到600条边，那你总共就有36亿条边。
2. 为什么这些数据必须全部放在内存里呢？
3. 你能给我们看看你现在用的结构吗？
4. 我们能用多少内存？（你遇到的内存限制是多少？）

如果你需要把这些数据放在内存里的唯一原因是为了快速读取和写入，那不如用数据库。数据库的读写速度非常快，很多时候它们可以直接读取数据，而不需要去硬盘上找。