MySQL实现嵌套集合模型

【自取】最近整理的,有需要可以领取学习:

MySQL实现嵌套集合模型

译文主要是介绍如何用MySQL来存储嵌套集合数据。在其中会增加一些自己的理解,也会删除掉一些自认为无用的废话。
本文主要讨论嵌套集合模型,因此邻接表不是本文的重点,跳过它。[en]This article is mainly about the nested set model, so the adjacency table is not the focus of this article, just skip it.

也许这是原文地址,因为我也不知道这是不是原文。

介绍

什么是分层数据?

MySQL实现嵌套集合模型

与树结构类似,除根节点和叶节点外,所有节点都使用一个父节点和多个子节点。[en]Similar to a tree structure, with the exception of root and leaf nodes, all nodes use one parent node and multiple child nodes.

那么,如何在MySQL中处理分层数据呢?[en]So, how do you deal with hierarchical data in MySQL?

原文中介绍了两种分层结构模型: 邻接表模型嵌套集合模型

邻接表模型(The Adjacency List Model)

首先,设置测试表并导入测试数据[en]First, set up the test table and import the test data

CREATE TABLE category(
        category_id INT AUTO_INCREMENT PRIMARY KEY,
        name VARCHAR(20) NOT NULL,
        parent INT DEFAULT NULL
);

INSERT INTO category VALUES
        (1,'ELECTRONICS',NULL),
        (2,'TELEVISIONS',1),
        (3,'TUBE',2),
        (4,'LCD',2),
        (5,'PLASMA',2),
        (6,'PORTABLE ELECTRONICS',1),
        (7,'MP3 PLAYERS',6),
        (8,'FLASH',7),
        (9,'CD PLAYERS',6),
        (10,'2 WAY RADIOS',6);

SELECT * FROM category ORDER BY category_id;
+-------------+----------------------+--------+
| category_id | name                 | parent |
+-------------+----------------------+--------+
|           1 | ELECTRONICS          |   NULL |
|           2 | TELEVISIONS          |      1 |
|           3 | TUBE                 |      2 |
|           4 | LCD                  |      2 |
|           5 | PLASMA               |      2 |
|           6 | PORTABLE ELECTRONICS |      1 |
|           7 | MP3 PLAYERS          |      6 |
|           8 | FLASH                |      7 |
|           9 | CD PLAYERS           |      6 |
|          10 | 2 WAY RADIOS         |      6 |
+-------------+----------------------+--------+
10 rows in set (0.00 sec)

在邻接表中,所有数据都有存储其父节点的父字段。如果当前节点是根节点,则其父节点为空。[en]In the adjacency table, all data has a Parent field that stores its parent node. If the current node is the root node, its parent node is NULL.
然后,在遍历时,您可以使用递归来查询整个树,从根节点开始,不断查找子节点(父节点->子节点->父节点->子节点)。[en]Then when traversing, you can use recursion to query the entire tree, starting from the root node, constantly looking for child nodes (parent node-> child node-> parent node-> child node).

检索分层路径

一般需要得到一个层次结构的路径问题,然后[en]Generally need to get a hierarchical structure of the path problem, then

SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS';

+-------------+----------------------+--------------+-------+
| lev1        | lev2                 | lev3         | lev4  |
+-------------+----------------------+--------------+-------+
| ELECTRONICS | TELEVISIONS          | TUBE         | NULL  |
| ELECTRONICS | TELEVISIONS          | LCD          | NULL  |
| ELECTRONICS | TELEVISIONS          | PLASMA       | NULL  |
| ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS  | FLASH |
| ELECTRONICS | PORTABLE ELECTRONICS | CD PLAYERS   | NULL  |
| ELECTRONICS | PORTABLE ELECTRONICS | 2 WAY RADIOS | NULL  |
+-------------+----------------------+--------------+-------+
6 rows in set (0.00 sec)

检索叶子节点

SELECT t1.name FROM
category AS t1 LEFT JOIN category as t2
ON t1.category_id = t2.parent
WHERE t2.category_id IS NULL;

+--------------+
| name         |
+--------------+
| TUBE         |
| LCD          |
| PLASMA       |
| FLASH        |
| CD PLAYERS   |
| 2 WAY RADIOS |
+--------------+

检索指定路径

SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS' AND t4.name = 'FLASH';

+-------------+----------------------+-------------+-------+
| lev1        | lev2                 | lev3        | lev4  |
+-------------+----------------------+-------------+-------+
| ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS | FLASH |
+-------------+----------------------+-------------+-------+
1 row in set (0.01 sec)

邻接表的缺点

在检索路径的过程中,除了本层外,每一层都会对应一个 LEFT JOIN,那么如果层数不定怎么办?或者层数过多?
删除中间层节点时,需要同时删除该节点下的所有节点,否则会出现孤立节点。[en]When deleting a node in the middle tier, you need to delete all nodes under that node at the same time, otherwise there will be orphaned nodes.

嵌套集合模型Nested Set Model

原文的主要目的是介绍嵌套SET模型,如下所示[en]The main purpose of the original text is to introduce the nested set model, as follows

MySQL实现嵌套集合模型

通过集合的包含关系,嵌套关联模型可以表示一种层次结构,每一层可以用一个集合(一个圆)来表示,父节点的圆包含所有子节点的圆。[en]Through the inclusion relationship of sets, the nested association model can represent a hierarchical structure, each layer can be represented by a Set (a circle), and the circle of the parent node contains the circle of all child nodes.

为了用MySQL来表示集合关系,需要定义连个字段 leftright(表示一个集合的范围)。

CREATE TABLE nested_category (
        category_id INT AUTO_INCREMENT PRIMARY KEY,
        name VARCHAR(20) NOT NULL,
        lft INT NOT NULL,
        rgt INT NOT NULL
);

INSERT INTO nested_category VALUES
  (1,'ELECTRONICS',1,20),
  (2,'TELEVISIONS',2,9),
  (3,'TUBE',3,4),
  (4,'LCD',5,6),
  (5,'PLASMA',7,8),
  (6,'PORTABLE ELECTRONICS',10,19),
  (7,'MP3 PLAYERS',11,14),
  (8,'FLASH',12,13),
  (9,'CD PLAYERS',15,16),
  (10,'2 WAY RADIOS',17,18);

SELECT * FROM nested_category ORDER BY category_id;

+-------------+----------------------+-----+-----+
| category_id | name                 | lft | rgt |
+-------------+----------------------+-----+-----+
|           1 | ELECTRONICS          |   1 |  20 |
|           2 | TELEVISIONS          |   2 |   9 |
|           3 | TUBE                 |   3 |   4 |
|           4 | LCD                  |   5 |   6 |
|           5 | PLASMA               |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |  10 |  19 |
|           7 | MP3 PLAYERS          |  11 |  14 |
|           8 | FLASH                |  12 |  13 |
|           9 | CD PLAYERS           |  15 |  16 |
|          10 | 2 WAY RADIOS         |  17 |  18 |
+-------------+----------------------+-----+-----+

由于 leftright是MySQL的保留字,因此,字段名称用lft和rgt代替。每一个集合都是从lft开始到rgt结束,也就是集合的两个边界。

MySQL实现嵌套集合模型

它也适用于树木。[en]It also applies in trees.

MySQL实现嵌套集合模型

当为树状结构编号时,我们从左到右,一次一层,赋值按照从左到右的顺序遍历其子节点,这种方法称为 先序遍历算法

检索分层路径

由于子节点的LFT值总是在父节点的LFT值和RGT值之间,因此可以通过将父节点连接到子节点来检索整个树。[en]Since the LFT value of the child node is always between the lft and RGT values of the parent node, the entire tree can be retrieved by connecting the parent node to the child node.

SELECT node.name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND parent.name = 'ELECTRONICS'
ORDER BY node.lft;

+----------------------+
| name                 |
+----------------------+
| ELECTRONICS          |
| TELEVISIONS          |
| TUBE                 |
| LCD                  |
| PLASMA               |
| PORTABLE ELECTRONICS |
| MP3 PLAYERS          |
| FLASH                |
| CD PLAYERS           |
| 2 WAY RADIOS         |
+----------------------+

该方法不需要考虑层数,也不需要考虑节点的RGT。[en]This method does not need to consider the number of layers, and does not need to consider the rgt of the node.

检索所有叶子节点

由于每一个叶子节点的 rgt=lft+1,那么只需要这一个条件即可。

SELECT name
FROM nested_category
WHERE rgt = lft + 1;

+--------------+
| name         |
+--------------+
| TUBE         |
| LCD          |
| PLASMA       |
| FLASH        |
| CD PLAYERS   |
| 2 WAY RADIOS |
+--------------+

检索节点路径

不再需要多个联接连接操作。[en]Multiple join connection operations are no longer required.

SELECT parent.name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.name = 'FLASH'
ORDER BY node.lft;

+----------------------+
| name                 |
+----------------------+
| ELECTRONICS          |
| PORTABLE ELECTRONICS |
| MP3 PLAYERS          |
| FLASH                |
+----------------------+

检索节点深度

通过 COUNTGROUP BY函数来获取父节点的个数。

SELECT node.name, (COUNT(parent.name) - 1) AS depth
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                 | depth |
+----------------------+-------+
| ELECTRONICS          |     0 |
| TELEVISIONS          |     1 |
| TUBE                 |     2 |
| LCD                  |     2 |
| PLASMA               |     2 |
| PORTABLE ELECTRONICS |     1 |
| MP3 PLAYERS          |     2 |
| FLASH                |     3 |
| CD PLAYERS           |     2 |
| 2 WAY RADIOS         |     2 |
+----------------------+-------+

您甚至可以获得分层缩进结果。[en]You can even get hierarchical indentation results.

SELECT CONCAT( REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name
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                  |
+-----------------------+
| ELECTRONICS           |
|  TELEVISIONS          |
|   TUBE                |
|   LCD                 |
|   PLASMA              |
|  PORTABLE ELECTRONICS |
|   MP3 PLAYERS         |
|    FLASH              |
|   CD PLAYERS          |
|   2 WAY RADIOS        |
+-----------------------+

检索子树的深度

考虑到检索中需要自联接节点或父节点,您需要添加一个额外的联接作为子查询来限制子树。[en]Considering the need for self-joined node or parent in retrieval, you need to add an additional join as a subquery to restrict the subtree.

SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
        nested_category AS parent,
        nested_category AS sub_parent,
        (
                SELECT node.name, (COUNT(parent.name) - 1) AS depth
                FROM nested_category AS node,
                nested_category AS parent
                WHERE node.lft BETWEEN parent.lft AND parent.rgt
                AND node.name = 'PORTABLE ELECTRONICS'
                GROUP BY node.name
                ORDER BY node.lft
        )AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
        AND sub_parent.name = sub_tree.name
GROUP BY node.name
ORDER BY node.lft;

+----------------------+-------+
| name                 | depth |
+----------------------+-------+
| PORTABLE ELECTRONICS |     0 |
| MP3 PLAYERS          |     1 |
| FLASH                |     2 |
| CD PLAYERS           |     1 |
| 2 WAY RADIOS         |     1 |
+----------------------+-------+

检索节点的直接子节点

假设用户点击站点上的一个电子产品类别,将显示该类别下的产品,并且需要列出所有子类别,而不是所有子类别。[en]Suppose a scenario in which the user clicks on a category of electronic products on the site, the products under that category will be presented, and all subcategories need to be listed, not all of them.
为了限制显示分类的层数,需要使用 HAVING字句,

SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
        nested_category AS parent,
        nested_category AS sub_parent,
        (
                SELECT node.name, (COUNT(parent.name) - 1) AS depth
                FROM nested_category AS node,
                        nested_category AS parent
                WHERE node.lft BETWEEN parent.lft AND parent.rgt
                        AND node.name = 'PORTABLE ELECTRONICS'
                GROUP BY node.name
                ORDER BY node.lft
        )AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
        AND sub_parent.name = sub_tree.name
GROUP BY node.name
HAVING depth <= 1
ORDER BY node.lft;

+----------------------+-------+
| name                 | depth |
+----------------------+-------+
| PORTABLE ELECTRONICS |     0 |
| MP3 PLAYERS          |     1 |
| CD PLAYERS           |     1 |
| 2 WAY RADIOS         |     1 |
+----------------------+-------+

增加新节点

我已经描述了如何检索结果,那么如何添加新节点呢?[en]I’ve already described how to retrieve the results, so how can I add new nodes?

MySQL实现嵌套集合模型

如果要在电视机和PROTABLE电子产品节点之间添加新节点,则新节点的LFT和RGT的值应为10和11,则所有大于10的节点(新节点右侧的节点)的LFT和RGT应加2,如上图所示。[en]If you want to add a new node between the TELEVISIONS and PROTABLE ELECTRONICS nodes, the values of lft and rgt for the new node should be 10 and 11, then the lft and rgt of all nodes greater than 10 (the node to the right of the new node) should be added by 2, as shown in the figure above.

LOCK TABLE nested_category WRITE;

SELECT @myRight := rgt FROM nested_category
WHERE name = 'TELEVISIONS';

UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;

INSERT INTO nested_category(name, lft, rgt) VALUES('GAME CONSOLES', @myRight + 1, @myRight + 2);

UNLOCK TABLES

如果要在叶节点下添加节点,则需要修改查询语句[en]If you want to add nodes under the leaf node, you need to modify the query statement

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft FROM nested_category

WHERE name = '2 WAY RADIOS';

UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myLeft;

INSERT INTO nested_category(name, lft, rgt) VALUES('FRS', @myLeft + 1, @myLeft + 2);

UNLOCK TABLES;`

###&#x5220;&#x9664;&#x8282;&#x70B9;

&#x5220;&#x9664;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x6BD4;&#x8F83;&#x5BB9;&#x6613;&#xFF0C;&#x53EA;&#x9700;&#x8981;&#x5220;&#x9664;&#x81EA;&#x5DF1;&#xFF0C;&#x800C;&#x5220;&#x9664;&#x4E00;&#x4E2A;&#x4E2D;&#x95F4;&#x5C42;&#x8282;&#x70B9;&#x5C31;&#x9700;&#x8981;&#x5220;&#x9664;&#x5176;&#x6240;&#x6709;&#x5B50;&#x8282;&#x70B9;&#x3002;&#x5728;&#x8FD9;&#x4E2A;&#x6A21;&#x578B;&#x4E2D;&#xFF0C;&#x6240;&#x6709;&#x5B50;&#x8282;&#x70B9;&#x7684;&#x8282;&#x70B9;&#x6B63;&#x597D;&#x5728;lft&#x548C;rgt&#x4E4B;&#x95F4;&#x3002;

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt – lft + 1
FROM nested_category
WHERE name = ‘GAME CONSOLES’;

DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;

UPDATE nested_category SET rgt = rgt – @myWidth WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft – @myWidth WHERE lft > @myRight;

UNLOCK TABLES;


&#x5728;&#x67D0;&#x4E9B;&#x60C5;&#x51B5;&#x4E0B;&#xFF0C;&#x53EA;&#x9700;&#x8981;&#x5220;&#x9664;&#x67D0;&#x4E2A;&#x8282;&#x70B9;&#xFF0C;&#x4F46;&#x662F;&#x5E76;&#x4E0D;&#x5E0C;&#x671B;&#x5220;&#x9664;&#x8BE5;&#x8282;&#x70B9;&#x4E0B;&#x7684;&#x5B50;&#x8282;&#x70B9;&#x6570;&#x636E;&#x3002;
&#x901A;&#x8FC7;&#x628A;&#x53F3;&#x4FA7;&#x6240;&#x6709;&#x8282;&#x70B9;&#x7684;&#x5DE6;&#x53F3;&#x503C;-2&#xFF0C;&#x5F53;&#x524D;&#x8282;&#x70B9;&#x7684;&#x5B50;&#x8282;&#x70B9;&#x5DE6;&#x53F3;&#x503C;-1

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt – lft + 1
FROM nested_category
WHERE name = ‘PORTABLE ELECTRONICS’;

DELETE FROM nested_category WHERE lft = @myLeft;

UPDATE nested_category SET rgt = rgt – 1, lft = lft – 1 WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nested_category SET rgt = rgt – 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft – 2 WHERE lft > @myRight;

UNLOCK TABLES;


##&#x6700;&#x540E;&#x7684;&#x601D;&#x8003;

&#x539F;&#x4F5C;&#x8005;&#x63A8;&#x8350;&#x4E86;&#x4E00;&#x672C;&#x540D;&#x4E3A;&#x300A;Joe Celko's Trees and Hierarchies in SQL for Smarties&#x300B;&#x7684;&#x4E66;&#x7C4D;&#xFF0C;&#x8BE5;&#x4E66;&#x7684;&#x4F5C;&#x8005;&#x662F;SQL&#x9886;&#x57DF;&#x7684;&#x5927;&#x795E;Joe Celko&#xFF08;&#x5D4C;&#x5957;&#x51E0;&#x4F55;&#x6A21;&#x578B;&#x7684;&#x521B;&#x9020;&#x8005;&#xFF09;&#x3002;&#x8FD9;&#x672C;&#x4E66;&#x6DB5;&#x76D6;&#x4E86;&#x672C;&#x6587;&#x4E2D;&#x672A;&#x6D89;&#x53CA;&#x5230;&#x7684;&#x4E00;&#x4E9B;&#x9AD8;&#x7EA7;&#x8BDD;&#x9898;&#x3002;

Original: https://www.cnblogs.com/coder2012/p/4827757.html
Author: cococo点点
Title: MySQL实现嵌套集合模型

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/6034/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

发表回复

登录后才能评论
免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部