php - 使用 PHP 创建一个高效的好友列表

Question

我想建立一个具有社交网络元素的网站。

所以我一直在想一种高效的方式来存储好友列表(有点像Facebook)。

经过一番搜索，我得到的唯一建议是制作一个包含两个“id”的“表格”，表示友谊。

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

我有 Java 背景，但我对 PHP 不够熟练。

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

想法是将你 friend 的所有“id”保存在一个树数据结构中，树中的每个节点都类似于 friend id 中的一位数字。

首先从 1 个节点开始，然后随着用户添加 friend 而添加更多节点。 (有点像 Lempel–Ziv)。

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

“X”表示 Id 结束。

例如看这棵树:

An Example

在这棵树中，用户有 4 个具有以下“id”的 friend :

• 0
• 143
• 1436
• 15

更新:之前可能不清楚，这个想法是每个用户都会有一个多维数组形式的树，其中指针本身的存在表明 friend 的“id” .

如果每个用户都有这样一个多维数组，搜索id“y”是否是我的 friend ，从我的 friend 列表中删除id“y”或者添加id“y”到我的 friend 列表都需要常数时间O( 1) 在不依赖于网站可能拥有的用户数量的情况下，唯一的缺点是，采用如此庞大的数组，对其进行序列化并将其插入表格的每一行似乎并不正确。

-这甚至有可能实现吗？

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

-有更好的方法吗？

我选择这个的好处是，即使有非常多的 ID(数百万或数十亿)，搜索、添加、删除时间也是线性的(取决于位数)。

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

Answer 1

我强烈反对这样做。

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

• “呈现”用户列表需要 CPU 投资。

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

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