本文接至SQL 反模式（一）
五、解决方案：用另外的树模型结构
相对邻接表来说，有几种其它的方法来存储层次结构数据，包括：Path Enumeration（路径枚举）, Nested Sets（嵌套集）,
和Closure Table(闭包表),下面三个部分展示了使用这些设计解决在“反模式”中的场景，存储和查询类似树集合的评论。
这些解决方案需要一些习惯。刚开始，它们可能看起来比邻接表更复杂，但是它们使得一些树操作更容易，
而使用邻接表设计模式会非常困难或效率低下。如果你的应用程序需要执行这些操作，那么这些设计比简单的邻接表是一个更好的选择。
Path Enumeration（路径枚举）
邻接表的一个缺点是，在树中检索指定节点的祖先节点是很昂贵的。在路径枚举中，通过将祖先存储成字符串，作为存储为节点。
你可以在目录层次结构中看到路径枚举的形式。像/usr/local/lib/这样的UNIX路径是文件系统的路径枚举，其中usr是local的父路径，后者反过来是lib的父路径。
在Comments表中，而不是parent_id列中，将名为path的列定义为一个长VARCHAR类型。该列中存储的字符串是当前行的祖先序列，
顺序为从顶向下，就像UNIX路径，你甚至可以选择/作为分隔符。
CREATE TABLE Comments (
comment_id SERIAL PRIMARY KEY,
path VARCHAR(1000),
bug_id BIGINT UNSIGNED NOT NULL,
author BIGINT UNSIGNED NOT NULL,
comment_date DATETIME NOT NULL,
comment TEXT NOT NULL,
FOREIGN KEY (bug_id) REFERENCES Bugs(bug_id),
FOREIGN KEY (author) REFERENCES Accounts(account_id)
);
表数据如下表5-1：
#表5-1#
#图5-1#
你可以通过比较当前行的路径和从另一行的路径形成的一条路径来查询祖先。
例如，找到评论#7 的祖先节点，其路径是1/4/6/7/，这样做：
SELECT *
FROM Comments AS c
WHERE '1/4/6/7/' LIKE c.path || '%' ;
这个模式匹配 1/4/6/%,1/4/%, and 1/%.
你可以通过倒转的方式来查询后代。若要查找路径为1/4/的#4评论的后代节点，请使用以下命令：
SELECT *
FROM Comments AS c
WHERE c.path LIKE '1/4/' || '%' ;
这种模式1/4/% 将匹配后代节点 1/4/5/, 1/4/6 和 1/4/6/7
一旦你可以轻松地选择树的子集或树顶的祖先链，你就可以轻松地执行许多其他查询，例如计算子树中节点成本的SUM()
或者简单地计算节点数。例如，要计算从#4评论开始的子树中每个作者的评论，可以执行以下操作：
SELECT COUNT(*)
FROM Comments AS c
WHERE c.path LIKE '1/4/' || '%'
GROUP BY c.author;
插入节点类似于在邻接表模型中的插入。你可以插入非叶节点，而无需修改任何其他行。
从新节点的父节点复制路径，并追加ID值到该字符串的新节点。如果主键在插入期间自动生成其值，
则可能需要插入行，然后更新path ，一旦你知道最新行的ID值。例如，如果你使用MySQL，
则内置函数LEVER_INSERT_ID()返回为当前会话中插入行生成的最新ID值。从新节点的父节点获取路径的其余部分。
INSERT INTO Comments (author, comment) VALUES ('Ollie' , 'Good job!' );
UPDATE Comments
SET path = (SELECT path FROM Comments WHERE comment_id = 7) || LAST_INSERT_ID() || '/'
WHERE comment_id = LAST_INSERT_ID();
路径枚举也有一些缺点：
1、数据库不能强制规定路径是正确形成的，或者路径中的值对应于存在的节点。
2、维护路径字符串取决于应用程序代码，并验证它的开销是非常昂贵的。无论你的VARCHAR列定义有多长，
它仍然有一个长度限制，因此它不严格支持无限的深度。
只要分隔符之间的元素具有一致的长度，路径枚举允许你根据它们的层级轻松地对一组行进行排序。
Nested Sets（嵌套集）
嵌套集解决方案将信息存储在每个节点中，每个节点对应于其后代的集合，而不是节点的直接父节点。
这个信息可以通过编码每个节点来表示。 在树中对应两个值，你可以称之为nsleft和nsright。
CREATE TABLE Comments (
comment_id SERIAL PRIMARY KEY,
nsleft INTEGER NOT NULL,
nsright INTEGER NOT NULL,
bug_id BIGINT UNSIGNED NOT NULL,
author BIGINT UNSIGNED NOT NULL,
comment_date DATETIME NOT NULL,
comment TEXT NOT NULL,
FOREIGN KEY (bug_id) REFERENCES Bugs (bug_id),
FOREIGN KEY (author) REFERENCES Accounts(account_id)
);
每个节点都给nsleft和nsright值用下列方式：nsleft值小于所有节点的子节点值，而nsright大于所有节点的子节点值。这些值与comment_id值无关。
分配这些值的一种简单方法是遵循树的深度优先遍历，在树的分支下降时递增地分配nsleft值，上升返回时分配nsright值。
如下图5-2和图5-3所示
#图5-2#
#图5-3#
一旦为每个节点分配了这些值，就可以使用它们查找任何指定节点的祖先和后代。
例如，你可以检索评论#4及其后代，方法是搜索其编号介于当前节点的nsleft和nsright之间的节点。
SELECT c2.*
FROM Comments AS c1
JOIN Comments as c2
ON c2.nsleft BETWEEN c1.nsleft AND c1.nsright
WHERE c1.comment_id = 4;
你可以通过搜索跨度在当前节点值范围内的节点，来检索评论#6和它的祖先。例如:
SELECT c2.*
FROM Comments AS c1
JOIN Comment AS c2
ON c1.nsleft BETWEEN c2.nsleft AND c2.nsright
WHERE c1.comment_id = 6;
嵌套集设计的一个主要优点是，当你删除非叶节点时，其后代将自动视为已删除节点的父节点的直接子节点。
虽然插图中显示的每个节点的左和右都有一个值，构成一个连续的序列，而且与相邻的兄弟姐妹和父母相比，值总是唯一的。
这对于嵌套集设计来保持层次结构是不必要的。因此，当值中的空白是由于删除节点而产生时，树结构就不会中断。
例如，你可以计算指定节点的深度并删除其父节点，然后当你再次计算节点的深度时，该节点的深度似乎降低了一个层次。
-- Reports depth = 3
SELECT c1.comment_id, COUNT(c2.comment_id) AS depth
FROM Comment AS c1 JOIN Comment AS c2
ON c1.nsleft BETWEEN c2.nsleft AND c2.nsright WHERE c1.comment_id = 7
GROUP BY c1.comment_id;
DELETE FROM Comment WHERE comment_id = 6;
-- Reports depth = 2
SELECT c1.comment_id, COUNT(c2.comment_id) AS depth
FROM Comment AS c1 JOIN Comment AS c2
ON c1.nsleft BETWEEN c2.nsleft AND c2.nsright WHERE c1.comment_id = 7
GROUP BY c1.comment_id;
然而，一些在邻接表设计中很简单的查询，例如检索直接子节点或直接父节点，在嵌套集设计中要复杂得多。
指定节点C1的直接父节点是该节点的祖先，但它们之间不存在其他节点。因此，你可以使用额外的外部联接(outer join)来搜索既是C1节点的祖先，又是其父母节点的后代 的那个节点。
只有在没有找到这样的节点时(即外部连接outer join的结果为NULL)，祖先才真正是C1的直接父节点。
SELECT parent.*
FROM Comment AS c
JOIN Comment AS parent
ON c.nsleft BETWEEN parent.nsleft AND parent.nsright
LEFT OUTER JOIN Comment AS in_between
ON c.nsleft BETWEEN in_between.nsleft AND in_between.nsright
AND in_between.nsleft BETWEEN parent.nsleft AND parent.nsright
WHERE c.comment_id = 6
AND in_between.comment_id IS NULL;
在嵌套集设计中，树的操作、插入和移动节点通常比在其他模型中更加复杂。
插入新节点时，需要重新计算所有大于新节点左值的左、右值。
这包括新节点的正确同级、其祖先以及其祖先的正确同级。如果将新节点插入为非叶节点，则还包括后代。
假设新节点是一个叶节点，下面的语句应该更新所有必需的内容：
--make space for NS values 8 and 9
UPDATE Comment
SET nsleft = CASE WHEN nsleft >= 8 THEN nsleft+2 ELSE nsleft END, nsright = nsright+2
WHERE nsright >= 7;
--create new child of comment #5, occupying NS values 8 and 9
INSERT INTO Comment (nsleft, nsright, author, comment)
VALUES (8, 9, 'Fran' , 'Me too!' );
当更重要的是快速、容易地执行子树查询时，嵌套集模型是最好的，而不是在单个节点上执行操作。
插入和移动节点很复杂，由于需要重新编号左值和右值。如果树的使用涉及频繁的插入，嵌套集不是最佳选择。
Closure Table(闭包表)
闭包表解决方案是一种简单而又优雅的存储层次数据的方法。它包括通过树存储所有的路径，而不仅仅是那些具有直接的父子关系的路径。
除了一个普通的Comments表外，还需要创建另一个TreePaths表，其中包含两列，每个列都是Comments的外键。
CREATE TABLE Comments (
comment_id SERIAL PRIMARY KEY,
bug_id BIGINT UNSIGNED NOT NULL,
author BIGINT UNSIGNED NOT NULL,
comment_date DATETIME NOT NULL,
comment TEXT NOT NULL,
FOREIGN KEY (bug_id) REFERENCES Bugs(bug_id),
FOREIGN KEY (author) REFERENCES Accounts(account_id)
);
CREATE TABLE TreePaths (
ancestor BIGINT UNSIGNED NOT NULL,
descendant BIGINT UNSIGNED NOT NULL,
PRIMARY KEY(ancestor, descendant),
FOREIGN KEY (ancestor) REFERENCES Comments(comment_id),
FOREIGN KEY (descendant) REFERENCES Comments(comment_id)
);
不要使用Comments表来存储有关树结构的信息，而是使用TreePaths表。在此表中为共享祖先/后代关系的树中的每一对节点存储一行，
即使它们在树中被多个层次分隔。还为每个节点添加一行以引用自身，来说明节点是如何配对的。
如下图5-4和图5-5所示：
#图5-4#
#图5-5#
从该表检索祖先和后代的查询甚至比嵌套集解决方案中的查询更简单。
若要检索评论#4的后代，请在祖先为4的TreePath表中匹配行：
SELECT c.*
FROM Comments AS c
JOIN TreePaths AS t ON c.comment_id = t.descendant
WHERE t.ancestor = 4;
若要检索评论#6的祖先，请在后代为6的TreePath表中匹配行：
SELECT c.*
FROM Comments AS c
JOIN TreePaths AS t ON c.comment_id = t.ancestor
WHERE t.descendant = 6;
要插入新的叶节点，例如评论#5的新子节点，首先插入自引用行。
然后添加TreePath表中一组行的副本，该副本将评论#5引用为后代(包含在评论#5中引用自己的行)，
将后代替换为新评论的编号：
INSERT INTO TreePaths (ancestor, descendant)
SELECT t.ancestor, 8
FROM TreePaths AS t
WHERE t.descendant = 5
UNION ALL
SELECT 8, 8;
要删除一个叶子节点，比如评论#7，在TreePath表中删除所有那些引用评论#7，作为后代的行：
DELETE FROM TreePaths WHERE descendant = 7;
要删除完整的子树，例如评论#4及其后代，请删除引用评论#4作为后代的TreePaths中的所有行，
以及评论#4的任何后代引用为后代的所有行：
DELETE FROM TreePaths
WHERE descendant IN (SELECT descendant
FROM TreePaths
WHERE ancestor = 4);
请注意，如果删除TreePaths表中的行，这并不会删除Comments本身。
对于这个评论示例来说，这似乎很奇怪，但如果你正在使用其他类型的树，例如产品目录中的类别或组织结构图中的员工，则更有意义。
当你将节点的关系更改为其他节点时，不一定要删除它。当你将路径存储在单独的表中时，它有助于使其更加灵活。
若要将子树从树的一个位置移动到另一个位置，首先，通过删除引用子树中顶部节点的祖先和该节点的后代的行，从其祖先树中提取子树。
例如，要将评论#6从评论#4的子节点位置移到评论#3的子节点，请从以下删除开始，确保不要删除评论6的自我引用。
DELETE FROM TreePaths
WHERE descendant IN (SELECT descendant
FROM TreePaths
WHERE ancestor = 6)
AND ancestor IN (SELECT ancestor
FROM TreePaths
WHERE descendant = 6
AND ancestor != descendant);
通过选择#6的祖先(而不是#6本身)和#6(包括#6)的后代，这正确地删除了从#6的祖先到#6的后代的所有路径。
换句话说，这将删除这些路径（1, 6），（1, 7），（4, 6），和（4, 7）。它不删除（6, 6）或（6, 7）。
然后，通过插入与新位置的转接器和子树的后代匹配的行，添加孤立子树。
你可以使用CROSS JOIN(交叉连接)语法来创建一个笛卡儿产品
将新位置的祖先匹配到子树中所有需要移动的节点所需的行。
INSERT INTO TreePaths (ancestor, descendant)
SELECT supertree.ancestor, subtree.descendant
FROM TreePaths AS supertree
CROSS JOIN TreePaths AS subtree
WHERE supertree.descendant = 3
AND subtree.ancestor = 6;
这将使用#3(包括#3)的祖先和#6(包括#6)的后代创建新的路径。
因此，新的路径是(1，6)，(2，6)，(3，6)，(1，7)，(2，7)，(3，7)。
结果是从评论#6开始的子树被重新定位为评论#3的子节点。
交叉连接创建所有所需的路径，即使子树被移动到树中的更高或更低的级别。
闭包表设计比嵌套集设计更直接。两种方法都有快速简便的方法来查询祖先和后代，
但是闭包表更容易维护分层结构信息。在这两种设计中，查询直接子节点或父节点比在邻接表或路径枚举设计中更方便。
然而，你可以改进闭包表，更容易查询直接的父节点或子节点。添加一个TreePaths表的path_length属性闭包表设计。
一个节点的自引用路径path_length为零，其直接子节点的路径path_length为1，其外孙的路径path_length为2，依此类推。
现在，找到评论#4的子项很简单：
SELECT *
FROM TreePaths
WHERE ancestor = 4 AND path_length = 1;
比较层次结构数据的设计如表5-6：
#表5-6#
总结： 应该用哪一种设计方式？
每一种设计都有自己的长处和弱点。根据需要最有效的操作选择设计。
在每个树的设计中，有些操作被标记为简单或困难。你还可以考虑每种设计的以下优点和缺点：
Adjacency List 邻接表，是最传统的设计，许多软件开发人员都认识到它.
Recursive Queries 递归查询，使用WITH或CONNECT BY PRIOR的递归查询可以更有效地使用邻接表设计，只要使用支持语法的数据库品牌之一。
Path Enumeration 路径枚举 ，对于用户界面中的面包屑是有益的，但是它是脆弱的，因为它不能强制执行引用完整性并冗余地存储信息。
Nested Sets 嵌套集合，是一个聪明的解决方案--也许太聪明了。它也不能支持引用完整性。当你需要比修改树更频繁地查询树时，最好使用它。
Closure Table 闭包表，是最通用的设计，也是本章中唯一允许节点属于多棵树的设计。它需要一个额外的表来存储关系。这种设计在编码深度层次结构时也使用了很多行，增加了空间消耗，以减少计算。
本文翻译自 Bill_Karwin-SQL_Antipatterns-EN 书籍第三章
如有转载，请标明来源：http://www.cnblogs.com/wjq310/p/8849896.html