邻接表
邻接表的优缺分析
对于以上邻接表,很多程序员已经将其当成默认的解决方案了,但即便是这样,但它在从前还是有存在的问题的。
分析1:查询一个节点的所有后代(求子树)怎么查呢?
我们先看看以前查询两层的数据的SQL语句:
SELECT c1.*,c2.*
FROM Comments c1 LEFT OUTER JOIN Comments2 c2
ON c2.ParentId = c1.CommentId
显然,每需要查多一层,就需要联结多一次表。SQL查询的联结次数是有限的,因此不能无限深的获取所有的后代。而且,这种这样联结,执行Count()这样的聚合函数也相当困难。
说了是以前了,现在什么时代了,在SQLServer 2005之后,一个公用表表达式就搞定了,顺带解决的还有聚合函数的问题(聚合函数如Count()也能够简单实用),例如查询评论4的所有子节点:
WITH COMMENT_CTE(CommentId,ParentId,CommentBody,tLevel)
AS
(
--基本语句
SELECT CommentId,ParentId,CommentBody,0 AS tLevel FROM Comment
WHERE ParentId =4UNION ALL --递归语句
SELECT c.CommentId,c.ParentId,c.CommentBody,ce.tLevel + 1 FROM Comment AS c
INNER JOIN COMMENT_CTE AS ce --递归查询
ON c.ParentId = ce.CommentId
)
SELECT * FROM COMMENT_CTE
显示结果如下:
那么查询祖先节点树又如何查呢?例如查节点6的所有祖先节点:
WITH COMMENT_CTE(CommentId,ParentId,CommentBody,tLevel)
AS
(
--基本语句
SELECT CommentId,ParentId,CommentBody,0 AS tLevel FROM Comment
WHERE CommentId =6UNION ALL
SELECT c.CommentId,c.ParentId,c.CommentBody,ce.tLevel -1 FROM Comment AS c
INNER JOIN COMMENT_CTE AS ce --递归查询
ON ce.ParentId = c.CommentId
where ce.CommentId <> ce.ParentId
)
SELECT * FROM COMMENT_CTE ORDER BY CommentId ASC
结果如下:
再者,由于公用表表达式能够控制递归的深度,因此,你可以简单获得任意层级的子树。
OPTION(MAXRECURSION 2)
看来哥是为邻接表平反来的。
分析2:当然,邻接表也有其优点的,例如要添加一条记录是非常方便的。
INSERT INTO Comment(ArticleId,ParentId)... --仅仅需要提供父节点Id就能够添加了。
分析3:修改一个节点位置或一个子树的位置也是很简单.
UPDATE Comment SET ParentId = 10 WHERE CommentId = 6 --仅仅修改一个节点的ParentId,其后面的子代节点自动合理。
分析4:删除子树
想象一下,如果你删除了一个中间节点,那么该节点的子节点怎么办(它们的父节点是谁),因此如果你要删除一个中间节点,那么不得不查找到所有的后代,先将其删除,然后才能删除该中间节点。
当然这也能通过一个ON DELETE CASCADE级联删除的外键约束来自动完成这个过程。
分析5:删除中间节点,并提升子节点
面对提升子节点,我们要先修改该中间节点的直接子节点的ParentId,然后才能删除该节点:
SELECT ParentId FROM Comments WHERE CommentId = 6; --搜索要删除节点的父节点,假设返回4
UPDATE Comments SET ParentId = 4 WHERE ParentId = 6; --修改该中间节点的子节点的ParentId为要删除中间节点的ParentId
DELETE FROM Comments WHERE CommentId = 6; --终于可以删除该中间节点了
由上面的分析可以看到,邻接表基本上已经是很强大的了。
闭包表
外加一个单独的表存储节点所有的子孙节点. 这样查找子孙和祖先都十分容易, 插入删除也容易, 但是查找儿子和爸爸麻烦, 可以额外加一个深度来解决.
基础表
CREATE TABLE Comments(
CommentId int PK,
ArticleId int,
CommentBody int,
FOREIGN KEY(ArticleId) REFERENCES Articles(Id)
)
父子关系表:
CREATE TABLE TreePaths(
ancestor int,
descendant int,
PRIMARY KEY(ancestor,descendant), --复合主键
FOREIGN KEY (ancestor) REFERENCES Comments(CommentId),
FOREIGN KEY (descendant) REFERENCES Comments(CommentId)
)
优点:
1、查询所有后代节点(查子树):
SELECT c.* FROM Comment AS c
INNER JOIN TreePaths t on c.CommentId = t.descendant
WHERE t.ancestor = 4
2、查询评论6的所有祖先(查祖先树):
SELECT c.* FROM Comment AS c
INNER JOIN TreePaths t on c.CommentId = t.ancestor
WHERE t.descendant = 6
3、插入新节点:
要插入一个新的叶子节点,应首先插入一条自己到自己的关系,然后搜索TreePaths表中后代是评论5的节点,增加该节点与要插入的新节点的"祖先-后代"关系。
比如下面为插入评论5的一个子节点的TreePaths表语句:
INSERT INTO TreePaths(ancestor,descendant)
SELECT t.ancestor,8FROM TreePaths AS t
WHERE t.descendant = 5UNION ALL
SELECT 8,8
执行以后:
至于Comment表那就简单得不说了。
4、删除叶子节点:
比如删除叶子节点7,应删除所有TreePaths表中后代为7的行:
DELETE FROM TreePaths WHERE descendant = 7
5、删除子树:
要删除一颗完整的子树,比如评论4和它的所有后代,可删除所有在TreePaths表中的后代为4的行,以及那些以评论4的后代为后代的行:
DELETE FROM TreePaths
WHERE descendant
IN(SELECT descendant FROM TreePaths WHERE ancestor = 4)
另外,移动节点,先断开与原祖先的关系,然后与新节点建立关系的SQL语句都不难写。
另外,闭包表还可以优化,如增加一个path_length字段,自我引用为0,直接子节点为1,再一下层为2,一次类推,查询直接自子节点就变得很简单。
路径枚举
CommentId Path CommentBody
1 1/ 这个Bug的成因是什么
2 1/2/ 我觉得是一个空指针
3 1/2/3 不是,我查过了
4 1/4/ 我们需要查无效的输入
5 1/4/5/ 是的,那是个问题
6 1/4/6/ 好,查一下吧。
7 1/4/6/7/ 解决了
优点
•
查询所有祖先非常容易
SELECT * FROM Comment AS c
WHERE '1/4/6/7/' LIKE c.path + '%'
•
查询所有后代
SELECT * FROM Comment AS c
WHERE c.Path LIKE '1/4/%'
•
插入 也 十分容易.
•
能够很方便地根据节点的层级排序,因为路径中分隔两边的节点间的距离永远是1,因此通过比较字符串长度就能知道层级的深浅。
缺点
•
删除时需要做许多额外工作
要删除所有path中的节点 , 要保证path中的数据时一直有效的.
•
VARCHAR的长度很难确定。无论VARCHAR的长度设为多大,都存在不能够无限扩展的情况。
顺序深度
存顺序和深度
操作
1.
查 直接父节点
•
顺序靠前,深度小1的最近节点。( where line <.. and level = ..-1 )
2.
查 第N代父辈
•
顺序靠前,深度小N的最近节点。
3.
查 儿子
•
顺序靠后,深度连续大1的节点。( where line>.. and line < (select min(line) where line >.. and level==..) and level = ..+1 )
4.
查 第N代儿子
5.
查 所有兄弟
•
相邻同深度节点 (全表扫描)
6.
插入
•
插入,层级直接设,就是顺序哪里有点困难,(全表顺序都可能要变,可以把顺序弄成不是连续的,只表示一个大小就好)
7.
删除
•
直接删
评论区