第3章　单纯的树

Trees/intro/parent.sql
CREATE TABLE Comments (
 comment_id SERIAL PRIMARY KEY,
 parent_id BIGINT UNSIGNED,
 comment TEXT NOT NULL,
 FOREIGN KEY (parent_id) REFERENCES Comments(comment_id)
);

• 组织架构图。职员与经理的关系是典型的树形结构数据，出现在无数的SQL书籍与论题中。在组织架构图中，每个职员有一个经理，在树结构中表现为职员的父节点。同时，经理也是一个职员。
• 话题型讨论。正如引言中介绍的，树形结构也能用来表示回复评论的评论链。在这种树中，评论的子节点是它的回复。

Trees/anti/adjacency-list.sql
CREATE TABLE Comments(
   comment_id SERIAL PRIMARY KEY,
   parent_id BIGINT UNSIGNED,
   bug_id BIGINT UNSIGNED NOT NULL,
   author BIGINT UNSIGNED NOT NULL,
   comment_date DATETIME NOT NULL,
   comment TEXT NOT NULL,
   FOREIGN KEY (parent_id) REFERENCES Comments(comment_id),
   FOREIGN KEY (bug_id) REFERENCES Bugs(bug_id),
   FOREIGN KEY (author) REFERENCES Accounts(account_id)
 );

Trees/anti/parent.sql
SELECT c1.*, c2.* FROM Comments c1 LEFT OUTER JOIN Comments c2
   ON c2.parent_id = c1.comment_id;

Trees/anti/ancestors.sql
SELECT c1.*, c2.*, c3.*, c4.* FROM Comments c1                     -- 1st level
   LEFT OUTER JOIN Comments c2
     ON c2.parent_id = c1.comment_id  -- 2nd level
 LEFT OUTER JOIN Comments c3
   ON c3.parent_id = c2.comment_id  -- 3rd level 
 LEFT OUTER JOIN Comments c4
   ON c4.parent_id = c3.comment_id;  -- 4th level

Trees/anti/all-comments.sql
SELECT * FROM Comments WHERE bug_id = 1234;

Trees/anti/insert.sql
INSERT INTO Comments (bug_id, parent_id, author, comment)
   VALUES (1234, 7, 'Kukla', 'Thanks!');

Trees/anti/update.sql
UPDATE Comments SET parent_id = 3 WHERE
comment_id = 6;

Trees/anti/delete-subtree.sql
SELECT comment_id FROM Comments WHERE parent_id = 4; -- returns 5 and 6
SELECT comment_id FROM Comments WHERE parent_id = 5; -- returns none
SELECT comment_id FROM Comments WHERE parent_id = 6; -- returns 7
SELECT comment_id FROM Comments WHERE parent_id = 7; -- returns none
DELETE FROM Comments WHERE comment_id IN ( 7 );
DELETE FROM Comments WHERE comment_id IN ( 5, 6 );
DELETE FROM Comments WHERE comment_id = 4;

Trees/anti/delete-non-leaf.sql
SELECT parent_id FROM Comments WHERE comment_id = 6; -- returns 4
UPDATE Comments SET parent_id = 4 WHERE parent_id = 6;
DELETE FROM Comments WHERE comment_id = 6;

• “我们的树结构要支持多少层？”你正纠结于不使用递归查询获取一个给定节点的所有祖先或者后代。你做出让步，只支持有限层级数据的所有的操作，然后紧接着的一个很自然的问题就是：多少层才足够满足需求？
• “我总是很怕接触那些管理树结构的代码。”你已经采用了一种管理分层数据的比较复杂的方法，但使用的是错误的方法。每一项技术都会使得一些任务变得很简单，但通常是以其他的任务变得更复杂作为代价的。你可能选择了在应用程序设计中并不是最佳的方案来管理这些分层数据。
• “我需要一个脚本来定期地清理树中的孤立节点数据。”你的应用程序因为删除了非叶子节点而产生了一些迷失节点。在数据库中存储了一些复杂的结构时，需要确保在任何改变之后，这个结构都处在一致的、有效的状态下。你可以使用本章后面所描述的任何解决方案，同时配合触发器、级联外键等，来使得数据存储的结构更加适合项目需求，尽可能少地产生零碎的数据。

Trees/legit/cte.sql
WITH CommentTree
     (comment_id, bug_id, parent_id, author, comment, depth) AS (
     SELECT *, 0 AS depth FROM Comments
     WHERE parent_id IS NULL
      UNION ALL
     SELECT c.*, ct.depth+1 AS depth FROM CommentTree ct
       JOIN Comments c ON (ct.comment_id = c.parent_id)
     )  SELECT * FROM CommentTree WHERE bug_id = 1234;

Trees/legit/connect-by.sql
SELECT * FROM Comments START WITH comment_id = 9876 CONNECT BY PRIOR parent_id = comment_id;

Trees/soln/path-enum/create-table.sql
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)
 );

Trees/soln/path-enum/ancestors.sql
SELECT * FROM Comments AS c WHERE '1/4/6/7/' LIKE c.path || '%';

Trees/soln/path-enum/descendants.sql
SELECT * FROM Comments AS c WHERE c.path LIKE '1/4/' || '%';

Trees/soln/path-enum/count.sql
SELECT COUNT(*) FROM Comments AS c WHERE c.path LIKE '1/4/' || '%' GROUP BY c.author;

Trees/soln/path-enum/insert.sql
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();

Trees/soln/nested-sets/create-table.sql
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)
 );

Trees/soln/nested-sets/descendants.sql
SELECT c2.* FROM Comments AS c1
   JOIN Comments as c2
     ON c2.nsleft BETWEEN c1.nsleft AND c1.nsright WHERE c1.comment_id = 4;

Trees/soln/nested-sets/ancestors.sql
SELECT c2.* FROM Comments AS c1
   JOIN Comment AS c2
     ON c1.nsleft BETWEEN c2.nsleft AND c2.nsright WHERE c1.comment_id = 6;

Trees/soln/nested-sets/depth.sql
-- 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;

Trees/soln/nested-sets/parent.sql
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;

Trees/soln/nested-sets/insert.sql
-- 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!');

Trees/soln/closure-table/create-table.sql
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)
 );

Trees/soln/closure-table/descendants.sql
SELECT c.* FROM Comments AS c
   JOIN TreePaths AS t ON c.comment_id = t.descendant WHERE t.ancestor = 4;

Trees/soln/closure-table/ancestors.sql
SELECT c.* FROM Comments AS c
   JOIN TreePaths AS t ON c.comment_id = t.ancestor WHERE t.descendant = 6;

Trees/soln/closure-table/insert.sql
INSERT INTO TreePaths (ancestor, descendant)
   SELECT t.ancestor, 8
   FROM TreePaths AS t
   WHERE t.descendant = 5
  UNION ALL SELECT 8, 8;

Trees/soln/closure-table/delete-leaf.sql
DELETE FROM TreePaths WHERE descendant = 7;

Trees/soln/closure-table/delete-subtree.sql
DELETE FROM TreePaths WHERE descendant IN (SELECT descendant FROM TreePaths WHERE ancestor = 4);

Trees/soln/closure-table/move-subtree.sql
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);

Trees/soln/closure-table/move-subtree.sql
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;

Trees/soln/closure-table/child.sql
SELECT * FROM TreePaths WHERE ancestor = 4 AND path_length = 1;

• 邻接表是最方便的设计，并且很多软件开发者都了解它。
• 如果你使用的数据库支持WITH或者CONNECT BY PRIOR的递归查询，那能使得邻接表的查询更为高效。
• 枚举路径能够很直观地展示出祖先到后代之间的路径，但同时由于它不能确保引用完整性，使得这个设计非常地脆弱。枚举路径也使得数据的存储变得比较冗余。
• 嵌套集是一个聪明的解决方案——但可能过于聪明了，它不能确保引用完整性。最好在一个查询性能要求很高而对其他需求要求一般的场合来使用它。
• 闭包表是最通用的设计，并且本章所描述的设计中只有它能允许一个节点属于多棵树。它要求一张额外的表来存储关系，使用空间换时间的方案减少操作过程中由冗余的计算所造成的消耗。