MySQL中存储与管理树型数据结构

原载地址：

http://www.wzjs163.com/tangshan/knowledge/mysql/38.html

介绍
大多数用户经常在某些场合需要在SQL数据库中存储树形结构数据，也清楚地知道管理树型结构不是关系型数据库的目标所在。关系型数据库的表不是分层次的(像XML)，而一个简单平坦的列表。树型层次数据有一个父节点关系，在关系型数据库的表中不能自然的表示。

对我们来说，树型结构数据是一个数据集合，每一个节点项目有一个单一的父节点、零个或多个子节点（根节点例外，没有父节点）。树型结构数据存在于很多数据库应用当中，像论坛、邮件列表、商业组织图、内容管理中的目录，和产品目录。我们将使用一个虚拟商店的电子产品目录层次来说明问题:

MySQL中存储与管理树型数据结构

这些目录形成一个像上面介绍的树型结构。本文我们将解释两种模型用以面对在MySQL中存储树型结构的问题，从传统的“邻接表(adjacency list)”模型开始。

邻接表(adjacency list)模型
上面的目录例子将像下面一样存储在表中： (其中包含所有CREATE 和 INSERT 语句，可以跟着做):

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)
在邻接表(adjacency list)模型中, 表中的每一项都包含指向父亲节点中的指针。本例中最*的元素，有一个 NULL 值做父元素节点。邻接表(adjacency list)模型有一个好处就是非常简单，很容易可以看到 FLASH 是 mp3 的一个子节点，mp3是 portable electronics的子节点， portable electronics是electronics的一个子节点。邻接表(adjacency list)模型相对于客户端代码(client-side code)比较容易，但是使用纯SQL有些问题。

获取全部树结构
第一个常见的任务是获取整个树型结构，通常用一定形式缩进。最常见的方式使用纯粹的SQL是使用self-jion：

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';

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 |
+--------------+

取得单条路径
self-join也同样可以查询树型结构的路戏：

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)
此法的主要限制是层次中的每一级都要self-join，同时性能因为每一级都要join变得低下。

邻接表模型(Adjacency List Model)的限制
在纯SQL中使用邻接表模型是很困难的。在我们能够看见目录的完整路径之前，我们必须知道它处于哪一级。另外，删除节点时必须特别注意，因为可能产生无双亲的完整的子树（删除portable electronics目录时，它所有子节点变成无双亲的）。这些限制可通过客户端代码(client-side code)或存储进程(stored procedures)来解决。通过一种过程式语言，我们可以在树的底端开始向上遍历，然后返回整个树或一个完整的路径。同样可以使用过程式语言编程来删除节点，为了不使子树失去双亲可以删节点后对留下的子节点重新排序使它们指向新的父节点。

嵌套集合模型（The Nested Set Model）
下面关注一种完全不同的方法，一般被称为嵌套集合模型（the Nested Set Model），我们可以用一种新的方式看到层次结构，不是节点和行，而是嵌套的容器。试用下边的方式画出电子产品分类：
MySQL中存储与管理树型数据结构

注意我们的层级是怎样维护的：父目录包含了它的孩子。我们通过在表中使用left和right值代表嵌套关系来描述这种层级结构：

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 |
+-------------+----------------------+-----+-----+
我们使用lft和rgt，因为left和right是MySQL中的保留字，详见： http://dev.mysql.com/doc/mysql/en/reserved-words.html 查看所有的保留字。

我们怎样指定left和right值？从最外层的最左边开始数，一直往右:

MySQL中存储与管理树型数据结构

此设计同样可以应用于一个典型的树：

MySQL中存储与管理树型数据结构

这个树工作时，从左到右，每次一层，在指定右手值时向每个节点的子节点延伸，并移到右边。这种方法叫做预排序遍历树算法 (the modified preorder tree traversal algorithm )。

获取整个树
我们可以通过使用一个自连结（self-join）获取整个树，根据连结父节点的节点其lft值总是出现在其父节点的lft和rgt之间：

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;

不像我们之前的使用邻接表模型(adjacency list model)的例子，此查询工作时不考虑树的深度。我们不必自己关心BETWEEN 子句中的rgt值，因为the rgt value will always fall within the same parent as the lft values。

查询所有叶子结点
查询所有嵌套集合模型中的叶子节点比相邻表模型(the adjacency list model)中的LEFT JOIN方法更简单。如果你看一下nested_category表，你会注意到叶子节点的lft和rgt值是连续的。要查询叶子节点，我们查看条件为rgt = lft + 1的节点：

SELECT name
FROM nested_category
WHERE rgt = lft + 1;

获取一个路径
通过嵌套集合模型（the nested set model），我们可以不用多个自连结(self-joins)取得一个路径：

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;

获取节点的深度
我们已经知道了怎样显示整个树，但如果我们想更好的标示出每个节点在树中的情况、显示每个节点在树中的深度怎么办？可以通过增加一个COUNT函数和一个GROUP 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 |
+----------------------+-------+

我们可以使用深度值来缩进目录名称，通过使用CONCAT和REPEAT字符串函数：

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;

当然，在一个客户端应用中你很有可能直接显示深度值。Web开发人员能够循环整个树，随着深度值的增加和减少来增加<li></li>和 <ul></ul>标签。

子树的深度
当我们需要一个子树的深度信息时，我们不能在self-join中限定子节点或父节点，那样会“污染”查询结果。而是，加入第三个self-join，连同一个子查询一起决定子树起点的深度：

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 |
+----------------------+-------+

此功能可以用于任何节点名称，包括根节点。深度值总是相对于给定的节点。

查询某个节点的子树
现在假设你要显示一个零售网站中的电子产品目录，当用户点击一个目录，你可能想显示该目录中的产品，同时显示子目录，但不是全部的子树。为此，我们需要显示本节点和它的子节点，但不继续显示它下边的整个树。例如，当显示 PORTABLE ELECTRONICS 目录时，我们想显示 MP3 PLAYERS， CD PLAYERS，和 2 WAY RADIOS，但不显示 FLASH。

可以通过在之前的查询中加入一个 HAVING 子句即可简单的实现：

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

如果不想显示父节点，把 HAVING 子句中的 depth <= 1 改成 HAVING depth = 1。

嵌套集合中的集合功能(Aggregate Functions in a Nested Set)
加入一个产品表来显示集合功能：

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 |
+------------+-------------------+-------------+

生成一个查询以获取我们的目录树，统计每个目录中的产品数量：

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 |
+----------------------+---------------------+

这是一个典型的使用了 COUNT 和 GROUP BY 子句的整树查询，连同一个到product表的引用，和一个在 WHERE 子句中node、product表的连结。如你所见，每个目录都有一个统计并且所有子目录的统计数据出现在父目录中。

添加新节点（Adding New Nodes）
现在我们知道如何查询我们的树，来看一下怎样一个新节点。再来看一下我们的嵌套集合图：

MySQL中存储与管理树型数据结构

如果我们想在 TELEVISIONS 和 PORTABLE ELECTRONICS 插入一个节点，新节点的lft和rgt值应该为10和11，所有位于它右边的节点它们的lft和rgt值加2。我们应该以适当的lft和rgt值加入新节点，在MySQL 5中可以通过一个存储过程实现，假设读者正在使用MySQL 4.1，它是目前（本文写作时）为止最新的稳定版本，我将使用 LOCK TABLES 语句把我的查询独立出来：

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;

可以通过缩进树查询检查我们的嵌套结构：

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;

如果想为一个不存在子节点的节点加入子节点，我们需要细微的改进一下程序。让我们在2 WAY RADIOS节点下边添加一个 FRS 节点：

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;

本例中，我们更新了2 WAY RADIOS右边所有节点的rgt值和lft值，再把新节点放在父亲节点（left-hand value）的右边。如下所示，新节点已正确的嵌入：

删除节点（Deleting Nodes）
最后一个在嵌套集合使用中涉及的基本工作是节点的删除。删除节点的操作过程依赖于节点在层次中的位置，删除叶子比删除有孩子的节点更容易，因为不需要处理变为孤立节点的孩子节点。

当我们删除叶子节点时，其过程恰恰是插入节点的反向操作，我们删除节点和它的宽度（width）（原文：When deleting a leaf node, the process if just the opposite of adding a new node, we delete the node and its width from every node to its right）：

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;

我们再次执行缩进树查询，确认节点已被删除、并且没有破坏层次结构：

此方法用来删除节点和节点的所有子节点：

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;

再一次，我们查询看是否成功删除整个子树：

我们需要处理的其它情况是删除父节点而不是子节点。在一些情况下你可能希望把名称设置为一个点位符，在需要的时候再进行替换。诸如一个管理员人被解雇了（such as when a supervisor is fired）？另外有一些情况，子节点应该全部向上移到删除的父节点的上一级：

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;

In this case we subtract two from all elements to the right of the node (since without children it would have a width of two), and one from the nodes that are its children (to close the gap created by the loss of the parent's left value). Once again, we can confirm our elements have been promoted:

+---------------+
| name          |
+---------------+
| ELECTRONICS   |
| TELEVISIONS |
|   TUBE        |
|   LCD         |
|   PLASMA      |
| CD PLAYERS   |
| 2 WAY RADIOS |
|   FRS         |
+---------------+

其它的情况是删除节点同时把一个子节点提升到父节点的位置，或把子节点移到父节点的兄弟姊妹之下，限于篇幅这些内容不在本文中讨论。

最后的思考（Final Thoughts）
很希望本文的内容对你有用，SQL中嵌套集合的概念已经有了10几年，在图书中和互联网上有很多相关的信息。在我看了，管理层次信息的最全面、综合的是一本叫做 Joe Celko's Trees and Hierarchies in SQL for Smarties 的书，由在高级SQL领域很受尊敬的Joe Celko编写。Joe Celko经常使用嵌套集合模型工作，在这方面是一位多产的作家。我发现Celko的书对我的学习研究来说是非常宝贵的资源，我强烈推荐它。书中包含了本文没有包含的高级主题，也提供除了邻接表(Adjacency List)和嵌套集合(Nested Set models)以外的其它方法管理层次数据。

在参考文献/资源一节我列出了一些web资源，你可能在管理层次数据时用到它们。包一对PHP相关的资源，包含了一些pre-built PHP库用于处理MySQL中的嵌套集合。那些正在使用邻接表模型(adjacency list model)并且愿意尝试嵌套集合模型(the netsted set model)的人，可以在下边的Storing Hierarchical Data in a Database 资源列表中发现一些用于转换的例子代码。

秒客网

MySQL中存储与管理树型数据结构

相关文章