2

我想建立一个包含一些社交网络元素的网站。

所以我一直在想一种有效的方法来存储朋友列表（有点像 Facebook）。

在搜索了一下之后，我遇到的唯一建议是制作一个带有两个“id”的“表格”，表示友谊。

这可能适用于小型网站，但似乎效率不高。

我有Java背景，但我对PHP不够精通。

我想到了一个想法，我认为它可以很好地工作，问题是我不确定如何实现它。

这个想法是将您朋友的所有“id”保存在树数据结构中，该树中的每个节点都类似于朋友 id 中的一个数字。

首先从 1 个节点开始，然后随着用户添加朋友而添加更多节点。（有点像 Lempel-Ziv）。

每个节点将能够指向 11 个其他节点，0 到 9 和 X。

“X”标记了 Id 的结尾。

例如看这棵树：

一个例子

在这棵树中，用户有 4 个朋友，他们的“id”如下：

  • 0
  • 143
  • 1436
  • 15

更新：正如之前可能不清楚的那样，这个想法是每个用户都将拥有一棵多维数组形式的树，其中指针本身的存在表示朋友的“id”。

如果每个用户都有这样一个多维数组，搜索 id "y" 是否是我的朋友，从我的朋友列表中删除 id "y" 或将 id "y" 添加到我的朋友列表中都需要恒定时间 O(1) 没有依赖于网站可能拥有的用户数量，唯一的缺点是，采用如此庞大的数组，将其序列化并将其推入表格的每一行似乎并不正确。

- 这甚至可以实施吗？

- 使用序列化将该树插入表中是否可行？

- 有没有更好的方法来做到这一点？

我选择这个的好处是，即使有大量的 id（数百万或数十亿），搜索、添加、删除时间也是线性的（取决于位数）。

对于实施此方法的任何帮助或有关改进或更改此方法的替代方法的任何建议，我将不胜感激。

4

4 回答 4

3

我强烈建议不要这样做。

  • 存储节省并不显着，并且可能（可能？）更糟。在真实的数据集中，使用这种方法为您节省的实际空间是最小的。计算平均节省是一个非常困难的问题，但是使用一些实数并尝试一些具有随机 ID 的样本。如果您有 100 万用户，请考虑一个有 15 个朋友的用户。使用此方法可以节省多少数据？您实际上可能会使用更多空间，因为树邻接模型可能需要大量数据。

  • “渲染”用户列表需要 CPU 投资。

  • 插入是非确定性和非平凡的。 当您将新用户添加到现有树中时，您将有多种插入它们的方法。假设您不随意选择，则很难计算出哪种方法是最好的（并且只能基于启发式）。

这是我想到的大事。但总的来说，我认为你想多了。

于 2011-08-01T18:37:40.790 回答
2

您应该查看OQGRAPH，开放查询图形存储引擎。它旨在为 MySQL 处理高效的树和图形存储。

您还可以查看我的演示文稿Models for Hierarchical Data with SQL and PHP ，或者我对将平面表解析为树的最有效/优雅的方法是什么的回答？在这里堆栈溢出。

我描述了一个我称之为Closure Table的设计，它记录了层次结构中祖先和后代之间的所有路径。

于 2011-08-01T18:14:09.887 回答
2

您在标题中说“使用 PHP”，但这似乎只是一个数据库问题。信不信由你，链接表是迄今为止最好的方法。特别是如果您拥有数百万或数十亿用户。它会更快处理，更容易在 PHP 代码中处理并且存储更小。

更新

用户表：

  id    |   name   |   moreInfo
   1    |    Joe   |     stuff
   2    |    Bob   |     stuff
   3    |   Katie  |     stuff
   4    |   Harold |     stuff

友谊表：

   left   |   right
    1     |     4
    1     |     2
    3     |     1
    3     |     4

在这个例子中，乔认识每个人，凯蒂认识哈罗德。

这当然是一个简化的例子。

我很想听听是否有人对左右有更好的逻辑，并解释原因。

更新

我在下面的评论中给出了一些 php 代码，但它被标记为错误，所以又来了。

$sqlcmd = sprintf( 'SELECT IF( `left` = %1$d, `right`, `left`) AS "friend" FROM `friendship` WHERE `left` = %1$d OR `right` = %1$d', $userid);
于 2011-08-01T18:15:54.030 回答
1

几个想法：

  • 有序列表 - 搜索有序列表很快，虽然排序本身可能更重；
  • 水平分区数据；
  • 摆脱过早的优化。
于 2011-08-02T07:32:15.717 回答