原文地址,原文中Hierarchical Data直译为 分层结构,这里我翻译成 树状结构

补充资源:

  1. https://django-mptt.github.io/django-mptt/ ,如果你也使用python和django,这个是现成的APP。

另外,个人觉得这种方法对于搜索的效率提升最大,而相应的新增、删除等操作则会变慢,个人猜测未经测试。

个人总结的核心:如果一个节点A是节点B的子节点,那么A的左值一定大于B的左值,A的右值一定小于B的右值。或者说,A的左值一定在B的左值和右值之间。

介绍

许多人都遇到过需要在MySQL中处理树状结构数据的情况,毫无疑问管理树状结构并不是关系型数据库的强项。关系型数据库的表并不是树状结构(比如XML)而是一种扁平结构。树状结构中的”父–子”关系并不被MySQL天生支持。

在我们看来,树状结构是一类数据的集合,集合中每一个元素都有一个父节点和零或多个子节点(除了根节点,根节点没有父节点)。树状结构在很多程序中都会出现,比如论坛、邮件列表、公司组织架构图、内容分类管理、产品目录等。在这里,我们使用下面的产品分来目录来虚构一个电子产品目录:
product

上面的分类构成了一种树状结构,在这篇文章中我们将使用2种方法来在MySQL中操作它。首先使用传统的邻接表的方式。

邻接表

典型的分类示例将以下面的结构存储在表中(下面包含了完整的create和insert操作,所以你可以自行测试):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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)

在邻接表中,每一条数据都有一个字段指向它的父节点。本例中的根节点ELECTRONICSparent则为NULL。邻接表的特点就是简单,可以很容易的看出FLASHMP3 PLAYERS的子节点。同时MP3 PLAYERSPORTABLE ELECTRONICS的子节点,而PORTABLE ELECTRONICS又是ELECTRONICS的子节点。尽管邻接表可以在客户端代码被很容易的处理,但对于原生的SQL语句则可能会产生问题。

遍历树

在操作树状结构时最常见的一个操作就是以缩进的形式来展示整个树,使用SQL语句实现的最常见方法就是使用join语句:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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)

找出所有叶子节点

我们可以使用LEFT JOIN语句来找出所有的叶子节点(没有子节点的节点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 |
+--------------+

寻找单一路径

可以使用JOIN语句在树状结构中查看某一条路径:

1
2
3
4
5
6
7
8
9
10
11
12
13
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)

这种方式最大的缺点就是每一层查询都要使用JOIN语句,随着树状结构的层次越来越复杂,查询的性能也越来越低下。

邻接表的局限性

使用原生SQL语句操作邻接表是十分困难的,在我们知道某个节点在分类中的路径之前,我们必须知道它所在的层级。除此之外,在执行删除操作时要额外的小心,因为这个操作可能潜在的使整个子树都变成孤儿节点。(比如删除了PORTABLE ELECTRONICS则它所有的子节点都会成为孤儿节点。)这些限制可以通过客户端代码或存储过程来解决。在程序代码中,我们可以通过从树底部向上遍历返回完整的树或一个单一路径,也可以通过重新指定一个父节点并对其他子节点进行重新排序来让他们指向新的父节点的方式来删除一个节点而不产生孤儿节点。

嵌套集

这篇文章中我想重点解释一下嵌套集(Nested Set Model)。在嵌套集中,我们可以用一种新的视角来看待树状结构。不是使用节点或行,而是使用嵌套的容器。想想一下我们的结构如下:
nested
请注意我们仍然保持了树状结构,作为父节点的分类包含了子节点。我们使用左值和右值的方式来在表中表现节点的层级关系:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 |
+-------------+----------------------+-----+-----+

我们使用lftrgt是因为leftright是SQL中的关键字,在这里可以看到完整的关键字列表。
那么,我们如何来确定节点的左值和右值呢?我们从左向右依次进行编号:
nested2
这种设计可以使用树状结构来展示:
nested3
构建这种树我们需要从左向右、每次一层的向下遍历其子节点,对于叶子节点则指定其右值并移动到其右边的兄弟节点。这种方法被称为“前序遍历树算法变异版”(modified preorder tree traversal algorithm)。

遍历树

我们可以基于这样一个前提遍历整个树:一个节点的左值总是处在父节点的左值和右值之间:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 |
+----------------------+

与前面说的邻接表不同,这里的查询不会考虑树的深度。也无需考虑节点的右值因为右值永远小于父节点的右值。

找出所有叶子节点

在嵌套集中找出所有叶子节点比在邻接表中使用JOIN查询简单的多。如果你仔细观察,会发现叶子节点的左值和右值永远是连续的,所以找到叶子节点,我们仅需找到rgt = lft + 1的节点即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
SELECT name
FROM nested_category
WHERE rgt = lft + 1;
+--------------+
| name |
+--------------+
| TUBE |
| LCD |
| PLASMA |
| FLASH |
| CD PLAYERS |
| 2 WAY RADIOS |
+--------------+

寻找单一路径

在嵌套集中我们可以寻找单一路径而不使用大量的JOIN操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 parent.lft;
+----------------------+
| name |
+----------------------+
| ELECTRONICS |
| PORTABLE ELECTRONICS |
| MP3 PLAYERS |
| FLASH |
+----------------------+

获取节点深度

我们已经知道了如何遍历整个树,但如何表示每个节点在树中的深度呢?如何更好的识别每个节点所处的层次呢?这里可以使用COUNT以及GROUP BY来实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 |
+----------------------+-------+

也可以使用depth结合CONCAT以及REPEAT函数来在前面添加空格:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 |
+-----------------------+

当然,在客户端程序中你可能更喜欢直接使用depth来展示树状结构,WEB开发人员可以通过循环来遍历树,使用depth控制<li></li><ul></ul>的数量增减。

子树的深度

当我们需要子树的深度信息时,我们既不能限制表中的子节点也不能限制父节点,因为这样做会破坏结果。相反的,我们添加一个新的自关联查询来构造一个子树,并将根节点指向构造出来的子树后进行深度的查询:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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 |
+----------------------+-------+

这个函数可以被应用到任何节点上,包括根节点。获得的深度总是相对于给出的节点。

找到一个节点的直属子节点

想像一下你要在一个网站上展示电子产品的分类,当用户点击某个分类后,你想展示这个分类的直属子分类而不是全部的子分类(ps:即相对这个节点深度为1的子节点)。例如,当展示PORTABLE ELECTRONICS分类时,我们仅想展示MP3 PLAYERSCD PLAYERS2 WAY RADIOS,而不包括FLASH

这可以通过添加HAVING关键字来实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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 |
+----------------------+-------+

如果你不想展示父节点,把HAVING depth <= 1替换成HAVING depth = 1即可。

在嵌套集中使用聚合函数

首先添加一个product表来方便演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
CREATE TABLE product
(
product_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(40),
category_id INT NOT NULL
);
INSERT INTO product(name, category_id) VALUES('20" TV',3),('36" TV',3),
('Super-LCD 42"',4),('Ultra-Plasma 62"',5),('Value Plasma 38"',5),
('Power-MP3 5gb',7),('Super-Player 1gb',8),('Porta CD',9),('CD To go!',9),
('Family Talk 360',10);
SELECT * FROM product;
+------------+-------------------+-------------+
| product_id | name | category_id |
+------------+-------------------+-------------+
| 1 | 20" TV | 3 |
| 2 | 36" TV | 3 |
| 3 | Super-LCD 42" | 4 |
| 4 | Ultra-Plasma 62" | 5 |
| 5 | Value Plasma 38" | 5 |
| 6 | Power-MP3 128mb | 7 |
| 7 | Super-Shuffle 1gb | 8 |
| 8 | Porta CD | 9 |
| 9 | CD To go! | 9 |
| 10 | Family Talk 360 | 10 |
+------------+-------------------+-------------+

下面我们进行一个查询,来统计每个分类下的产品数量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
SELECT parent.name, COUNT(product.name)
FROM nested_category AS node ,
nested_category AS parent,
product
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.category_id = product.category_id
GROUP BY parent.name
ORDER BY node.lft;
+----------------------+---------------------+
| name | COUNT(product.name) |
+----------------------+---------------------+
| ELECTRONICS | 10 |
| TELEVISIONS | 5 |
| TUBE | 2 |
| LCD | 1 |
| PLASMA | 2 |
| PORTABLE ELECTRONICS | 5 |
| MP3 PLAYERS | 2 |
| FLASH | 1 |
| CD PLAYERS | 2 |
| 2 WAY RADIOS | 1 |
+----------------------+---------------------+

这是一种典型的示例,展示了使用COUNTGROUP BY以及WHERE语句和product表进行关联查询。正如你看到的,每一个分类的数量都被统计出来了并反映在父类别中。

添加节点

之前我们学习了如何查询,现在来看看如何新增一个节点。让我们再看一下嵌套集的示例图:
nested2
如果我们想在TELEVISIONSPORTABLE ELECTRONICS节点之间添加一个新节点,这个新节点左值应该是10而右值为11,而它右边所有的节点的值都应该加2。我们可以在MySQL5中使用存储过程来实现,这里我假设MySQL版本为4.1(译者注:这是一篇旧文,写作时mysql稳定版本还是4.1)。使用下面的语句:

1
2
3
4
5
6
7
8
9
10
11
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;

我们可以来检查一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 |
| GAME CONSOLES |
| PORTABLE ELECTRONICS |
| MP3 PLAYERS |
| FLASH |
| CD PLAYERS |
| 2 WAY RADIOS |
+-----------------------+

如果我们想给一个叶子节点添加子节点,需要修改一下代码。这里我们给2 WAY RADIOS添加一个FRS做子节点:

1
2
3
4
5
6
7
8
9
10
11
12
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;

在这个示例中我们修改了新的父节点的右值,正如所见,新的节点被插入了正确的位置:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 |
| GAME CONSOLES |
| PORTABLE ELECTRONICS |
| MP3 PLAYERS |
| FLASH |
| CD PLAYERS |
| 2 WAY RADIOS |
| FRS |
+-----------------------+

删除节点

最后一个基础操作就是删除节点。删除节点的行为取决于被删除节点在树状结构中所处的层级,删除叶子节点比删除子节点容易,因为不用考虑孤儿节点的问题。

当删除叶子节点时,操作仅仅和添加节点相反,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
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;

我们来执行查询操作确认删除成功:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 |
| FRS |
+-----------------------+

这个方法也可以用于删除子节点以及这个节点的所有节点:

1
2
3
4
5
6
7
8
9
10
11
12
LOCK TABLE nested_category WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'MP3 PLAYERS';
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;

再来查询一遍,确认我们是否删除了整个子树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 |
| CD PLAYERS |
| 2 WAY RADIOS |
| FRS |
+-----------------------+

在某些情况下我们仅想删除父节点而保留子节点,而这些子节点则被提升至和父节点平级:

1
2
3
4
5
6
7
8
9
10
11
12
13
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;

在这里,我们把这个节点的所有右侧节点的值减2(因为没有子节点的宽度为2),并且把这个节点的子节点的值减1(使用被删除的父节点的左值来弥补差距)。再来确认一下操作是否成功:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 |
| CD PLAYERS |
| 2 WAY RADIOS |
| FRS |
+---------------+

其他的情形比如:移动节点到兄弟节点下、使一个子节点替代原来的父节点等,这里不再进行说明。

总结

希望这篇文章对你有用,关于嵌套集的概念在SQL中已经有很多年的历史了,网上和书中也有很多额外的信息。在我看来关于管理树状结构最全面的一本书是《 Joe Celko’s Trees and Hierarchies in SQL for Smarties》,作者是MYSQL大牛Joe Celko。他的书是一个宝库,我强烈建议每个人都读读他的作品。这本书中包含了很多文章中没提到的高级技巧,并且提供了除邻接表和嵌套集外其他的管理树状结构的方法。

(还有一段原作者介绍下面资源的话,略)

引用/资源

  1. Joe Celko’s Trees and Hierarchies in SQL for Smarties – ISBN 1-55860-920-2
  2. Storing Hierarchical Data in a Database
  3. A Look at SQL Trees
  4. SQL Lessons
  5. Nontraditional Databases
  6. Trees in SQL
  7. Trees in SQL (2)
  8. Converting an adjacency list model to a nested set model
  9. Nested Sets in PHP Demonstration (German)
  10. A Nested Set Library in PHP