sns好友算法

最近研究sns的好友系统，才慢慢理解了六度分割中的度的概念，比如：我跟你是好友，咱们之间的度就是1，你的好友呢，也就是我的好友的好友，那我们之间的度就是2，相当于隔了多少层。
比如我有个好友表：（以双向好友表为例）

user_id friend_id
1         2
1         3
2         1
2         3
3         1  
3         2
3         4

如果我的id是1 那么我的好友就是2,3 也就是

select friend_id from xxx where user_id=1

这句话就是查看我的直接好友，也就是一度好友
那么查看二度好友呢 就在循环遍历一遍 也就是查找我的好友的好友
而好友关系是这样 A->B->C C是A的二度好友
也就是

select friend_id from xxx where user_id in (select friend_id from xxx where user_id=1)

这是id为1的二度好友 可是如果A->C 那个C与A认识 ABC互相认识，C既可以是A的一度好友也可以是A的二度好友，这时就看要求了，如果要是只查二度好友，就可以用上面的句子，如果要是想看不认识的二度好友，就像人人网的好友推荐那样，还要在上面的结果中把A的好友去除，也就是

select friend_id from xxx where user_id in (select friend_id from xxx where user_id=1) and friend_id not in(select friend_id from xxx where user_id=1)

括号内为一度好友查询
恩 这样就是不认识的二度好友了
看到这里大家也应该明白了 二度好友就是在一度好友的情况下 在遍历一遍 如果每个人的好友有n个 那么你的二度好友就是n*n个
现实世界中假设你的好友有100个 肯定比这个多 那么二度好友就是10000个（先不排除认识二度好友） 那么6度好友就是100^6 1万亿 地球上才几十亿 也就是这个道理
废话不说 继续跟着上述的SQL  根据sql出的结果是二度好友数 可是还有情况是好友是自己 也就是循环一圈回来了- -！ 因为是双向好友表嘛 需要在结果中把自己的id去掉

select friend_id from xxx where user_id in (select friend_id from xxx where user_id=1) and friend_id not in(select friend_id from xxx where user_id=1) and friend_id <> 1

括号内为一度好友查询
可以根据group by 分下组 就知道了自己不认识的人 和自己有多少个共同好友 也就是人人的好友推荐了
如果要是查询两人的共同好友，我又要开一贴了，况且我这是sql数据库 人人好像用的nosql，想不管这么多 写完了
欢迎大家提意见

评论

2 楼 happyprogram 2012-04-17  

这种效率是很低的，要是在大数据量的情况下，恐怕db就要崩溃了。

1 楼 tsxm 2011-08-04  

这个db受的了吗