无限级别分佣模式设计

[rootx]

A 邀请了 B C

B 邀请了 D E
C 邀请了 F G

D 邀请了 1 2
E 邀请了 3 4
F 邀请了 5 6
G 邀请了 7 8

当前 A 是团长 BCDEFG12345678 均为会员 因为他们都是 A 这条线带出来的 他们的消费 A 都可以获得佣金

突然 B 升级成为了团长 则需要把 B 这条线带出来的用户都找出来并归给 B：DE1234

查出 B 这条线所有用户 除了数据库记录上级关系 程序用递归法遍历 因为深度未知 所以该方案操作耗时位未知 并且可能随着时间的推移 越顶层的人升级 需要遍历的就越久

还有其他更优雅更快速的方式实现吗？无论是从数据库设计还是程序上。

1.传销的定义：1.收费 2.多级 但该模式只是 2 级 只是数据库存在树型结构而已 而且并没有说要收费
2.这里只是讨论技术和算法问题 如果看不懂还想发表传销言论批判的不要回复

[moult]

这不是花生日记的模式吗？
增加一个字段记录团长 ID，每天凌晨把所有的用户和上下级关系读取出来，没必要的字段就不要查询了，然后递归进行处理就好了，处理环节用不了多少内存和计算资源，就是一开始读取所有用户到内存的时候吃力点，所以要凌晨要批量处理。

[Olament]

Disjoint set?

[Olament]

@Olament 看错需求了 当我没说

[whileFalse]

我记得三级以上的分俑是犯法的？

[geelaw]

缓存你的答案，每次加一个人只会改变高度个数的缓存。

[gzlock]

@whileFalse 所以楼主赶紧辞职或者自首？

[lovestudykid]

@whileFalse 程序员作为正义的化身，自然不受法律约束啦

[lovestudykid]

PS>没有任何针对楼主和楼上诸位技术讨论的意思。只是不认同对法律问题不以为然的态度，以反话对反话。

[houlin]

这个不算三级分销，按照遍历的逻辑，当 B 成为团长时，A 和 B 就已经不是层级关系了，也就是说在规则上如果 B 是团长的话，A 不再从 B 及 B 以下获取佣金就不属于三级分销了。其实这是两个进程，一是人员等级问题，A 的等级树，二是分佣规则的制定，A 获取 B 及以下和 A 仅获取 B 是不同的。那么我们程序在设计的时候其实是在做程序一，而程序二就看产品经理怎么定了

[ebony0319]

查并集。这种一次查询不是很好查，要写一个视图，一个函数。视图实习的功能是查找所有子。函数的功能是从自己开始一层层找上集（从下而上），找到第一个非团长。

[jacobz]

@ebony0319 并查集不合适吧

[xuanbg]

超过 3 级就是传销，楼主赶紧投案自首吧

[respect11]

mysql 的 closure table

[imnpc]

我的做法是只更改 B 以及 B 的下级的 teamid 需要递归处理，
用户表内记录用户的上级 pid 以及 当前所属 teamid，
B 团队离开 A 线，B 的上级 pid 归 0，无限极查询 B 的所有下级 id, 更改 teamid 为 B 的 id
因为这里不递归处理的话 订单那边进行分佣计算的时候也要递归

[rockyou12]

似乎可以考虑用图数据库？

[TangMonk]

递归

[Mohanson]

用 simple merkle tree. A 的 id 是 10， 则 B 的 id 是 10-11, 依次类推，当你找到一个用户，其所有上级都是确定的。

[Mohanson]

千万别用个字段记录上级 id， 这种对数据库的压力是指数级别增长的

[Mohanson]

错了，是 trie 树， 还没睡醒

[abcbuzhiming]

第一，国家现在好像严打多级分佣。
第二，程序员讨论的是技术问题，这个技术问题从本质是如何从理论上无限极的树里把把 1 个节点的子节点全部查出来。记录父 id 的方式是不行的，深度到一定程度后指数级别的增加计算压力，有一种 AB 树的记录方案，但是仍然有弱点。
我也希望能看到更好的算法

[Conte]

原来超过三级就是传销，学到了😁

[zn]

每个人都只有一个上级，有许多个下级，这样的话，实际上结构是一棵树，是否可以考虑维护树状结构？优化得好的话，每个用户占 16 字节左右数据应该够了，这样的话，一亿用户大约只需要 1.5G 内存就可以了。

[yidinghe]

遍历树结构没你想象那么慢，先用笨方法实现没关系。

[lyhiving]

之前有做过，父一级单独记录，父集一个记录，子集一个记录。实际中跑到 199 级没什么压力。

[northernlights]

这是传销，犯法的。

[lihongjie0209]

数据库的树形结构设计可以了解一下

[cnkuner]

你们的下线不会达到数据库瓶颈的。

[showecho]

说传销的建议好好了解一下；

传销最简单的判断方法是 看是不是利用拉下线赚钱；

很明显，lz 的不是，这只是一种激励政策，这种激励政策很多网站在用的。

[robinchina]

@Conte 不是超过三级，是达到三级就算传销

[robinchina]

不要怕慢，电脑很强大的，我在的一个群里面，有人就这么跑，1 万多级都很快，1 万多级全世界的人都不够用啊

[Aruforce]

这样做？每拉一个人则为这个人建立一个团员的列表…同时维护一个树存储人间的关系？对于每个人查团员都是常数复杂度……任何一个人增加团员是的时候只为父级团员表加数据…… 内存消耗比较大

[Aruforce]

@Aruforce 数据不要在数据库里递归…放到本地缓存里面

[liukanshan]

可以考虑下数据嵌套模型 。

简单来说 每个用户都存在一个 left v 和 right v，这两个值来确定层级以及范围关系。

举例来说:

当 A 的 左值: 1 右值: 2 (没有邀请人的状态)

A 这个时候邀请了 B 来看一看这个范围值如何变化

B 节点左值=A.右值
B 节点右值= B.左值+1

最后一步 由于 A 节点插入了一个子节点 需要范围包括 那么 A.右值 = A.右值+2


最终状态就是

A 左值: 1 右值: 4
B 左值: 2 右值: 3


以此类推 。

如果维护起了这套关系 查询子节点信息不需要递归 因为子节点的两边值是一定小于父节点的值 即:

```sql
SELECT * FROM user WHERE lv > parent.lv and rv < parent.rv
```

再来看下 B 邀请了 C

C 节点的左右值和 B 值获取方式一样。

这里不同的是 你需要更改 A 和 B 节点的右值，当然也不需要递归 你只需要找出 lv >= C.lv AND rv < C.lv 然后右值 + 2

最终的状态就是

A 左值: 1 右值: 6
B 左值: 2 右值: 5
C 左值: 3 右值: 4

来查询下 A 一共邀请了多少人？

```
A.右值 / 2 -1 = 2
```


这套模型的关键在于插入和删除 要确保相关的节点值要改变 只要能做到这一点 理论支持无限极分销 并且查询并不需要递归。

希望能帮到你。

[liukanshan]

补充上面说的

推荐使用存储过程进行插入和节点的删除

[TommyLemon]

不确定层级就只能递归，不确定每层的内容就只能遍历。
这个需求类似于 评论的评论、文件夹套文件夹 /文件，
已经有开源的算法了，
还支持朋友圈单层评论、QQ 空间动态二级评论等。

github.com/TommyLemon/AbsGrade
创作不易，GitHub 右上角点 Star 支持下吧 ^_^

[takato]

@geelaw 代价是单个新 node 插入操作的最坏情况变成了 O(V)?

[Hilong]

如果是 django 可以了解下 django-tree-beard

[zhzer]

传销？

[colordog]

传销还有一点，收入是不是均来源于下线

[realpg]

传销算法的库超级难写 2333
一个基本的分层结构还好
等你遇到层出不同的奖金制度时候就要崩溃了

[sucks]

[fy]

我记得 PostgreSQL 可以写这种递归遍历统计的语句，再加索引套缓存，完事

[star1cjl]

我有好算法。但是不打算公布。提示一下，时间换空间，空间换时间。自己考虑下吧。

[rootx]

貌似楼上的方案 都不够优