数据库树型规划[转]ITeye - 威尼斯人

数据库树型规划[转]ITeye

2019-01-10 11:45:25 | 作者: 博耘 | 标签: 节点,规划,一个 | 浏览: 2668

 

信任有过开发经历的朋友都曾碰到过这样一个需求。假定你正在为一个新闻网站开发一个谈论功用,读者能够谈论原文乃至彼此回复。

这个需求并不简略,彼此回复会导致无限多的分支,无限多的先人-子孙联系。这是一种典型的递归联系数据。

关于这个问题,以下给出几个处理计划,各位客观可酌量后挑选。

一、邻接表:依靠父节点

邻接表的计划如下(仅仅阐明问题):

 CREATE TABLE Comments(
 CommentId int PK,
 ParentId int, --记载父节点
 ArticleId int,
 CommentBody nvarchar(500),
 FOREIGN KEY (ParentId) REFERENCES Comments(CommentId) --自衔接,主键外键都在自己表内
 FOREIGN KEY (ArticleId) REFERENCES Articles(ArticleId)
 )

由于偷闲,所以选用了书本中的图了,Bugs便是Articles:

这种规划方法就叫做邻接表。这或许是存储分层结构数据中最一般的计划了。

下面给出一些数据来显现一下谈论表中的分层结构数据。示例表:

图片阐明存储结构:

邻接表的优缺剖析

关于以上邻接表,许多程序员现已将其当成默许的处理计划了,但即便是这样,但它在早年仍是有存在的问题的。

剖析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)
 --根本句子
 SELECT CommentId,ParentId,CommentBody,0 AS tLevel FROM Comment
 WHERE ParentId = 4
 UNION 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)
 --根本句子
 SELECT CommentId,ParentId,CommentBody,0 AS tLevel FROM Comment
 WHERE CommentId = 6
 UNION 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; --总算能够删去该中心节点了

由上面的剖析能够看到,邻接表根本上现已是很强壮的了。

二、途径枚举

途径枚举的规划是指经过将一切先人的信息联组成一个字符串,并保存为每个节点的一个特点。

途径枚举是一个由接连的直接层级联系组成的完好途径。如"/home/account/login",其间home是account的直接父亲,这也就意味着home是login的先人。

仍是有方才新闻谈论的比方,咱们用途径枚举的方法来替代邻接表的规划:

 CREATE TABLE Comments(
 CommentId int PK,
 Path varchar(100), --仅仅改变了该字段和删去了外键
 ArticleId int,
 CommentBody nvarchar(500),
 FOREIGN KEY (ArticleId) REFERENCES Articles(ArticleId)
 )

  简略阐明问题的数据表如下:

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/ 处理了

途径枚举的长处:

关于以上表,假定咱们需求查询某个节点的悉数先人,SQL句子能够这样写(假定查询7的一切先人节点):

SELECT * FROM Comment AS c
WHERE 1/4/6/7/ LIKE c.path + %

成果如下:

假定咱们要查询某个节点的悉数子孙,假定为4的子孙:

SELECT * FROM Comment AS c
WHERE c.Path LIKE 1/4/%

成果如下:

一旦咱们能够很简略地获取一个子树或许从子孙节点到先人节点的途径,就能够很简略地完成更多查询,比方核算一个字数一切节点的数量(COUNT聚合函数)

  刺进一个节点也能够像和运用邻接表相同地简略。能够刺进一个叶子节点而不必修正任何其他的行。你所需求做的仅仅仿制一份要刺进节点的逻辑上的父亲节点途径,并将这个新节点的Id追加到途径结尾就能够了。假如这个Id是刺进时由数据库生成的,你或许需求先刺进这条记载,然后获取这条记载的Id,并更新它的途径。

途径枚举的缺陷:

1、数据库不能保证途径的格局总是正确或许途径中的节点的确存在(中心节点被删去的状况,没外键束缚)。

2、要依靠高档程序来保护途径中的字符串,而且验证字符串的正确性的开支很大。

3、VARCHAR的长度很难确认。不管VARCHAR的长度设为多大,都存在不能够无限扩展的状况。

途径枚举的规划方法能够很便利地依据节点的层级排序,由于途径中分隔两头的节点间的间隔永远是1,因而经过比较字符串长度就能知道层级的深浅。

三、嵌套集

嵌套集处理计划是存储子孙节点的信息,而不是节点的直接先人。咱们运用两个数字来编码每个节点,表明这个信息。能够将这两个数字称为nsleft和nsright。

仍是以上面的新闻-谈论作为比方,关于嵌套集的方法表能够规划为:

 CREATE TABLE Comments(
 CommentId int PK,
 nsleft int, --之前的一个父节点
 nsright int, --变成了两个
 ArticleId int,
 CommentBody nvarchar(500),
 FOREIGN KEY (ArticleId) REFERENCES Articles(ArticleId)
 )

nsleft值的确认:nsleft的数值小于该节点一切子孙的Id。

nsright值的确认:nsright的值大于该节点一切子孙的Id。

当然,以上两个数字和CommentId的值并没有任何相关,确认值的方法是对树进行一次深度优先遍历,在逐层入神的进程中顺次递加地分配nsleft的值,并在回来时顺次递加地分配nsright的值。

选用书中的图来阐明一下状况:

一旦你为每个节点分配了这些数字,就能够运用它们来找到给定节点的先人和子孙。

嵌套集的长处:

我觉得是仅有的长处了,查询先人树和子树便利。

例如,经过查找那些节点的ConmentId在谈论4的nsleft与nsright之间就能够取得其及其一切子孙:

 SELECT c2.* FROM Comments AS c1
 JOIN Comments AS c2 ON cs.neleft BETWEEN c1.nsleft AND c1.nsright
 WHERE c1.CommentId = 1;

成果如下:

经过查找谈论6的Id在哪些节点的nsleft和nsright规模之间,就能够获取谈论6及其一切先人:

 SELECT c2.* FROM Comment AS c1
 JOIN Comment AS c2 ON c1.nsleft BETWEEN c2.nsleft AND c2.nsright
 WHERE c1.CommentId = 6;

这种嵌套集的规划还有一个长处,便是当你想要删去一个非叶子节点时,它的子孙会主动地替代被删去的节点,称为其直接先人节点的直接子孙。

嵌套集规划并不有必要保存分层联系。因而当删去一个节点形成数值不接连时,并不会对树的结构发生任何影响。

嵌套集缺陷:

1、查询直接父亲。

在嵌套集的规划中,这个需求的完成的思路是,给定节点c1的直接父亲是这个节点的一个先人,且这两个节点之间不该该有任何其他的节点,因而,你能够用一个递归的外联合来查询一个节点,它便是c1的先人,也一起是另一个节点Y的子孙,随后咱们使y=x就查询,直到查询回来空,即不存在这样的节点,此刻y便是c1的直接父亲节点。

比方,要找到谈论6的直接父节点:老实说,SQL句子又长又臭,行肯定是行,但我真的写不动了。

2、对树进行操作,比方刺进和移动节点。

当刺进一个节点时,你需求从头核算新刺进节点的相邻兄弟节点、先人节点和它先人节点的兄弟,来保证它们的左右值都比这个新节点的左值大。一起,假如这个新节点是一个非叶子节点,你还要查看它的子孙节点。

够了,够了。就凭查直接父节点都困难,这个东西就很冷门了。我确认我不会运用这种规划了。

四、闭包表

闭包表是处理分层存储一个简略而又高雅的处理计划,它记载了表中一切的节点联系,并不仅仅是直接的父子联系。
在闭包表的规划中,额定创建了一张TreePaths的表(空间交换时刻),它包括两列,每一列都是一个指向Comments中的CommentId的外键。

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)
)

在这种规划中,Comments表将不再存储树结构,而是将书中的先人-子孙联系存储为TreePaths的一行,即便这两个节点之间不是直接的父子联系;一起还添加一行指向节点自己,了解不了?便是TreePaths表存储了一切先人-子孙的联系的记载。如下图:

Comment表:

TreePaths表:

长处:

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,8
 FROM TreePaths AS t
 WHERE t.descendant = 5
 UNION 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,一次类推,查询直接自子节点就变得很简略。

其实,在以往的工作中,曾见过不同类型的规划,邻接表,途径枚举,邻接表途径枚举一起来的都见过。

每种规划都各有好坏,假如挑选规划依靠于应用程序中哪种操作最需求性能上的优化。

下面给出一个表格,来展现各种规划的难易程度:

版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表威尼斯人立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章

阅读排行

  • 1
  • 2
  • 3
  • 4

    MongoDBITeye

    文档,测验,调集
  • 5

    RAC的Diskgroup重建ITeye

    磁盘,重建,数据库
  • 6

    Switch to UTFITeye

    编码,设置,文件
  • 7

    pl/sql使用之使用utlITeye

    文件,办法,输出
  • 8
  • 9

    (转)in 和 existITeye

    分区,查询,一个
  • 10

    oracle正则表达式ITeye

    正则表达式,匹配,表达式