侧边栏壁纸
  • 累计撰写 793 篇文章
  • 累计创建 1 个标签
  • 累计收到 1 条评论
标签搜索

目 录CONTENT

文章目录

树形数据存储

Dettan
2021-04-10 / 0 评论 / 0 点赞 / 215 阅读 / 2,722 字
温馨提示:
本文最后更新于 2022-07-23,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。
发明了一种新的树结构数据库存储方案 - - ITeye博客
最近在开发jSqlBox过程中,想研究一下树形结构和VO对象树的转换,突然发现一种新的树结构数据库存储方案,在网上搜索了一下,没有找到雷同的(也可能是我花的时间不够)方案,现介绍如下: 目前常见的树形结构数据库存储方案有以下四种,但是都存在一定问题: 1)Adjacency List::记录父节点。优点是简单,缺点是访问子树需要遍历,发出许多条SQL,对数据库压力大。 2)Path Enumerations:用一个字符串记录整个路径。优点是查询方便,缺点是插入新记录时要手工更改此节点以下所有路径,很容易出错。 3)Closure Table:专门一张表维护Path,缺点是占用空间大,操作不直观。 4)Nested Sets:记录左值和右值,缺点是复杂难操作。 以上方法都存在一个共同缺点:操作不直观,不能直接看到树结构,不利于开发和调试。 本文介绍的方法我暂称它为"简单粗暴多列存储法",它与Path Enumerations有点类似,但区别是用很多的数据库列来存储一个占位符(1或空值),如下图(https://github.com/drinkjava2/Multiple-Columns-Tree/blob/master/treemapping.jpg) 左边的树结构,映射在数据库里的结构见右图表格: 各种SQL操作如下: 1.获取(或删除)指定节点下所有子节点,已知节点的行号为"X",列名"cY": select *(or delete) from tb where line>=X and line X and (cY=1 or c(Y-1)=1 or c(Y-2)=1 ...
http://drinkjava2.iteye.com/blog/2353983

邻接表
邻接表的优缺分析
对于以上邻接表,很多程序员已经将其当成默认的解决方案了,但即便是这样,但它在从前还是有存在的问题的。
分析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.
删除
直接删

0

评论区