MySQL有效地存储无向图边

Question

我想存储无向图边(例如,对于朋友).要存储和检索节点的所有朋友a,可以使用:

每个边创建两行,每个节点在一列上查询:

+--------------------------+
| id | from_node | to_node |
+--------------------------+
| 1  |  a        |  b      |
| 2  |  b        |  a      |
+--------------------------+
SELECT * FROM `x` WHERE from_node = a

每条边创建一行,使用OR:

+--------------------------+
| id | node_a    | node_b  |
+--------------------------+
| 1  |  a        |  b      |
+--------------------------+
SELECT * FROM `y` WHERE node_a = a OR node_b = a

这样可以提高查找效率？

• 表中x包含2n行,索引from_node和to_node,以及在一列上查找
• 表中y包含n行,索引node_a和node_b,以及使用两列查找OR

Answer 1

这可能已经过时而无用，但我会发布以防它帮助其他人！

我像你的第二个例子一样存储无向图，并且有一个约束，node_a 必须小于 node_b。然后，您可以轻松地UNIQUE对该对设置约束，并知道数据是一致的。通过将 node_a 与 {a,b} 和 node_b 中的较小值进行比较，查询需要做更多的工作。PostgreSQL（我最了解的数据库）提供的功能GREATEST()和LEAST()功能在这里有所帮助。

Answer 2

如果你优化一切，那么 X 将是最快的，假设你从磁盘读取数据并查询一个人的朋友。这是因为您可以在磁盘上排列数据，以便将它们排序以匹配一个索引，即您正在查询的索引。因此，对于一个人来说，您只需要进行一次磁盘寻道。Y 需要对两个索引进行查询，因此可能意味着多次搜索来检索朋友，即使对于一个人也是如此（磁盘访问时间通常主导简单查询）。

请参阅维基百科上的聚集索引（以及mysql 手册）

如果您足够幸运，知道数据将始终在内存中，那么它们可能都“足够快”（即使数据在磁盘上，它们也可能足够快 - 我并不是说 X 是最好的设计，只是它可以变得最有效）。