无限级别分佣模式设计

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2206 天前的主题，其中的信息可能已经有所发展或是发生改变。

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 条附言 · 2018-10-27 11:09:43 +08:00

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

邀请

遍历

团长

耗时位

44 条回复 • 2018-11-09 23:13:15 +08:00

moult

2018-10-27 03:31:33 +08:00 via iPhone

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

Olament

2018-10-27 03:32:38 +08:00 via iPhone

Disjoint set?

Olament

2018-10-27 03:37:57 +08:00 via iPhone

@Olament 看错需求了当我没说

whileFalse

2018-10-27 04:03:59 +08:00 via iPhone

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

geelaw

2018-10-27 04:44:58 +08:00 via iPhone

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

gzlock

2018-10-27 05:07:56 +08:00 via Android

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

lovestudykid

2018-10-27 05:35:35 +08:00

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

lovestudykid

2018-10-27 05:53:10 +08:00

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

houlin

2018-10-27 06:08:42 +08:00 via Android

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

ebony0319

2018-10-27 07:12:14 +08:00 via Android

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

jacobz

2018-10-27 07:33:23 +08:00 via iPhone

@ebony0319 并查集不合适吧

xuanbg

2018-10-27 08:54:27 +08:00

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

respect11

2018-10-27 09:03:35 +08:00

mysql 的 closure table

imnpc

2018-10-27 09:03:44 +08:00

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

rockyou12

2018-10-27 09:14:42 +08:00 via Android

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

TangMonk

2018-10-27 09:24:21 +08:00 via Android

递归

Mohanson

2018-10-27 09:27:10 +08:00 via Android

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

Mohanson

2018-10-27 09:28:15 +08:00 via Android

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

Mohanson

2018-10-27 09:29:36 +08:00 via Android

错了，是 trie 树，还没睡醒

abcbuzhiming

2018-10-27 09:40:37 +08:00

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

Conte

2018-10-27 09:41:04 +08:00 via Android

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

2018-10-27 09:51:56 +08:00 via iPhone

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

yidinghe

2018-10-27 09:55:03 +08:00 via Android

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

lyhiving

2018-10-27 10:05:49 +08:00

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

northernlights

2018-10-27 10:32:53 +08:00 via Android

这是传销，犯法的。

lihongjie0209

2018-10-27 11:12:39 +08:00

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

cnkuner

2018-10-27 11:14:33 +08:00 via Android

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

showecho

2018-10-27 11:27:45 +08:00

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

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

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

robinchina

2018-10-27 11:44:42 +08:00

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

robinchina

2018-10-27 11:46:17 +08:00

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

Aruforce

2018-10-27 12:02:29 +08:00 via Android

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

Aruforce

2018-10-27 12:03:29 +08:00 via Android

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

liukanshan

2018-10-27 15:09:53 +08:00

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

简单来说每个用户都存在一个 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

2018-10-27 15:11:35 +08:00

补充上面说的

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

TommyLemon

2018-10-27 15:16:55 +08:00

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

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