计算按行分组的左右总子节点数
use*_*633 8 mysql sql binary-tree hierarchical-data binary-search-tree
我正在开展一个奖励人们推荐的项目(MLM)
我已经能够计算左侧和右侧的子节点总数,但现在我需要能够更新用户的等级,当他们有一定数量的用户时,他们两侧的某些等级低于他们.(我将在下面解释得更好:
用户表
id | name | parentID| side | rank |
4 | Dan | | | starter|
5 | Chris | 4 | left | starter|
6 | James | 4 | right| starter|
7 | Tybe | 5 | left | starter|
8 | Rose | 5 | right| starter|
9 | Paul | 6 | left | starter|
10 | Zach | 6 | right| starter|
树桌
userID | left | right| leftCount | rightCount|
4 | 5 | 6 | 3 | 3 |
5 | 7 | 8 | 1 | 1 |
6 | 9 | 10 | 1 | 1 |
7 | | | 0 | 0 |
8 | | | 0 | 0 |
9 | | | 0 | 0 |
10 | | | 0 | 0 |
下面是从该表生成的树
我如何在用户注册时更新leftCount和rightCount
$referralid; //who is referring the current user
$side; //the side the user is to fall under, either left or right
$temp_referralid = $referralid;
$temp_sideCount = $side.'Count'; //leftCount or rightCount
$temp_side = $side;
$total_count=1;
$i=1;
while($total_count>0){
$stmt = $db->prepare("SELECT * from tree WHERE id=:id");
$stmt->bindValue(':id', $temp_referralid);
$stmt->execute();
$r = $stmt->fetch(PDO::FETCH_ASSOC);
$current_temp_sideCount = ($r[$temp_sideCount]+1);
//This will add (+1) to the leftCount or rightCount
//of the referral depending on the side the user
//choose to fall under.
$sql ="UPDATE `tree` SET `$temp_sideCount`=:count WHERE `id` = :id";
$stmt = $db->prepare($sql);
$stmt->bindValue(':count', $current_temp_sideCount);
$stmt->bindValue(':id', $temp_referralid);
$stmt->execute();
//if the user has someone that referred them as
//only the last person at the top has no referral
if($temp_referralid!=""){
//change the $referralid to the person that referred the person
//referring this user. this is where the loop will go through
//to the last person maintaining the side upward
$next_referralid = $this->getReferringId($db, $temp_referralid);
$temp_side = $this->getReferringIdSide($db, $temp_referralid);
$temp_sideCount = $temp_side.'Count';
$temp_referralid = $next_referralid;
$i++;
}else{
$total_count=0;
}
}
}
使用的功能
getReferringId($db, $id) //gets the referringId of the user passed as
//param from the user table
getReferringIdSide($db, $id) //gets the side which the user
//is on (left or right) from the user table
所有这一切都很好,但后来我需要实现一些东西,我没有找到最好的方法.
如果每个用户已达到阶段,我需要不断更改等级.见下面和例子:
stage 1: starter //just registered
stage 2: grow // the person has leftCount=3 and rightCount=3
stage 3: growbig //the person has 7 - grow user on the left
//and 7- grow user on the right
state 4: growbigger //the person has 7 - growbig on left and 7 growbig
//on the right
到第2阶段,我没有问题,但向上是我无法掌握正确逻辑的地方
例如更新:growbig的数量可以来自腿上的任何地方,它不应该只是直接节点,只是在每个方面都低于该用户的等级数
更新:重新询问更清晰的术语和规范
它是一棵二叉树(2:2),这意味着一个人只能在他们下面有两个人(一个在左边,另一个在右边).
上面的图片我的表看起来像这样
树桌
userID | left (userid) | right (userid)| rank
8 | 4 | 12 |
4 | 2 | 6 |
12 | 10 | 14 |
2 | 1 | 3 |
6 | 5 | 7 |
10 | 9 | 11 |
14 | 14 | 15 |
注意:对于用户而言,任何一方或两者都不得使用任何人.这意味着如果一个用户在他下面没有人,那么树(分支)就在那里结束,如果他有一个人直接在左边而没有在右边那意味着左分支可以继续增长.
每个用户根据他们的增长进行评级的逻辑以及他们如何设法平衡每一方的增长是一个问题.
逻辑
等级1:主管:用户必须在其右侧分支上有3个用户,在左侧分支上有3个用户.
等级2:控制器:用户必须有7个用户,他们是左侧的"主管",7个用户也是右侧的主管.
等级3:高级控制器:用户必须有7个用户,他们在左侧分支上是"控制器",右侧也有7个"控制器".
等级4:大使:用户必须有7个用户,左边是高级控制员,右边是7个高级控制员
等级5:高级大使:用户必须有7个用户,左边是大使,右边是大使.
等级6:大使:用户必须有7位用户,他们都是双方的高级大使.
说明: 让我挑选等级并解释它:
排名:大使 - 如果ID为3的用户右侧有45人,右侧分支有7人是高级管制员,左侧有67人,7人已经是高级管制员,那么ID为3的用户应该升级为'大使'
@blag
这更可能是我处理这个问题的方式（使用http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/）：
\n\n新的表架构是：
\n\n\'id\'| \'name\' | \'left\'| \'right\'| \'rank\' \n4 | \'Dan\' | 1 | 14 | \'starter\'\n5 | \'Chris\'| 2 | 7 | \'starter\'\n6 | \'James\'| 8 | 13 | \'starter\'\n7 | \'Tybe\' | 3 | 4 | \'starter\'\n8 | \'Rose\' | 5 | 6 | \'starter\'\n9 | \'Paul\' | 9 | 10 | \'starter\'\n10 | \'Zach\' | 11 | 12 | \'starter\'\n完整版：
\n\n请注意，我使用以下值来避免使用更大的数据集
\n\n-- on each side \nset @grow = 1 // -- 1 child R & L\nset @growbig = 2 // -- 2 grow child R & L\n程序
\n\nCREATE PROCEDURE p(IN p_parent varchar(15), IN p_children varchar(15))\nBEGIN\n IF NOT EXISTS (\n select parent.*, count(distinct dc.id) direct_child\n from u parent\n left join u as dc on(parent.left=dc.left-1 or parent.right=dc.right+1)\n WHERE parent.name = p_parent\n group by parent.id\n having count(distinct dc.id) =2\n )\n THEN\n SET @myLeft =(SELECT `left` FROM u WHERE name = p_parent);\n\n UPDATE u SET `right` = `right` + 2 WHERE `right` > @myLeft;\n UPDATE u SET `left` = `left` + 2 WHERE `left` > @myLeft;\n\n INSERT INTO u(`name`, `left`, `right`) \n VALUES(p_children, @myLeft + 1, @myLeft + 2);\n\n END IF;\nEND\n//\n\n\ncall p(\'Tybe\',\'Marjorie\') //\ncall p(\'Tybe\',\'Vernon\') //\ncall p(\'Rose\',\'Marc\') //\ncall p(\'Rose\',\'Peter\') //\ncall p(\'Marc\',\'Lily\') //\ncall p(\'Marc\',\'Ignotus\') //\ncall p(\'Ignotus\',\'Aragorn\') //\ncall p(\'Ignotus\',\'Arwen\') //\ncall p(\'Peter\',\'Chase\') //\ncall p(\'Peter\',\'Foreman\') //\ncall p(\'Chase\',\'P\xc3\xa9tunia\') //\ncall p(\'Chase\',\'Dudley\') //\ncall p(\'Foreman\',\'Bob\') //\ncall p(\'Foreman\',\'Taub\') //\ncall p(\'Paul\',\'Lisa\') //\ncall p(\'Paul\',\'Bilbo\') //\ncall p(\'Lisa\',\'House\') //\ncall p(\'Lisa\',\'Gandalf\') //\ncall p(\'Gandalf\',\'Frodo\') //\ncall p(\'Gandalf\',\'Legolas\') //\ncall p(\'House\',\'Thirteen\') //\ncall p(\'House\',\'Wilson\') //\ncall p(\'Thirteen\',\'Ginny\') //\ncall p(\'Thirteen\',\'Harry\') //\ncall p(\'Wilson\',\'Kutner\') //\ncall p(\'Wilson\',\'Master\') //\ncall p(\'Master\',\'Adams\') //\ncall p(\'Master\',\'Park\') //\ncall p(\'Zach\',\'Ary\') //\n生长
\n\nset @grow = 1 //\nupdate u\nset rank = \'grow\'\nwhere u.id in (\n select id from ( \n select id \n from (\n select p.id id, p.name name, lc.id lcid, null rcid\n from u p\n inner join u l on (p.left = l.left-1 and p.right <> l.right+1)\n inner join u lc on (lc.left >= l.left and lc.right <= l.right)\n inner join u r on (p.right = r.right+1 and p.left <> r.left-1)\n\n union all\n\n select p.id id, p.name name, null lcid, rc.id rcid\n from u p\n inner join u l on (p.left = l.left-1 and p.right <> l.right+1)\n inner join u r on (p.right = r.right+1 and p.left <> r.left-1)\n inner join u rc on (rc.left >= r.left and rc.right <= r.right)\n ) p\n group by p.id\n having \n count(distinct lcid) >= @grow\n and count(distinct rcid) >= @grow\n ) z\n)\n//\n长大
\n\nset @growbig = 2 //\nupdate u\nset rank = \'growbig\'\nwhere u.id in (\n select id from ( \n select id \n from (\n select p.id id, p.name name, lc.id lcid, null rcid\n from u p\n inner join u l on (p.left = l.left-1 and p.right <> l.right+1)\n inner join u lc on (lc.rank =\'grow\' and lc.left >= l.left and lc.right <= l.right)\n inner join u r on (p.right = r.right+1 and p.left <> r.left-1)\n\n union all\n\n select p.id id, p.name name, null lcid, rc.id rcid\n from u p\n inner join u l on (p.left = l.left-1 and p.right <> l.right+1)\n inner join u r on (p.right = r.right+1 and p.left <> r.left-1)\n inner join u rc on (rc.rank =\'grow\' and rc.left >= r.left and rc.right <= r.right)\n ) p\n group by p.id\n having \n count(distinct lcid) >= @growbig\n and count(distinct rcid) >= @growbig\n ) z\n)\n\n//\n查询1：
\n\n-- output parent that have both right and left child\nselect parent.*, count(distinct dc.id) direct_child\nfrom u parent\nleft join u as dc on(parent.left=dc.left-1 or parent.right=dc.right+1)\ngroup by parent.id\nhaving count(distinct dc.id) =2\n结果：
\n\n| id | name | left | right | rank | direct_child |\n|----|----------|------|-------|---------|--------------|\n| 4 | Dan | 1 | 72 | growbig | 2 |\n| 5 | Chris | 2 | 35 | grow | 2 |\n| 6 | James | 36 | 71 | grow | 2 |\n| 7 | Tybe | 3 | 8 | grow | 2 |\n| 8 | Rose | 9 | 34 | growbig | 2 |\n| 9 | Paul | 37 | 66 | grow | 2 |\n| 13 | Marc | 24 | 33 | grow | 2 |\n| 14 | Peter | 10 | 23 | grow | 2 |\n| 16 | Ignotus | 25 | 30 | grow | 2 |\n| 19 | Chase | 17 | 22 | grow | 2 |\n| 20 | Foreman | 11 | 16 | grow | 2 |\n| 25 | Lisa | 40 | 65 | grow | 2 |\n| 27 | House | 47 | 64 | grow | 2 |\n| 28 | Gandalf | 41 | 46 | grow | 2 |\n| 31 | Thirteen | 58 | 63 | grow | 2 |\n| 32 | Wilson | 48 | 57 | grow | 2 |\n| 36 | Master | 49 | 54 | grow | 2 |\n查询2：
\n\n-- show the tree\nSELECT CONCAT( REPEAT(\'|...\', COUNT(parent.name) - 1), node.id, \' \', node.name,\' /\',node.rank) AS name \nFROM u AS node,\n u AS parent \nWHERE node.left BETWEEN parent.left AND parent.right\nGROUP BY node.name\nORDER BY node.left\n结果：
\n\n| name |\n|-----------------------------------------------|\n|4 Dan /growbig |\n||...5 Chris /grow |\n||...|...7 Tybe /grow |\n||...|...|...12 Vernon /starter |\n||...|...|...11 Marjorie /starter |\n||...|...8 Rose /growbig |\n||...|...|...14 Peter /grow |\n||...|...|...|...20 Foreman /grow |\n||...|...|...|...|...24 Taub /starter |\n||...|...|...|...|...23 Bob /starter |\n||...|...|...|...19 Chase /grow |\n||...|...|...|...|...22 Dudley /starter |\n||...|...|...|...|...21 P\xc3\xa9tunia /starter |\n||...|...|...13 Marc /grow |\n||...|...|...|...16 Ignotus /grow |\n||...|...|...|...|...18 Arwen /starter |\n||...|...|...|...|...17 Aragorn /starter |\n||...|...|...|...15 Lily /starter |\n||...6 James /grow |\n||...|...9 Paul /grow |\n||...|...|...26 Bilbo /starter |\n||...|...|...25 Lisa /grow |\n||...|...|...|...28 Gandalf /grow |\n||...|...|...|...|...30 Legolas /starter |\n||...|...|...|...|...29 Frodo /starter |\n||...|...|...|...27 House /grow |\n||...|...|...|...|...32 Wilson /grow |\n||...|...|...|...|...|...36 Master /grow |\n||...|...|...|...|...|...|...38 Park /starter |\n||...|...|...|...|...|...|...37 Adams /starter |\n||...|...|...|...|...|...35 Kutner /starter |\n||...|...|...|...|...31 Thirteen /grow |\n||...|...|...|...|...|...34 Harry /starter |\n||...|...|...|...|...|...33 Ginny /starter |\n||...|...10 Zach /starter |\n||...|...|...39 Ary /starter |\n查询3：
\n\n-- show parent + child data\nselect *,(l.right - l.left -1)/2 l , (r.right - r.left -1)/2 r from u p\ninner join u l on (p.left = l.left-1 and p.right <> l.right+1)\ninner join u r on (p.right = r.right+1 and p.left <> r.left-1)\n结果：
\n\n| id | name | left | right | rank | id | name | left | right | rank | id | name | left | right | rank | l | r |\n|----|----------|------|-------|---------|----|---------|------|-------|---------|----|----------|------|-------|---------|----|----|\n| 4 | Dan | 1 | 72 | growbig | 5 | Chris | 2 | 35 | grow | 6 | James | 36 | 71 | grow | 16 | 17 |\n| 5 | Chris | 2 | 35 | grow | 7 | Tybe | 3 | 8 | grow | 8 | Rose | 9 | 34 | growbig | 2 | 12 |\n| 6 | James | 36 | 71 | grow | 9 | Paul | 37 | 66 | grow | 10 | Zach | 67 | 70 | starter | 14 | 1 |\n| 7 | Tybe | 3 | 8 | grow | 12 | Vernon | 4 | 5 | starter | 11 | Marjorie | 6 | 7 | starter | 0 | 0 |\n| 8 | Rose | 9 | 34 | growbig | 14 | Peter | 10 | 23 | grow | 13 | Marc | 24 | 33 | grow | 6 | 4 |\n| 13 | Marc | 24 | 33 | grow | 16 | Ignotus | 25 | 30 | grow | 15 | Lily | 31 | 32 | starter | 2 | 0 |\n| 16 | Ignotus | 25 | 30 | grow | 18 | Arwen | 26 | 27 | starter | 17 | Aragorn | 28 | 29 | starter | 0 | 0 |\n| 14 | Peter | 10 | 23 | grow | 20 | Foreman | 11 | 16 | grow | 19 | Chase | 17 | 22 | grow | 2 | 2 |\n| 19 | Chase | 17 | 22 | grow | 22 | Dudley | 18 | 19 | starter | 21 | P\xc3\xa9tunia | 20 | 21 | starter | 0 | 0 |\n| 20 | Foreman | 11 | 16 | grow | 24 | Taub | 12 | 13 | starter | 23 | Bob | 14 | 15 | starter | 0 | 0 |\n| 9 | Paul | 37 | 66 | grow | 26 | Bilbo | 38 | 39 | starter | 25 | Lisa | 40 | 65 | grow | 0 | 12 |\n| 25 | Lisa | 40 | 65 | grow | 28 | Gandalf | 41 | 46 | grow | 27 | House | 47 | 64 | grow | 2 | 8 |\n| 28 | Gandalf | 41 | 46 | grow | 30 | Legolas | 42 | 43 | starter | 29 | Frodo | 44 | 45 | starter | 0 | 0 |\n| 27 | House | 47 | 64 | grow | 32 | Wilson | 48 | 57 | grow | 31 | Thirteen | 58 | 63 | grow | 4 | 2 |\n| 31 | Thirteen | 58 | 63 | grow | 34 | Harry | 59 | 60 | starter | 33 | Ginny | 61 | 62 | starter | 0 | 0 |\n| 32 | Wilson | 48 | 57 | grow | 36 | Master | 49 | 54 | grow | 35 | Kutner | 55 | 56 | starter | 2 | 0 |\n| 36 | Master | 49 | 54 | grow | 38 | Park | 50 | 51 | starter | 37 | Adams | 52 | 53 | starter | 0 | 0 |\n| 归档时间： |
|
| 查看次数： |
1122 次 |
| 最近记录： |