MYSQL中分层数据的管理
By Mike Hillyer
引言
大多数用户都曾在数据库中处理过分层数据(hierarchical data)，认为分层数据的管理不是关系数据库的目的。之所以这么认为，是因为关系数据库中的表没有层次关系，只是简单的平面化的列表；而分层数据具有父－子关系，显然关系数据库中的表不能自然地表现出其分层的特性。
我们认为，分层数据是每项只有一个父项和零个或多个子项（根项除外，根项没有父项）的数据集合。分层数据存在于许多基于数据库的应用程序中，包括论坛和邮件列表中的分类、商业组织图表、内容管理系统的分类、产品分类。我们打算使用下面一个虚构的电子商店的产品分类：
这些分类层次与上面提到的一些例子中的分类层次是相类似的。在本文中我们将从传统的邻接表(adjacency list)模型出发，阐述2种在MySQL中处理分层数据的模型。
邻接表模型
上述例子的分类数据将被存储在下面的数据表中（我给出了全部的数据表创建、数据插入的
代码，你可以跟着做）：
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)
在邻接表模型中，数据表中的每项包含了指向其父项的指示器。在此例中，最上层项的父项为空值(NULL)。邻接表模型的优势在于它很简单，可以很容易地看出FLASH是MP3 PLAYERS 的子项，哪个是portable electronics的子项，哪个是electronics的子项。虽然，在客户端编码中邻接表模型处理起来也相当的简单，但是如果是纯SQL编码的话，该模型会有很多问题。
检索整树
通常在处理分层数据时首要的任务是，以某种缩进形式来呈现一棵完整的树。为此，在纯SQL编码中通常的做法是使用自连接(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';
+­­­­­­­­­­­­­+­­­­­­­­­­­­­­­­­­­­­­+­­­­­­­­­­­­­­+­­­­­­­+
| 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 JO I N)来检索出树中所有叶子节点(没有孩子节点的节点）：
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)
这种方法的主要局限是你需要为每层数据添加一个自连接，随着层次的增加，自连接变得越来越复杂，检索的性能自然而然的也就下降了。
邻接表模型的局限性
用纯SQL编码实现邻接表模型有一定的难度。在我们检索某分类的路径之前，我们需要知道
该分类所在的层次。另外，我们在删除节点的时候要特别小心，因为潜在的可能会孤立一棵子树（当删除portable electronics分类时，所有他的子分类都成了孤儿）。部分局限性可以通过使用客户端代码或者存储过程来解决，我们可以从树的底部开始向上迭代来获得一颗树或者单一路径，我们也可以在删除节点的时候使其子节点指向一个新的父节点，来防止孤立子树的产生。
嵌套集合(Nested Set)模型
我想在这篇文章中重点阐述一种不同的方法，俗称为嵌套集合模型。在嵌套集合模型中，我们将以一种新的方式来看待我们的分层数据，不再是线与点了，而是嵌套容器。我试着以嵌套容器的方式画出了electronics分类图：
从上图可以看出我们依旧保持了数据的层次，父分类包围了其子分类。在数据表中，我们通过使用表示节点的嵌套关系的左值(left v al u e)和右值(ri g ht v al u e)来表现嵌套集合模型中数据的分层特性：
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和r g t来代替left和ri g ht，是因为在MySQL中left和ri g ht是保留字。de v.m ys m/doc/m ys q l/en/reser v ed-w ords.ht m l，有一份详细的MySQL保留字清单。
那么，我们怎样决定左值和右值呢？我们从外层节点的最左侧开始，从左到右编号：
这样的编号方式也同样适用于典型的树状结构：
mysql group by order by当我们为树状的结构编号时，我们从左到右，一次一层，为节点赋右值前先从左到右遍历其子节点给其子节点赋左右值。这种方法被称作改进的先序遍历算法。