预排序树实现无限极分类

一.概念

  • 左右值无限级分类,也称为预排序树无限级分类

  • 是一种有序的树状结构

  • 于这些树状结构中的每一个节点都有一个 左值 和 右值

二.规则

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

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

  • 每一个节点的 右值 > 左值

三.新增节点

  • 新增顶级分类:

    • 获取该树中 最大右值;

    • 左值 = 最大右值 + 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&gt; 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 &lt;= 1;     
+-----------+------+    
| name      | deep |    
+-----------+------+    
| 商品    |    0 |    
| 化妆品 |    1 |    
| 食品    |    1 |    
| 酒       |    1 |    
| 服装    |    1 |    
| 家电    |    1 |    
| 鞋帽    |    1 |    
+-----------+------+    
7 rows in set (0.00 sec)

十二.总结

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

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

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

    评论

    1. 2年前
      2018-11-16 3:46:22

      I will immediately take hold of your rss as I can’t to find your e-mail subscription hyperlink or newsletter service.
      Do you have any? Kindly allow me know in order that I could subscribe.
      Thanks. It is perfect time to make some plans for the future and it’s
      time to be happy. I’ve read this post and if I could
      I want to suggest you some interesting things or suggestions.

      Perhaps you can write next articles referring to this article.

      I wish to read more things about it! bookmarked!!, I really like your blog!

      http://Cspan.Co.uk/

    发送评论 编辑评论

    
    
    |´・ω・)ノ
    ヾ(≧∇≦*)ゝ
    (☆ω☆)
    (╯‵□′)╯︵┴─┴
     ̄﹃ ̄
    (/ω\)
    ∠( ᐛ 」∠)_
    (๑•̀ㅁ•́ฅ)
    →_→
    ୧(๑•̀⌄•́๑)૭
    ٩(ˊᗜˋ*)و
    (ノ°ο°)ノ
    (´இ皿இ`)
    ⌇●﹏●⌇
    (ฅ´ω`ฅ)
    (╯°A°)╯︵○○○
    φ( ̄∇ ̄o)
    ヾ(´・ ・`。)ノ"
    ( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
    (ó﹏ò。)
    Σ(っ °Д °;)っ
    ( ,,´・ω・)ノ"(´っω・`。)
    ╮(╯▽╰)╭
    o(*////▽////*)q
    >﹏<
    ( ๑´•ω•) "(ㆆᴗㆆ)
    😂
    😀
    😅
    😊
    🙂
    🙃
    😌
    😍
    😘
    😜
    😝
    😏
    😒
    🙄
    😳
    😡
    😔
    😫
    😱
    😭
    💩
    👻
    🙌
    🖕
    👍
    👫
    👬
    👭
    🌚
    🌝
    🙈
    💊
    😶
    🙏
    🍦
    🍉
    😣
    Source: github.com/k4yt3x/flowerhd
    颜文字
    Emoji
    小恐龙
    花!
    上一篇
    下一篇