设想你正在开发一个新闻网站，读者可以对文章评论，甚至相互回复，这样一来这个树就会延伸出很多分支，其深度也会大大增加，你选择一个简单的方案来实现需求：每条评论引用它所回复的评论。

1
2
3
4
5
6
CREATE TABLE comments(
	comment_id SERIAL PRIMARY KEY,
	parent_id BIGINT UNSIGNED,
	comment text NOT NULL,
	FOREIGN KEY (parent_id) REFERENCES comments(comment_id)
);

    这样一来，程序逻辑变得清晰明了，但是它并不能完成一棵树最基本的功能，就是遍历一整棵树

目的（分成存储与查询）

    递归关系的数据很常见，数据会像树或以层级方式组织，比如：

  • 组织机构图：职员与经理关系，每个职员有一个经理，同时经理也是一个职员
  • 线程化讨论：像引言中介绍的评论链。

    本篇对树结构定义：

  • 最上层的节点叫做根（root）节点，它没有父节点
  • 最底层的没有子节点的节点叫做叶（leaf）
  • 中间的节点简单地称为非叶节点（nonleaf）

反模式（总是依赖父节点，邻接表）

    最简单的方式就是添加parent_id，引用同一张表的其他条目，这样的设计也叫做邻接表，如下：

1
2
3
4
5
6
7
8
9
10
11
CREATE TABLE comment(
	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 comment(comment_id),
	FOREIGN KEY (bug_id) REFERENCES bug(bug_id),
	FOREIGN KEY (author) REFERENCES account(account_id)
);

    以下展示一个树结构
评论示意图

1.使用邻接表查询树

    在引言中提到，邻接表不能完成一棵树最基本的查询：虽然你可以使用关联查询出某一个节点的子节点，如下：

1
2
select c1.*, c2.* from comment c1
left join comment c2 on c2.parent_id = c1.comment_id

    但是，这个查询只能获取两层，如果要继续查询某个节点的孙子，就的再关联一层。但是树的深度是无止境的。
    另外还有一种办法，查询出所有的评论，然后再Java中重新构造这个树，但是大量的数据赋值，这是非常低效的。

2.使用邻接表维护树

    插入修改节点：使用邻接表，是非常简单

1
2
3
4
INSERT INTO comment(parent_id, bug_id, author, comment)
VALUES(7, 1234, 'Kukla', 'Thanks!');

UPDATE comment SET parent_id = 4 WHERE comment_id = 6;

    删除节点：但是删除节点会变得复杂，你必须从该节点下最低级子节点开始删除，以保证外键完整性

1
2
3
4
5
6
7
8
select comment_id from comment where parent_id = 4 -- return 5 and 6
select comment_id from comment where parent_id = 5 -- return none
select comment_id from comment where parent_id = 6 -- return 7
select comment_id from comment where parent_id = 7 -- return none

delete from comment where comment_id in (7);
delete from comment where comment_id in (5, 6);
delete from comment where comment_id = 4;

    这里虽然可以使用带 ON DELETE CASCADE 来修改外键，来使它自动完成以上操作。但是，如果需求是删除一个非叶子节点，并提升它的子节点，或将它子节点移动到另一个节点，如下：

1
2
3
4
5
6
-- 查出自己的父节点
select parent_id from comment where comment_id = 6; -- return 4
-- 修改自己所有的子节点的父节点为要删除节点的父节点
update comment set parent_id = 4 where parent_id = 6;
-- 删除自己
delete from comment where comment_id = 6;

如何识别反模式

     当你说过以下话，你可能正在使用“反模式”

  1. 我们的数结构要支持多少层
  2. 我们总是很害怕接触那些管理树结构的代码
  3. 我需要一个脚本来定期的清理树中的孤立节点数据

合理使用反模式

  1. 邻接表设计的优势在与能快速地获取一个给定节点的直接父子节点，也很容易插入新节点、维护节点、删除节点。如果树的分层结构不是很深，可以使用这种模式。
  2. 某些数据库提供了递归查询，可是使用WITH关键字来查询，
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    -- SQL Server 2005, Oracle 11g, IBM DB2, PostgreSQL 8.4
    with CommentTree(comment_id, parent_id, bug_id, author, comment_date, comment)
    as (
    	select * 0 as depth from comment
    	where parent_id is null
    	union all
    	select c.*, ct.depth+1 as depth from CommentTree ct 
    	join comment c on ct.comment_id = c.parent_id
    )
    select * from CommentTree where bug_id = 1234;
    -- Oracle 9i 和 10g 递归查询
    select * from comment
    start with comment_id = 9876
    connect by prior parent_id = comment_id

解决办法:使用其他树模型

1.路径枚举：

    用一个path字段保存当前节点的最顶层的祖先到自己的序列(路径)

1
2
3
4
5
6
7
8
9
10
CREATE TABLE comment(
	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 bug(bug_id),
	FOREIGN KEY (author) REFERENCES account(account_id)
);

评论示意图

查询评论#7（路径是1/4/6/7），的祖先
1
2
select * from comment where '1/4/6/7' like path || '%';
-- 它会匹配到 1/4/6/%，1/4/%，1/%的节点，而他们就是#7祖先
查询评论#4（路径是1/4），的子孙
1
2
select * from comment where path like '1/4/' || '%';
-- 它会匹配到 1/4/% 的节点，而他们就是#4子孙
查询评论#4，每个用户的评论数
1
2
select count(1) from comment where path like '1/4' || '%'
group by author
插入也简单

    只需要将父节点的path查出来，再追加自己的id就行了，但是一般id是自增，你需要先insert子节点，再select父节点，再update子节点

总结：
  1. 优点：查询方便
  2. 缺点：
  • 存在“乱穿马路”，不能保证存储的值的有效性。
  • 修改节点，比较麻烦，所有子节点的path也要修改
2.嵌套集：

    存储子孙节点的相关信息，而不是节点的直接祖先。

1
2
3
4
5
6
7
8
9
10
11
CREATE TABLE comment(
	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 bug(bug_id),
	FOREIGN KEY (author) REFERENCES account(account_id)
);

    要求：nsleft的数值小于该节点所有后代的id，nsright的数值大于所有后代的id。
评论示意图

查询评论#4及其所有后代
1
2
3
select c2.* from comment as c1
join comment as c2 on c2.nsleft between c1.nsleft and c1.nsright
where c1.comment_id=4;
查询评论#6的祖先
1
2
3
select c2.* from comment as c1
join comment as c2 on c1.nsleft between c2.nsleft and c2.nsright
where c1.comment_id=4;
删除指定节点

    可以直接删除，虽然再示例图中，左右两个值时有序的，而每个节点也是和它相邻的父兄节点进行比较，但是嵌套集设计并不必须保证分层关系。并且在你删除某节点后，该节点所有子节点自动上移

查询评论#6的直接父亲
1
2
3
4
5
6
7
8
select parent.* from comment as c 
	join comment as parent 
		on c.nsleft between parent.nsleft and parent.nsright
	left 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;
增加，移动节点

    这个对于嵌套集要复杂的多，你需要重新计算插入节点的相邻兄弟的节点、祖先节点和祖先节点的兄弟，来确保它们左右值都比这个新节点的左右值大，如果这个节点不是非叶节点，你还需要计算它的子孙节点。
    插入一个叶子节点，以下语句将更新每个需要更新的地方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-- make space for NS values 8 and 9
update comment
	set nsleft = case 
		where
			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!');
总结

优点：查询，简单快速。删除时，原来子节点的关系自动上移。
缺点：

  1. 查询一个节点的直接上级或下级，很困难。
  2. 增、改，困难。
3.闭包表：

    闭包表是解决分级存储一个简单而优雅的解决办法。
    创建另一张叫做tree_path，他包含两列，每一列都是一个指向comment中的comment_id

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
CREATE TABLE comment(
	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 bug(bug_id),
	FOREIGN KEY (author) REFERENCES account(account_id)
);

create table tree_path(
	ancestor bigint unsigned not null,
	descendant bigint unsigned not null,
	primary key(ancestor,descendant),
	foreign key(ancestor) references comment(comment_id),
	foreign key(descendant) references comment(comment_id)
);

    将树中任何一对具有祖先-后代关系的节点对都存储在tree_path的一行中，即使他们不是直接的父子关系，同时还增加一行指向自己。
评论示意图

查询评论#4的后代
1
2
3
select c.* from comment as c
join tree_path as t on c.comment_id = t.descendant
where t.ancestor = 4
查询评论#6的祖先
1
2
3
select c.* from comment as c
join tree_path as t on c.comment_id = t.ancestor
where t.descendant = 6
插入#5下的子节点#8
1
2
3
4
5
6
insert into tree_path（ancestor,descendant）
	select t.ancestor, 8
	from tree_path as t
	where t.descendant = 5
union all
	select 8, 8;
删除评论#4
1
2
3
4
5
-- 删除直接后代
delete from tree_path where descendant = 4;
-- 删除所有后代 
delete from tree_path 
where descendant in (select descendant from tree_path where ancestor = 4);
移动，#6从现在的位置(#4的孩子)移动到#3下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-- 删除所有子节点跟他祖先的关系
delete from tree_path 
where descendant in (
	select descendant from tree_path
	where ancestor = 6
) and ancestor in (
	select ancestor from tree_path
	where descendant = 6
	and ancestor != descendant
);
-- 建立新节点的关系
insert into tree_path (ancestor,descendant) 
	select supertree.ancestor,supertree.descendant from tree_path as supertree
		cross join tree_path as subtree
	where supertree.descendant = 3 and subtree.ancestor = 6;

你改使用哪种设计

  • 邻接表
        简单高效，如果你的数据库支持WITH或者CONNECT BY PRIOR的递归查询，那么邻接表是最高效的

  • 路劲枚举
        直观的看到祖先到后代关系，但无法保证引用完整性

  • 嵌套集
        无法保证引用完整性，太复杂。适用于查询小于非常高场景

  • 闭包表
        以空间换时间，通用的设计