MySQL 高效存储无向图边

Question

我想存储无向图边(例如，为 friend )。要存储和检索节点 a 的所有 friend ，可以使用:

每条边创建两行，每个节点查询一列:

+--------------------------+
| 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 上的索引，使用 在两列上查找>或

Answer 1

这可能太过时了，没有用，但我会发布它以防对其他人有帮助!

我像您的第二个示例一样存储无向图，并且有一个约束，即 node_a 必须小于 node_b。然后，您可以简单地在该对上放置一个 UNIQUE 约束，并知道数据是一致的。通过将 node_a 与 {a,b} 中较小的值进行比较，将 node_b 与另一个值进行比较，查询需要做更多的工作。 PostgreSQL(我最了解的数据库)提供了 GREATEST() 和 LEAST() 函数来帮助解决这个问题。