V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
rootx
V2EX  ›  程序员

无限级别分佣模式设计

  •  2
     
  •   rootx · 2018-10-27 03:10:14 +08:00 · 8570 次点击
    这是一个创建于 1979 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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
        1
    moult  
       2018-10-27 03:31:33 +08:00 via iPhone   ❤️ 1
    这不是花生日记的模式吗?
    增加一个字段记录团长 ID,每天凌晨把所有的用户和上下级关系读取出来,没必要的字段就不要查询了,然后递归进行处理就好了,处理环节用不了多少内存和计算资源,就是一开始读取所有用户到内存的时候吃力点,所以要凌晨要批量处理。
    Olament
        2
    Olament  
       2018-10-27 03:32:38 +08:00 via iPhone
    Disjoint set?
    Olament
        3
    Olament  
       2018-10-27 03:37:57 +08:00 via iPhone
    @Olament 看错需求了 当我没说
    whileFalse
        4
    whileFalse  
       2018-10-27 04:03:59 +08:00 via iPhone
    我记得三级以上的分俑是犯法的?
    geelaw
        5
    geelaw  
       2018-10-27 04:44:58 +08:00 via iPhone
    缓存你的答案,每次加一个人只会改变高度个数的缓存。
    gzlock
        6
    gzlock  
       2018-10-27 05:07:56 +08:00 via Android
    @whileFalse 所以楼主赶紧辞职或者自首?
    lovestudykid
        7
    lovestudykid  
       2018-10-27 05:35:35 +08:00
    @whileFalse 程序员作为正义的化身,自然不受法律约束啦
    lovestudykid
        8
    lovestudykid  
       2018-10-27 05:53:10 +08:00
    PS>没有任何针对楼主和楼上诸位技术讨论的意思。只是不认同对法律问题不以为然的态度,以反话对反话。
    houlin
        9
    houlin  
       2018-10-27 06:08:42 +08:00 via Android
    这个不算三级分销,按照遍历的逻辑,当 B 成为团长时,A 和 B 就已经不是层级关系了,也就是说在规则上如果 B 是团长的话,A 不再从 B 及 B 以下获取佣金就不属于三级分销了。其实这是两个进程,一是人员等级问题,A 的等级树,二是分佣规则的制定,A 获取 B 及以下和 A 仅获取 B 是不同的。那么我们程序在设计的时候其实是在做程序一,而程序二就看产品经理怎么定了
    ebony0319
        10
    ebony0319  
       2018-10-27 07:12:14 +08:00 via Android
    查并集。这种一次查询不是很好查,要写一个视图,一个函数。视图实习的功能是查找所有子。函数的功能是从自己开始一层层找上集(从下而上),找到第一个非团长。
    jacobz
        11
    jacobz  
       2018-10-27 07:33:23 +08:00 via iPhone
    @ebony0319 并查集不合适吧
    xuanbg
        12
    xuanbg  
       2018-10-27 08:54:27 +08:00   ❤️ 1
    超过 3 级就是传销,楼主赶紧投案自首吧
    respect11
        13
    respect11  
       2018-10-27 09:03:35 +08:00
    mysql 的 closure table
    imnpc
        14
    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
        15
    rockyou12  
       2018-10-27 09:14:42 +08:00 via Android
    似乎可以考虑用图数据库?
    TangMonk
        16
    TangMonk  
       2018-10-27 09:24:21 +08:00 via Android
    递归
    Mohanson
        17
    Mohanson  
       2018-10-27 09:27:10 +08:00 via Android
    用 simple merkle tree. A 的 id 是 10, 则 B 的 id 是 10-11, 依次类推,当你找到一个用户,其所有上级都是确定的。
    Mohanson
        18
    Mohanson  
       2018-10-27 09:28:15 +08:00 via Android
    千万别用个字段记录上级 id, 这种对数据库的压力是指数级别增长的
    Mohanson
        19
    Mohanson  
       2018-10-27 09:29:36 +08:00 via Android
    错了,是 trie 树, 还没睡醒
    abcbuzhiming
        20
    abcbuzhiming  
       2018-10-27 09:40:37 +08:00
    第一,国家现在好像严打多级分佣。
    第二,程序员讨论的是技术问题,这个技术问题从本质是如何从理论上无限极的树里把把 1 个节点的子节点全部查出来。记录父 id 的方式是不行的,深度到一定程度后指数级别的增加计算压力,有一种 AB 树的记录方案,但是仍然有弱点。
    我也希望能看到更好的算法
    Conte
        21
    Conte  
       2018-10-27 09:41:04 +08:00 via Android
    原来超过三级就是传销,学到了😁
    zn
        22
    zn  
       2018-10-27 09:51:56 +08:00 via iPhone
    每个人都只有一个上级,有许多个下级,这样的话,实际上结构是一棵树,是否可以考虑维护树状结构?优化得好的话,每个用户占 16 字节左右数据应该够了,这样的话,一亿用户大约只需要 1.5G 内存就可以了。
    yidinghe
        23
    yidinghe  
       2018-10-27 09:55:03 +08:00 via Android
    遍历树结构没你想象那么慢,先用笨方法实现没关系。
    lyhiving
        24
    lyhiving  
       2018-10-27 10:05:49 +08:00
    之前有做过,父一级单独记录,父集一个记录,子集一个记录。实际中跑到 199 级没什么压力。
    northernlights
        25
    northernlights  
       2018-10-27 10:32:53 +08:00 via Android
    这是传销,犯法的。
    lihongjie0209
        26
    lihongjie0209  
       2018-10-27 11:12:39 +08:00
    数据库的树形结构设计可以了解一下
    cnkuner
        27
    cnkuner  
       2018-10-27 11:14:33 +08:00 via Android
    你们的下线不会达到数据库瓶颈的。
    showecho
        28
    showecho  
       2018-10-27 11:27:45 +08:00
    说传销的建议好好了解一下;

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

    很明显,lz 的不是,这只是一种激励政策,这种激励政策很多网站在用的。
    robinchina
        29
    robinchina  
       2018-10-27 11:44:42 +08:00   ❤️ 2
    @Conte 不是超过三级,是达到三级就算传销
    robinchina
        30
    robinchina  
       2018-10-27 11:46:17 +08:00
    不要怕慢,电脑很强大的,我在的一个群里面,有人就这么跑,1 万多级都很快,1 万多级全世界的人都不够用啊
    Aruforce
        31
    Aruforce  
       2018-10-27 12:02:29 +08:00 via Android
    这样做?每拉一个人则为这个人建立一个团员的列表…同时维护一个树存储人间的关系?对于每个人查团员都是常数复杂度……任何一个人增加团员是的时候只为父级团员表加数据…… 内存消耗比较大
    Aruforce
        32
    Aruforce  
       2018-10-27 12:03:29 +08:00 via Android
    @Aruforce 数据不要在数据库里递归…放到本地缓存里面
    liukanshan
        33
    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
        34
    liukanshan  
       2018-10-27 15:11:35 +08:00
    补充上面说的

    推荐使用存储过程进行插入和节点的删除
    TommyLemon
        35
    TommyLemon  
       2018-10-27 15:16:55 +08:00
    不确定层级就只能递归,不确定每层的内容就只能遍历。
    这个需求类似于 评论的评论、文件夹套文件夹 /文件,
    已经有开源的算法了,
    还支持朋友圈单层评论、QQ 空间动态二级评论等。

    github.com/TommyLemon/AbsGrade
    创作不易,GitHub 右上角点 Star 支持下吧 ^_^
    takato
        36
    takato  
       2018-10-27 15:34:37 +08:00
    @geelaw 代价是单个新 node 插入操作的最坏情况变成了 O(V)?
    Hilong
        37
    Hilong  
       2018-10-27 15:36:01 +08:00 via Android
    如果是 django 可以了解下 django-tree-beard
    zhzer
        38
    zhzer  
       2018-10-27 16:11:30 +08:00 via Android
    传销?
    colordog
        39
    colordog  
       2018-10-27 16:20:40 +08:00 via iPhone
    传销还有一点,收入是不是均来源于下线
    realpg
        40
    realpg  
       2018-10-27 16:31:46 +08:00
    传销算法的库超级难写 2333
    一个基本的分层结构还好
    等你遇到层出不同的奖金制度时候就要崩溃了
    sucks
        41
    sucks  
       2018-10-27 17:13:16 +08:00
    fy
        42
    fy  
       2018-10-27 19:34:10 +08:00
    我记得 PostgreSQL 可以写这种递归遍历统计的语句,再加索引套缓存,完事
    star1cjl
        43
    star1cjl  
       2018-10-28 00:51:41 +08:00
    我有好算法。但是不打算公布。提示一下,时间换空间,空间换时间。自己考虑下吧。
    rootx
        44
    rootx  
    OP
       2018-11-09 23:13:15 +08:00
    貌似楼上的方案 都不够优
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3185 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 13:04 · PVG 21:04 · LAX 06:04 · JFK 09:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.