数百万节点的图数据结构（社交网络）

Question

在使用“图(Graphs)”数据结构设计社交网络的情况下，您可以执行BFS来查找一个人到另一个人的联系，我有一些相关问题。

如果有数百万个用户，拓扑结构将比我们通常设计的图更加复杂和相互关联，我在尝试理解如何解决这些问题。

1. 在现实世界中，“服务器会失败”。这会对您产生什么影响？

2. 你怎么样才能充分利用缓存?

3. 您是否要搜索整张图直到结束(无限)?您如何决定何时放弃?

4. 在现实生活中，有些人的朋友和朋友的朋友比其他人更多，因此更有可能在你和别人之间建立路径。您如何使用这些数据选择从哪里开始遍历?

- Legolas

---

值得一提的是，这些问题来自Gayle Laakman M.所著的《破解编程面试》一书。 - Andrew

Answer 1

你提出的问题很有趣，也很好奇 :)

1) 当然，数据被存储在硬盘中，而不是RAM中。 硬盘具有防止故障的系统，特别是例如RAID-5。 冗余是关键：如果一个系统失败，就有另一个系统准备好接替它的位置。 还有冗余和工作负载共享一起...有两台计算机并行工作并共享他们的工作，但如果其中一台停止工作，那么只有一台计算机能够工作并承担全部工作量。

在像谷歌或Facebook这样的地方，冗余不是2，而是1200000000 :) 此外，还要考虑数据不在单个服务器上，谷歌有多个数据中心相互连接，因此，如果一栋建筑物爆炸了，就会有另一栋建筑物接替其位置。

2) 这不是一个简单的问题，但通常这些系统也具有大型磁盘阵列缓存，因此读写磁盘上的数据比我们的笔记本电脑更快:) 数据可以由多个并发系统并行处理，这是像Facebook这样的服务速度的关键。

3) 图表的末尾不是无限的。 因此，实际上使用现有技术是可能的。

探索所有连接和所有节点的计算复杂度为O(n + m)，其中n是顶点的数量，m是边的数量。 这意味着它与注册用户的数量和用户之间的连接数成线性增长。而且，现在的RAM非常便宜。

由于是线性增长，因此需要时可以轻松添加资源。 越富裕，就可以添加更多的计算机 :)

还要考虑到，在Facebook中没有人会对每个节点进行真正的搜索，一切都相当“本地化”，您可以查看一个人的直接朋友，而不是朋友的朋友的朋友...那将毫无用处。

如果数据结构做得好，直接连接到顶点的顶点数量很容易快速获取。在SQL中，这将是一个简单的选择，并且如果表被良好索引，它将非常快速，而且也不太依赖用户总数（请参见哈希表的概念）。

- Salvatore Previti