预排序树实现无限极分类

概念

• 左右值无限级分类，也称为预排序树无限级分类
• 是一种有序的树状结构
• 于这些树状结构中的每一个节点都有一个 左值 和 右值

规则

• 每一个 后代节点 的 左值 > 父节点 的 左值
• 每一个 后代节点 的 右值 < 父节点的 右值
• 每一个节点的 右值 > 左值

新增节点

新增顶级分类

• 获取该树中 最大右值;
• 左值 = 最大右值 + 1;
• 右值 = 最大右值 + 2;

新增子节点

• 首先获取 父节点右值

UPDATE `catagory` SET `lft` = `lft`+2 WHERE `lft`>`父节点右值`;
UPDATE `catagory` SET `rgt` = `rgt` + 2 WHERE `rgt`>= `父节点右值`

新增节点左值 = 父节点右值

新增节点右值 = 新增节点左值 + 1

删除节点

获取删除节点的左右值 $lft, $rgt

删除该节点以及所有后代节点

DELETE FROM `catagory` WHERE `lft`>=$lft AND `rgt`<=$Rgt"

更新左右值

$Value=$rgt-$lft+1;
UPDATE `catagory` SET `lft`=`lft`- $Value WHERE `lft`>$lft
UPDATE `catagory` SET `rgt`=`rgt`- $Value WHERE `rgt`>$rgt"

数据准备

CREATE TABLE `nested_category` (
`category_id` int(10) NOT NULL AUTO_INCREMENT COMMENT '自增ID',
`name` varchar(18) COLLATE utf8_unicode_ci NOT NULL DEFAULT '' COMMENT '名称',
 `lft` int(4) NOT NULL,  `rgt` int(4) NOT NULL,
  KEY `category_id` (`category_id`)
) ENGINE=InnoDB AUTO_INCREMENT=14 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;
INSERT INTO `nested_category` VALUES    
(1,'商品',1,26),    
(2,'化妆品',2,7),    
(3,'食品',8,9),    
(4,'酒',10,15),    
(5,'服装',16,17),    
(6,'家电',18,23),    
(7,'鞋帽',24,25),    
(8,'面霜',3,4),    
(9,'面膜',5,6),    
(10,'白酒',11,12),    
(11,'红酒',13,14),    
(12,'冰箱',19,20),    
(13,'空调',21,22);    

数据查看    
mysql> select * from nested_category;    
+-------------+-----------+-----+-----+    
| category_id | name      | lft | rgt |    
+-------------+-----------+-----+-----+    
|           1 | 商品    |   1 |  26 |    
|           2 | 化妆品 |   2 |   7 |    
|           3 | 食品    |   8 |   9 |    
|           4 | 酒       |  10 |  15 |    
|           5 | 服装    |  16 |  17 |    
|           6 | 家电    |  18 |  23 |    
|           7 | 鞋帽    |  24 |  25 |    
|           8 | 面霜    |   3 |   4 |    
|           9 | 面膜    |   5 |   6 |    
|          10 | 白酒    |  11 |  12 |    
|          11 | 红酒    |  13 |  14 |    
|          12 | 冰箱    |  19 |  20 |    
|          13 | 空调    |  21 |  22 |    
+-------------+-----------+-----+-----+

获取所有后代节点

select * from nested_category where lft > 18 and rgt < 23;
+-------------+--------+-----+-----+    
| category_id | name   | lft | rgt |    
+-------------+--------+-----+-----+    
|          12 | 冰箱 |  19 |  20 |    
|          13 | 空调 |  21 |  22 |    
+-------------+--------+-----+-----+

计算后代数量

后代的数量 = (右值 - 左值 - 1) / 2。

减少1的原因是排除该节点本身

判断叶子节点

右值 - 左值 = 1

获取叶子节点

mysql> select * from nested_category  where rgt - lft = 1;
+-------------+--------+-----+-----+    
| category_id | name   | lft | rgt |    
+-------------+--------+-----+-----+    
|           3 | 食品   |   8 |   9 |    
|           5 | 服装   |  16 |  17 |    
|           7 | 鞋帽   |  24 |  25 |    
|           8 | 面霜   |   3 |   4 |    
|           9 | 面膜   |   5 |   6 |    
|          10 | 白酒   |  11 |  12 |    
|          11 | 红酒   |  13 |  14 |    
|          12 | 冰箱   |  19 |  20 |    
|          13 | 空调   |  21 |  22 |    
+-------------+--------+-----+-----+

检索单一路径

select 
parent.name,    
parent.category_id,    
parent.lft,    
parent.rgt    
from    
nested_category as node, nested_category as parent    
where    
node.lft between parent.lft and parent.rgt and node.name = '空调'    
order by parent.lft;    
+--------+-------------+-----+-----+    
| name   | category_id | lft | rgt |    
+--------+-------------+-----+-----+    
| 商品 |           1 |   1 |  26 |    
| 家电 |           6 |  18 |  23 |    
| 空调 |          13 |  21 |  22 |    
+--------+-------------+-----+-----+    
3 rows in set (0.00 sec)

检索分类深度

select 
node.name as name,  (count(parent.name) - 1) as deep    
from    
nested_category as node,    
nested_category as parent    
where node.lft between parent.lft and parent.rgt    
group by node.name    
order by node.lft    
+-----------+------+    
| name      | deep |    
+-----------+------+    
| 商品    |    0 |    
| 化妆品 |    1 |    
| 面霜    |    2 |    
| 面膜    |    2 |    
| 食品    |    1 |    
| 酒       |    1 |    
| 白酒    |    2 |    
| 红酒    |    2 |    
| 服装    |    1 |    
| 家电    |    1 |    
| 冰箱    |    2 |    
| 空调    |    2 |    
| 鞋帽    |    1 |    
+-----------+------+    
13 rows in set (0.03 sec)

检索某个节点的子节点(不包含后代节点)

select * from (
select    
node.name as name,    
(count(parent.name) - 1) as deep    
from    
nested_category as node,    
nested_category as parent    
where node.lft between parent.lft and parent.rgt    
group by node.name    
order by node.lft    
) as a where a.deep <= 1;     
+-----------+------+    
| name      | deep |    
+-----------+------+    
| 商品    |    0 |    
| 化妆品 |    1 |    
| 食品    |    1 |    
| 酒       |    1 |    
| 服装    |    1 |    
| 家电    |    1 |    
| 鞋帽    |    1 |    
+-----------+------+    
7 rows in set (0.00 sec)

总结

我们看到上边的获取深度 和 检索某个节点的子节点实现上用到了子查询,sql语句很复杂.

所以我的解决办法是在数据结构上增加 深度 和 父id 两个字段

因为分类是前台页面操作人员操作的, 也就是说操作的时候就知道深度, 每次新增时候将 深度 和 父id 带上就可以方便的解决复杂sql语句的问题;