朋友圈裂变算法 2018-04-03

问题定义：
什么是裂变，举例：
A下完订单之后，分享到朋友圈，B是A的朋友，B又在平台下单。

当前裂变运营：拼团，砍价，刷脸等等玩法。

那么问题是如何简单有效的去查询裂变效果呢？？

正常情况，裂变算法都是后补的，有几种方案。
第一种，直接拿关联数据进行查询，A-B-C-D，构建这种树形结构。
SQl：估计写出这种SQL的大神少之又少，太复杂了，首先是需要找到源头的ROOT节点，
可以用时间进行排序，之后根据每一个ROOT递归往下查。随着订单量增大，这种算法，几乎是被判死刑，不用实际运行也会被枪毙。

第二种：用遍历的路径搜索算法

A<-B->C
找到任意一节点，先向上不断搜索，验证是否下单，之后向下递归。向上找到root，向下找到最新的。
缺点：
1：不能实时更新。
2：需要都放到内存中。
随着订单量增多，这个方案也不可取，订单量小，可以尝试。

最终我们采取的方案：

是一种最小生成树的一种思想，
由于是后补充的算法，首先要解决就是性能问题，第二要解决的就是实时性问题。
性能问题最优肯定是O（N），每次只是遍历一颗树，不是加载所有订单，所有关系链，而且不会随着订单整体规模增大成指数增长。

详细描述：
数据结构设计：
【会员ID
树的高度（朋友的深度）
朋友们IDS】
树的高度：用户是ROOT（第一次购买，没有朋友）高度为1，上面有一个朋友则是2.如图：

裂变树.png

图：root裂变数：4

1：我们新增一单L4，就会查询一下该用户是否是新客，是否是其他会员的朋友。
2：如果确认他是其他会员的朋友，就递归向上。
1）：L4深度最浅，它的高度为1
2）：它的上一层最低高度是2如果原来值得小于2则加到2，如果大于2则保持不变。如何朋友里面有L4则忽略，没有进行添加。
3）：递归重复第二步判断
4）：递归到root 截止

这样算法复杂度只有O（N）但是可以迅速补充裂变指数。