一般社交网站的"friend"是怎么存储的呢？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一般社交网站的"friend"是怎么存储的呢？

一般社交网站的"friend"是怎么存储的呢？# JobHunting - 待字闺中

j*y2013-01-16 08:01

1 楼

比如
A 有 friend B , C
B 有 friend A, D
C 有 friend A E
D 有 friend B.
E 有 freind C
friend 是相互的， A 是 B的friend那么B 一定也是 A的 friend
首先每个用户有一个唯一的 ID
给每个用户创建一个 friend list,friend list 里面存储的就是 ID, 就变成了 graph
的 adjacency-list 的表示，每个 list可以通过用户 id排序，那么找两个人的共同
朋友的话，线性搜索就可衣做到。不知道有没有更好的方法存储。
linkedin 里面的 1st connection 容易实现，它的 2nd connection, 3rd
connection,
这个是怎么做到的呢。
比如 A 加了 B, 那么 B 的 friend list 里面所有不是 A的friend的话，就加到 A 的
2nd connection list里面，但是感觉这么做会有冲突，比如一个人这么看是 A 的
2nd
connection, 那么看会是 A 的 3rd connection, 怎么 resolve.
不是面试题目，只是想想, 呵呵 :)

l*a2013-01-16 08:01

2 楼

多级不就是图吗？或者多叉树
你说的那个情况PM定义需求，developer实现。
怎么解决都可以

graph

【在 j*****y 的大作中提到】

: 比如
: A 有 friend B , C
: B 有 friend A, D
: C 有 friend A E
: D 有 friend B.
: E 有 freind C
: friend 是相互的， A 是 B的friend那么B 一定也是 A的 friend
: 首先每个用户有一个唯一的 ID
: 给每个用户创建一个 friend list,friend list 里面存储的就是 ID, 就变成了 graph
: 的 adjacency-list 的表示，每个 list可以通过用户 id排序，那么找两个人的共同

j*y2013-01-16 08:01

3 楼

那给定一个 A, B, 如何判断他们中间隔了几个人呢？
不会每次要算一次 shortest path 吧？
那样太慢了。

【在 l*****a 的大作中提到】

: 多级不就是图吗？或者多叉树
: 你说的那个情况PM定义需求，developer实现。
: 怎么解决都可以
:
: graph

l*a2013-01-16 08:01

4 楼

你是FB的PM？
听说他们在搞graph search
你的问题很像他们的需求啊

【在 j*****y 的大作中提到】

: 那给定一个 A, B, 如何判断他们中间隔了几个人呢？
: 不会每次要算一次 shortest path 吧？
: 那样太慢了。