左右值无限级分类-阿里云开发者社区

开发者社区> 数据库> 正文

左右值无限级分类

简介:

什么是左右值无限级分类:

左右值无限级分类,也称为预排序树无限级分类,是一种有序的树状结构,位于这些树状结构中的每一个节点都有一个“左值”和“右值”,其规则是:每一个后代节 点的左值总是大于父类,右值总是小于父级,右值总是小于左值。处于这些结 构中的每一个节点,都可以轻易的算出其祖先或后代节点。因此,可以用它来实现无限分类。优点:通过一条SQL就可以获取所有的祖先或后代,这在复杂的分类中非常必要,通过简单的四则运算就可以得到后代的数量.由于这种方法不使用递归查询算法,有更高的查询效率,采用左右值编码的设计方案,在进行类别树的遍历时,由于只需进行2次查询,消除了递归,再加上查询条件都为数字比较,效率极高。这种算法比较高端,是mysql官方推荐的算法
1. 测试数据准备
Java代码  收藏代码
  1. CREATE TABLE `tree` (  
  2.   `id` int(10) NOT NULL AUTO_INCREMENT,  
  3.   `name` varchar(255) NOT NULL,  
  4.   `lft` int(10) NOT NULL DEFAULT '0' COMMENT '左节点',  
  5.   `rgt` int(10) NOT NULL DEFAULT '0' COMMENT '右节点',  
  6.   `status` int(1) NOT NULL DEFAULT '0' COMMENT '逻辑删除 1是 0否',  
  7.   PRIMARY KEY (`id`),  
  8.   KEY `lft` (`lft`),  
  9.   KEY `rgt` (`rgt`),  
  10.   KEY `status` (`status`)  
  11. ) ENGINE=InnoDB DEFAULT CHARSET=utf8;  
  12.   
  13. insert into tree value (null,'Food',1,18,0);  
  14. insert into tree value (null,'Fruit',2,11,0);  
  15. insert into tree value (null,'Red',3,6,0);  
  16. insert into tree value (null,'Cherry',4,5,0);  
  17. insert into tree value (null,'Yellow',7,10,0);  
  18. insert into tree value (null,'Banana',8,9,0);  
  19. insert into tree value (null,'Meat',12,17,0);  
  20. insert into tree value (null,'Beef',13,14,0);  
  21. insert into tree value (null,'Pork',15,16,0);  

我们首先将多级数据按照下面的方式画在纸上

Java代码  收藏代码
  1.                          1 Food 18   
  2.                              |  
  3.             +------------------------------+  
  4.             |                              |  
  5.         2 Fruit 11                     12 Meat 17   
  6.             |                              |  
  7.     +-------------+                 +------------+  
  8.     |             |                 |            |  
  9.  3 Red 6      7 Yellow 10       13 Beef 14   15 Pork 16   
  10.     |             |  
  11. 4 Cherry 5    8 Banana 9     

2. 插入分类思路

两种情况:
插入最顶级节点:它的左右值与该树中最大的右值有关:左值=1,右值=最大右值+2
插入子节点:它的左右值与它的父级有关:左值=父级的右值,右值=当前的左值+1,这时要更新的数据有:父级的右值,所有左值大于父级左级,右值大于低级右值的节点左右值都应该+2;

3. 获取所有的后代节点

从图中可以看出找出某个节点的所有子节点,lft 大于左值 rgt 小于右值
Java代码  收藏代码
  1. SELECT * FROM tree WHERE lft>2 AND rgt<11;  

这个查询得到了以下的结果。

Java代码  收藏代码
  1. +------------+-----+-----+  
  2. |    name    | lft | rgt |  
  3. +------------+-----+-----+  
  4. |    Red     | 3   |  6  |  
  5. |    Cherry  | 4   |  5  |  
  6. |    Yellow  | 7   | 10  |  
  7. |    Banana  | 8   |  9  |  
  8. +------------+-----+-----+  

4. 计算所有子类的数量

每有子类节点中每个节点占用两个值,而这些值都是不一样且连续的,那些就可以计算出子代的数量=(右值-左值-1)/2。减少1的原因是排除该节点,你可以想像一个,一个单节点,左值是1,右值是2,没有子类节点,而这时它的右值-左值=1.

5. 检索单一路径

如果我们想知道Cherry 的路径就利用它的左右值4和5来做一个查询。反向也是一样的唯一的区别就是排序是反向的就行了

Java代码  收藏代码
  1. SELECT name FROM tree WHERE lft < 4 AND rgt >5 ORDER BY lft ASC;  
6. 检索所有叶子节点

要检索出叶子节点(一棵树当中没有子结点的结点,称为叶子结点),我们只要查找满足rgt=lft+1的节点

Java代码  收藏代码
  1. select * from tree where rgt = lft + 1;  
7. 获取分类的深度
Java代码  收藏代码
  1. SELECT node.*, (count(parent.name) - 1) AS deep   
  2. FROM tree AS node,tree AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt   
  3. GROUP BY node.name ORDER BY node.lft  
8. 检索节点的直接子节点
可以想象一下,你在零售网站上呈现电子产品的分类。当用户点击分类后,你将要呈现该分类下的产品,同时也需列出该分类下的直接子分类,而不是该分类下的全部分类。为此,我们只呈现该节点及其直接子节点,不再呈现更深层次的节点.如上述获取深度的例子,可以根椐深度来小于等于1获得直接子节点
Java代码  收藏代码
  1. SELECT * FROM (sql7) AS a WHERE a.deep<= 1;  
拿到Fruit的指定一级深度的子分类
Java代码  收藏代码
  1. SELECT * FROM (sql7) AS tt WHERE tt.lft>2 AND tt.rgt<11 AND tt.deep=2 ORDER BY lft   
移动节点及其子节点至节点A下?

设该节点左值$lft , 右值$rgt,其子节点的数目为$count = ($rgt - $lft -1 )/2 , 节点A左值为$A_lft ,

Java代码  收藏代码
  1. UPDATE `tree` SET `rgt`=`rgt`-$rgt-$lft-1 WHERE `rgt`>$rgt AND `rgt`<$A_lft  
  2. UPDATE `tree` SET `lft`=`lft`-$rgt-$lft-1 WHERE `lft`>$rgt AND `lft`<=$A_lft  
  3. UPDATE `tree` SET `lft`=`lft`+$A_lft-$rgt , `rgt`=`rgt`+$A_lft-$rgt WHERE `lft`>=$lft AND `rgt`<=$rgt  

移动多个节点;移动单个节点;删除多个节点;删除单个节点;新增节点

Java代码  收藏代码
  1. <?php  
  2.   
  3. /** 
  4.  *用于移动一个节点(包括子节点) 
  5.  * @param array $pdata = array('id'=>主键,'root'=>名称) 二选一 父节点(为空时插入最大的父节点) 
  6.  * @param array $ndata = array('id'=>主键,'root'=>名称) 二选一 下一个兄弟节点(没有兄弟的时候就不用) 
  7.  * @param array $cdata = array('id'=>主键,'root'=>名称) 二选一 当前待移动的节点 
  8.  */  
  9. function move_tree_all($pdata = array(), $ndata = array(), $cdata = array())  
  10. {  
  11.     $cid = $cdata['id'] ? intval($cdata['id']) : '';  
  12.     $croot = $cdata['root'];  
  13.     if (!$cid && !$croot) return;  
  14.   
  15.     //需自加判断  
  16.     //1、cdata不能为顶级  
  17.     //2、cdata不能比$pdata等级高  
  18.   
  19.     $adata = get_tree_all($cdata); //获取当前移动节点的所有节点  
  20.     delete_tree_all($cdata, 1); //逻辑删除当前移动节点的所有节点  
  21.   
  22.     foreach ($adata as $k => $val) {  
  23.         if ($k != 0) {  
  24.             $pdata = array('root' => $val['parent']);  
  25.             insert_tree($pdata, '', $val['name'], 1);  
  26.         } else { //first  
  27.             insert_tree($pdata, $ndata, $val['name'], 1);  
  28.         }  
  29.     }  
  30. }  
  31.   
  32. /** 
  33.  *用于移动一个节点(不包括子节点) 
  34.  * @param array $pdata = array('id'=>主键,'root'=>名称) 二选一 父节点(为空时插入最大的父节点) 
  35.  * @param array $ndata = array('id'=>主键,'root'=>名称) 二选一 下一个兄弟节点(没有兄弟的时候就不用) 
  36.  * @param array $cdata = array('id'=>主键,'root'=>名称) 二选一 当前待移动的节点 
  37.  */  
  38. function move_tree_item($pdata = array(), $ndata = array(), $cdata = array())  
  39. {  
  40.     $cid = $cdata['id'] ? intval($cdata['id']) : '';  
  41.     $croot = $cdata['root'];  
  42.     if (!$cid && !$croot) return;  
  43.   
  44.     //需自加判断  
  45.     //1、cdata不能为顶级  
  46.   
  47.     if (!$croot) {  
  48.         $sql = "SELECT name from tree where id = $cid";  
  49.         $result = mysql_query($sql);  
  50.         $row = mysql_fetch_assoc($result);  
  51.         $croot = $row['name'];  
  52.         unset($sql);  
  53.     }  
  54.   
  55.     delete_tree_item($cdata, 1);  
  56.     insert_tree($pdata, $ndata, $croot, 1);  
  57. }  
  58.   
  59. /** 
  60.  *用于插入一个节点 
  61.  * @param array $pdata = array('id'=>主键,'root'=>名称) 二选一 父节点(为空时插入最大的父节点) 
  62.  * @param array $ndata = array('id'=>主键,'root'=>名称) 二选一 下一个兄弟节点(没有兄弟的时候就不用) 
  63.  * @param string $name string 新插入的名称 
  64.  * @param int $update 默认为空,为1时更新插入 
  65.  */  
  66. function insert_tree($pdata = array(), $ndata = array(), $name, $update = '')  
  67. {  
  68.     if (!$name) return;  
  69.   
  70.     $pid = $pdata['id'] ? intval($pdata['id']) : '';  
  71.     $proot = $pdata['root'];  
  72.   
  73.     $nid = $ndata['id'] ? intval($ndata['id']) : '';  
  74.     $nroot = $ndata['root'];  
  75.   
  76.     //有父无兄(最小的子节点,父节点的最后一个儿子)  
  77.     if (($pid || $proot) && !($nid || $nroot)) {  
  78.         $sql = $pid ? "SELECT lft, rgt FROM tree WHERE id = '{$pid}';" : "SELECT lft, rgt FROM tree WHERE name = '{$proot}';";  
  79.         $result = mysql_query($sql);  
  80.         $row = mysql_fetch_assoc($result);  
  81.         unset($sql);  
  82.   
  83.         //新节点  
  84.         $lft = $row['rgt'];  
  85.         $rgt = $lft + 1;  
  86.         if (!$update) {  
  87.             $sql = "insert into tree values (null,'{$name}',$lft,$rgt,0);";  
  88.             $sql1 = "update tree set rgt = rgt+2 where rgt >= {$row['rgt']}";  
  89.             $sql2 = "update tree set lft = lft+2 where lft >= {$row['rgt']}";  
  90.         } else {  
  91.             $sql = "update tree set lft=$lft,rgt=$rgt,status=0 where name ='{$name}';";  
  92.             $sql1 = "update tree set rgt = rgt+2 where status =0 and rgt >= {$row['rgt']}";  
  93.             $sql2 = "update tree set lft = lft+2 where status =0 and lft >= {$row['rgt']}";  
  94.         }  
  95.   
  96.         mysql_query($sql1);  
  97.         mysql_query($sql2);  
  98.         mysql_query($sql); //last add new data  
  99.     }  
  100.   
  101.     //有父有兄  
  102.     if (($pid || $proot) && ($nid || $nroot)) {  
  103.         $sql = $nid ? "SELECT lft, rgt FROM tree WHERE id = '{$nid}';" : "SELECT lft, rgt FROM tree WHERE name = '{$nroot}';";  
  104.         $result = mysql_query($sql);  
  105.         $row = mysql_fetch_assoc($result);  
  106.         unset($sql);  
  107.   
  108.         //新节点  
  109.         $lft = $row['lft'];  
  110.         $rgt = $lft + 1;  
  111.         if (!$update) {  
  112.             $sql = "insert into tree values (null,'{$name}',$lft,$rgt,0);";  
  113.             $sql1 = "update tree set rgt = rgt+2 where rgt >= {$row['lft']};";  
  114.             $sql2 = "update tree set lft = lft+2 where lft >= {$row['lft']};";  
  115.         } else {  
  116.             $sql = "update tree set lft=$lft,rgt=$rgt,status=0 where name ='{$name}';";  
  117.             $sql1 = "update tree set rgt = rgt+2 where status = 0 and rgt >= {$row['lft']};";  
  118.             $sql2 = "update tree set lft = lft+2 where status = 0 and lft >= {$row['lft']};";  
  119.         }  
  120.         mysql_query($sql1);  
  121.         mysql_query($sql2);  
  122.         mysql_query($sql); //last add new data  
  123.     }  
  124.   
  125.     //无父无兄(大佬)  
  126.     if (!($pid || $proot) && !($nid || $nroot)) {  
  127.         $sql = "SELECT max(`rgt`) as rgt FROM tree;";  
  128.         $result = mysql_query($sql);  
  129.         $row = mysql_fetch_assoc($result);  
  130.         unset($sql);  
  131.   
  132.         //新节点  
  133.         $lft = 1;  
  134.         $rgt = $row['rgt'] + 2;  
  135.         if (!$update) {  
  136.             $sql = "insert into tree values (null,'{$name}',$lft,$rgt,0);";  
  137.             $sql1 = "update tree set rgt = rgt+1";  
  138.             $sql2 = "update tree set lft = lft+1";  
  139.         } else {  
  140.             $sql = "update tree set lft=$lft,rgt=$rgt,status=0 where name ='{$name}';";  
  141.             $sql1 = "update tree set rgt = rgt+1 where status = 0";  
  142.             $sql2 = "update tree set lft = lft+1 where status = 0";  
  143.         }  
  144.   
  145.         mysql_query($sql1);  
  146.         mysql_query($sql2);  
  147.         mysql_query($sql); //last add new data  
  148.     }  
  149.   
  150. }  
  151.   
  152. /** 
  153.  *用于删除一个节点(包括子节点) 
  154.  * @param array $data = array('id'=>主键,'root'=>名称) 二选一 
  155.  * @param int $update 默认为空,为1时逻辑删除 
  156.  */  
  157. function delete_tree_all($data, $update = '')  
  158. {  
  159.     $id = $data['id'] ? intval($data['id']) : '';  
  160.     $root = $data['root'];  
  161.     if (!$id && !$root) return;  
  162.   
  163.     $sql = $id ? "SELECT lft, rgt FROM tree WHERE id = '{$id}';" : "SELECT lft, rgt FROM tree WHERE name = '{$root}';";  
  164.     $result = mysql_query($sql);  
  165.     $row = mysql_fetch_assoc($result);  
  166.     unset($sql);  
  167.   
  168.     $middle = $row['rgt'] - $row['lft'] + 1;  
  169.     if (!$update) {  
  170.         $sql = "delete from tree where lft BETWEEN '" . $row['lft'] . "' AND '" . $row['rgt'] . "'";  
  171.         $sql1 = "update tree set rgt = rgt-{$middle} where rgt > {$row['rgt']}";  
  172.         $sql2 = "update tree set lft = lft-{$middle} where lft > {$row['rgt']}";  
  173.     } else {  
  174.         $sql = "update tree set status = 1 where lft BETWEEN '" . $row['lft'] . "' AND '" . $row['rgt'] . "'";  
  175.         $sql1 = "update tree set rgt = rgt-{$middle} where status=0 and rgt > {$row['rgt']}";  
  176.         $sql2 = "update tree set lft = lft-{$middle} where status=0 and lft > {$row['rgt']}";  
  177.     }  
  178.   
  179.     mysql_query($sql);  
  180.     mysql_query($sql1);  
  181.     mysql_query($sql2);  
  182. }  
  183.   
  184. /** 
  185.  *用于删除一个节点(不包括子节点) 
  186.  * @param array $data = array('id'=>主键,'root'=>名称) 二选一 
  187.  * @param int $update 默认为空,为1时逻辑删除 
  188.  */  
  189. function delete_tree_item($data, $update = '')  
  190. {  
  191.     $id = $data['id'] ? intval($data['id']) : '';  
  192.     $root = $data['root'];  
  193.     if (!$id && !$root) return;  
  194.   
  195.     $sql = $id ? "SELECT id,lft, rgt FROM tree WHERE id = '{$id}';" : "SELECT id,lft, rgt FROM tree WHERE name = '{$root}';";  
  196.     $result = mysql_query($sql);  
  197.     $row = mysql_fetch_assoc($result);  
  198.     unset($sql);  
  199.   
  200.     if (!$update) {  
  201.         $sql = "delete from tree where id = {$row['id']};";  
  202.         $sql1 = "update tree set rgt = rgt-1,lft = lft -1 where lft > {$row['lft']} and rgt < {$row['rgt']}";  
  203.         $sql2 = "update tree set lft = lft-2 where lft > {$row['rgt']}";  
  204.         $sql3 = "update tree set rgt = rgt-2 where rgt > {$row['rgt']}";  
  205.     } else {  
  206.         $sql = "update tree set status = 1 where id = {$row['id']};";  
  207.         $sql1 = "update tree set rgt = rgt-1,lft = lft -1 where status = 0 and lft > {$row['lft']} and rgt < {$row['rgt']}";  
  208.         $sql2 = "update tree set lft = lft-2 where status = 0 and lft > {$row['rgt']}";  
  209.         $sql3 = "update tree set rgt = rgt-2 where status = 0 and rgt > {$row['rgt']}";  
  210.     }  
  211.   
  212.     mysql_query($sql);  
  213.     mysql_query($sql1);  
  214.     //can do or not do just right,but not do load empty 2 number in middle  
  215.     mysql_query($sql2);  
  216.     mysql_query($sql3);  
  217. }  
  218.   
  219. /** 
  220.  *用于获取所有的节点 
  221.  * @param array $data = array('id'=>主键,'root'=>名称) 二选一 
  222.  */  
  223. function get_tree_all($data)  
  224. {  
  225.     $id = $data['id'] ? intval($data['id']) : '';  
  226.     $root = $data['root'];  
  227.     if (!$id && !$root) return;  
  228.   
  229.     $sql = $id ? "SELECT lft, rgt FROM tree WHERE id = '{$id}';" : "SELECT lft, rgt FROM tree WHERE name = '{$root}';";  
  230.     $result = mysql_query($sql);  
  231.     $row = mysql_fetch_assoc($result);  
  232.   
  233.     $adata = array(); //所有数据  
  234.     $right = array(); //计数  
  235.     $prev = array();  
  236.     $result = mysql_query("SELECT id,name, lft, rgt FROM tree WHERE lft BETWEEN '" . $row['lft'] . "' AND '" . $row['rgt'] . "' ORDER BY lft ASC ;");  
  237.     while ($row = mysql_fetch_assoc($result)) {  
  238.         if (count($right) > 0) {  
  239.             while ($right[count($right) - 1] < $row['rgt']) { // 检查我们是否应该将节点移出堆栈  
  240.                 array_pop($right);  
  241.                 array_pop($prev);  
  242.             }  
  243.         }  
  244.   
  245.         $parent = $prev ? end($prev) : '';  
  246.         $adata[] = array('id' => $row['id'], 'name' => $row['name'], 'level' => count($right), 'parent' => $parent);  
  247.   
  248.         $right[] = $row['rgt'];  
  249.         $prev[] = $row['name'];  
  250.     }  
  251.     return $adata;  
  252. }  
  253.   
  254. /** 
  255.  *用于展示分类 
  256.  * @param array $data = array('id'=>主键,'root'=>名称) 二选一 
  257.  */  
  258. function display_tree($data)  
  259. {  
  260.     $id = $data['id'] ? intval($data['id']) : '';  
  261.     $root = $data['root'];  
  262.     if (!$id && !$root) return;  
  263.   
  264.     $sql = $id ? "SELECT lft, rgt FROM tree WHERE id = '{$id}';" : "SELECT lft, rgt FROM tree WHERE name = '{$root}';";  
  265.     $result = mysql_query($sql);  
  266.     $row = mysql_fetch_assoc($result);  
  267.   
  268.     $right = array();  
  269.     $result = mysql_query("SELECT name, lft, rgt FROM tree WHERE lft BETWEEN '" . $row['lft'] . "' AND '" . $row['rgt'] . "' ORDER BY lft ASC ;");  
  270.     while ($row = mysql_fetch_assoc($result)) {  
  271.         if (count($right) > 0) { // 检查我们是否应该将节点移出堆栈  
  272.             while ($right[count($right) - 1] < $row['rgt']) {  
  273.                 array_pop($right);  
  274.             }  
  275.         }  
  276.         echo str_repeat('--', count($right)) . $row['name'] . "<br/>";  
  277.         $right[] = $row['rgt'];  
  278.     }  
  279. }  
  280.   
  281. mysql_connect('localhost''root''orbit') or die('connect error');  
  282. mysql_select_db('test') or die('database error');  
  283. mysql_query('set names utf8');  
  284.   
  285. //display_tree(array('root' => 'Food'));  
  286. //display_tree(array('root'=>'bigboss'));  
  287.   
  288. //move_tree_all($pdata=array('root'=>'Fruit'),$ndata=array('root'=>'Red'),$cdata=array('root'=>'Meat'));  
  289. //move_tree_all('','',$cdata=array('root'=>'Meat'));  
  290. //move_tree_item('','',array('root'=>'Red'));  
  291. //move_tree_item(array('root'=>'Red'),array('root'=>'Cherry'),array('root'=>'Fruit'));  
  292.   
  293. //delete_tree_all(array('root'=>'Yellow'));  
  294. //delete_tree_all(array('root'=>'Meat'));  
  295. //delete_tree_item(array('root'=>'Meat'));  
  296.   
  297. //insert_tree('','','bigboss');  
  298. //insert_tree(array('root'=>'Red'),'','dalao');  
  299. //insert_tree(array('root'=>'Red'),array('root'=>'Cherry'),'baddalao');  
  300. //insert_tree(array('root'=>'Fruit'),array('root'=>'Red'),'Redbother');  

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
数据库
使用钉钉扫一扫加入圈子
+ 订阅

分享数据库前沿,解构实战干货,推动数据库技术变革

其他文章