database - 六度分离面试题

Question

A 最近在一次采访中被问到一个有趣的问题。

• 您有 100 万用户
• 每个用户有1000个好友
• 您的系统应该有效地回答每对用户的我认识他吗？ 问题。如果用户通过 6 级 friend 联系在一起，则他们“认识”另一个用户。

例如A是B的 friend ，B是C的 friend ，C是D 的 friend ，D 是E 的 friend ，E 是F 的 friend 。所以我们可以说，A 知道 F。

显然，您无法使用 BFS 或其他标准遍历技术有效地解决此问题。问题是 - 如何将此数据结构存储在数据库中以及如何快速执行此搜索。

Answer 1

BFS 有什么问题？

从第一个节点开始执行三步BFS，用flag 1标记可访问用户，需要10^9步。

从第二个节点开始执行三步BFS，用flag 2标记可访问用户。如果遇到标记1 - bingo。