mysql - 如何在像 MySQL 这样的 RDBMS 中存储双向关系？

Question

假设我想存储我的应用程序的用户之间的关系，类似于 Facebook，本身。

这意味着如果A是B的 friend (或某种关系)，那么B也是A的 friend 。为了存储这种关系，我目前计划将它们存储在关系表中，如下所示

  UID      FriendID
 ------    --------
 user1      user2
 user1      user3
 user2      user1

但是我在这里面临两个选择:

1. 典型情况，我将同时存储 user1 -> user2 和 user2->user1。这将占用更多空间，但(至少在我看来)只需要遍历行一次即可显示特定用户的好友。
2. 另一种选择是存储 user1->user2 或 user2->user1 以及每当我想找到 user1，我将查询表的两列以查找用户的 friend 。它会占用一半的空间，但(至少在我的脑海中)是两倍的时间。

首先，我的推理是否合适？如果是，那么是否有任何我忘记的瓶颈(在扩展/吞吐量或其他方面)？

基本上，除了这里列出的那些之外，两者之间是否有任何权衡取舍。另外，在行业中哪个更受青睐？

Answer 1

以下是这两种方法在数据库中的物理表示方式:

让我们分析这两种方法...

方法1(两个方向都存储在表中):

• 专业版:更简单的查询。
• CON:仅在一个方向插入/更新/删除可能会损坏数据。
• MINOR PRO:不需要额外的限制来确保友谊不会被复制。
• 需要进一步分析:
  1. TIE:一个索引 covers两个方向，因此您不需要二级索引。
  2. TIE:存储要求。
  3. 并列:表现。

方法2(表中只存储一个方向):

• CON:更复杂的查询。
• 专业人士:不会因为忘记处理相反的方向而损坏数据，因为没有相反的方向。
• 轻微缺点:需要 CHECK(UID < FriendID) , 所以同一个友谊永远不能用两种不同的方式来表示，(UID, FriendID) 上的关键可以完成它的工作。
• 需要进一步分析:
  1. TIE:cover 需要两个索引查询的两个方向({UID, FriendID} 上的复合索引和 {FriendID, UID} 上的复合索引)。
  2. TIE:存储要求。
  3. 并列:表现。

第 1 点特别有趣。 MySQL/InnoDB 总是 clusters数据和二级索引在聚簇表中可能很昂贵(请参阅 this article 中的“聚簇的缺点”)，因此方法 2 中的二级索引似乎会吃掉更少行的所有优势。 然而，二级索引包含与主索引完全相同的字段(只是顺序相反)，因此在这种特殊情况下没有存储开销。也没有指向表堆的指针(因为没有表堆)，所以它可能比普通的基于堆的索引更便宜。并且假设查询被索引覆盖，通常也不会有与聚集表中的二级索引相关联的双重查找。因此，这基本上是平局(方法 1 和方法 2 都没有显着优势)。

第 2 点 与第 1 点相关:无论我们是拥有 N 个值的 B-Tree 还是拥有 N/2 个值的两个 B-Tree 都无关紧要。所以这也是一个平局:两种方法都将使用大致相同的存储量。

同样的推理也适用于第 3 点:我们是搜索一个较大的 B-Tree 还是搜索两个较小的 B-Tree，并没有太大区别，所以这也是平局。

因此，为了稳健性，尽管查询有些难看，并且需要额外的 CHECK ，我会采用方法 2。