Leg*_*las 11 c oop graph data-structures
在使用Graphs 数据结构设计社交网络的环境中,您可以执行BFS以查找从一个人到另一个人的连接,我有一些与之相关的问题.
如果有数百万用户,拓扑结构确实比我们通常设计的图表复杂得多且相互联系,我试图理解如何解决这些问题.
在现实世界中,服务器失败.这对你有什么影响？
你怎么能利用缓存？
你搜索到图表的结尾(无限)？你怎么决定什么时候放弃？
你的问题似乎很有趣和好奇:)
1)嗯...当然,数据存储在磁盘中,而不是存储在RAM中.磁盘具有避免故障的系统,例如RAID-5.冗余是关键:如果一个系统出现故障,则有另一个系统准备接替他的位置.还有冗余和工作负载共享......有两台计算机并行工作并共享其工作但如果只停止一台工作并承担全部工作量.
在google或facebook这样的地方冗余不是2,是1200000000 :)并且还考虑到数据不在单个服务器场中,在google中有几个数据中心连接在一起,所以如果一个建筑物爆炸,另一个将取代他的位置例.
2)根本不是一个简单的问题,但通常这些系统对磁盘阵列也有很大的缓存,因此在磁盘上读取和写入数据比在我们的笔记本电脑上更快.数据可以由几个并发系统并行处理,这就是像facebook这样的服务速度的关键.
3)图的结尾不是无限的.因此,实际技术确实可行.
探索图上所有连接和所有节点的计算复杂度为O(n + m),其中n是顶点数,m是边数.这意味着,它与注册用户的数量和用户之间的连接数量成线性关系.而这些天的RAM非常便宜.
线性增长很容易在需要时添加资源.你越发富越多,添加更多的电脑:)
还要考虑没有人会对每个节点进行真正的搜索,facebook中的所有内容都是"本地的",你可以查看一个人的直接朋友,而不是朋友朋友的朋友....这样就没用了.
如果数据结构做得好,获得直接连接到顶点的顶点数量非常简单快捷.在SQL中,它将是一个简单的选择,如果表被很好地索引,它将非常快并且也不是非常依赖于用户总数(参见哈希表的概念).