这个需求并不简单,相互回复会导致无限多的分支,无限多的祖先-后代关系。这是一种典型的递归关系数据。
对于这个问题,以下给出几个解决方案,各位客观可斟酌后选择。
邻接表的方案如下(仅仅说明问题):
这种设计方式就叫做邻接表。这可能是存储分层结构数据中最普通的方案了。
图片说明存储结构:
邻接表的优缺分析
对于以上邻接表,很多程序员已经将其当成默认的解决方案了,但即便是这样,但它在从前还是有存在的问题的。
分析1:查询一个节点的所有后代(求子树)怎么查呢?
我们先看看以前查询两层的数据的SQL语句:
SELECTc1.*,c2.*FROMCommentsc1LEFTOUTERJOINComments2c2ONc2.ParentId=c1.CommentId显然,每需要查多一层,就需要联结多一次表。SQL查询的联结次数是有限的,因此不能无限深的获取所有的后代。而且,这种这样联结,执行Count()这样的聚合函数也相当困难。
那么查询祖先节点树又如何查呢?例如查节点6的所有祖先节点:
再者,由于公用表表达式能够控制递归的深度,因此,你可以简单获得任意层级的子树。
OPTION(MAXRECURSION2)看来哥是为邻接表平反来的。
分析2:当然,邻接表也有其优点的,例如要添加一条记录是非常方便的。
INSERTINTOComment(ArticleId,ParentId)...--仅仅需要提供父节点Id就能够添加了。分析3:修改一个节点位置或一个子树的位置也是很简单.
UPDATECommentSETParentId=10WHERECommentId=6--仅仅修改一个节点的ParentId,其后面的子代节点自动合理。分析4:删除子树
想象一下,如果你删除了一个中间节点,那么该节点的子节点怎么办(它们的父节点是谁),因此如果你要删除一个中间节点,那么不得不查找到所有的后代,先将其删除,然后才能删除该中间节点。
当然这也能通过一个ONDELETECASCADE级联删除的外键约束来自动完成这个过程。
分析5:删除中间节点,并提升子节点
面对提升子节点,我们要先修改该中间节点的直接子节点的ParentId,然后才能删除该节点:
SELECTParentIdFROMCommentsWHERECommentId=6;--搜索要删除节点的父节点,假设返回4UPDATECommentsSETParentId=4WHEREParentId=6;--修改该中间节点的子节点的ParentId为要删除中间节点的ParentIdDELETEFROMCommentsWHERECommentId=6;--终于可以删除该中间节点了由上面的分析可以看到,邻接表基本上已经是很强大的了。
路径枚举的设计是指通过将所有祖先的信息联合成一个字符串,并保存为每个节点的一个属性。
路径枚举是一个由连续的直接层级关系组成的完整路径。如"/home/account/login",其中home是account的直接父亲,这也就意味着home是login的祖先。
CommentIdPathCommentBody
11/这个Bug的成因是什么
21/2/我觉得是一个空指针
31/2/3不是,我查过了
41/4/我们需要查无效的输入
51/4/5/是的,那是个问题
61/4/6/好,查一下吧。
71/4/6/7/解决了
路径枚举的优点:
对于以上表,假设我们需要查询某个节点的全部祖先,SQL语句可以这样写(假设查询7的所有祖先节点):
SELECT*FROMCommentAScWHERE'1/4/6/7/'LIKEc.path+'%'结果如下:
假设我们要查询某个节点的全部后代,假设为4的后代:
SELECT*FROMCommentAScWHEREc.PathLIKE'1/4/%'结果如下:
一旦我们可以很简单地获取一个子树或者从子孙节点到祖先节点的路径,就可以很简单地实现更多查询,比如计算一个字数所有节点的数量(COUNT聚合函数)
插入一个节点也可以像和使用邻接表一样地简单。可以插入一个叶子节点而不用修改任何其他的行。你所需要做的只是复制一份要插入节点的逻辑上的父亲节点路径,并将这个新节点的Id追加到路径末尾就可以了。如果这个Id是插入时由数据库生成的,你可能需要先插入这条记录,然后获取这条记录的Id,并更新它的路径。
路径枚举的缺点:
1、数据库不能确保路径的格式总是正确或者路径中的节点确实存在(中间节点被删除的情况,没外键约束)。
2、要依赖高级程序来维护路径中的字符串,并且验证字符串的正确性的开销很大。
3、VARCHAR的长度很难确定。无论VARCHAR的长度设为多大,都存在不能够无限扩展的情况。
路径枚举的设计方式能够很方便地根据节点的层级排序,因为路径中分隔两边的节点间的距离永远是1,因此通过比较字符串长度就能知道层级的深浅。
嵌套集解决方案是存储子孙节点的信息,而不是节点的直接祖先。我们使用两个数字来编码每个节点,表示这个信息。可以将这两个数字称为nsleft和nsright。
nsright值的确定:nsright的值大于该节点所有后代的Id。
当然,以上两个数字和CommentId的值并没有任何关联,确定值的方式是对树进行一次深度优先遍历,在逐层入神的过程中依次递增地分配nsleft的值,并在返回时依次递增地分配nsright的值。
采用书中的图来说明一下情况:
一旦你为每个节点分配了这些数字,就可以使用它们来找到给定节点的祖先和后代。
嵌套集的优点:
我觉得是唯一的优点了,查询祖先树和子树方便。
SELECTc2.*FROMCommentsASc1JOINCommentsASc2ONcs.neleftBETWEENc1.nsleftANDc1.nsrightWHEREc1.CommentId=1;结果如下:
这种嵌套集的设计还有一个优点,就是当你想要删除一个非叶子节点时,它的后代会自动地代替被删除的节点,称为其直接祖先节点的直接后代。
嵌套集设计并不必须保存分层关系。因此当删除一个节点造成数值不连续时,并不会对树的结构产生任何影响。
嵌套集缺点:
1、查询直接父亲。
在嵌套集的设计中,这个需求的实现的思路是,给定节点c1的直接父亲是这个节点的一个祖先,且这两个节点之间不应该有任何其他的节点,因此,你可以用一个递归的外联结来查询一个节点,它就是c1的祖先,也同时是另一个节点Y的后代,随后我们使y=x就查询,直到查询返回空,即不存在这样的节点,此时y便是c1的直接父亲节点。
2、对树进行操作,比如插入和移动节点。
当插入一个节点时,你需要重新计算新插入节点的相邻兄弟节点、祖先节点和它祖先节点的兄弟,来确保它们的左右值都比这个新节点的左值大。同时,如果这个新节点是一个非叶子节点,你还要检查它的子孙节点。
够了,够了。就凭查直接父节点都困难,这个东西就很冷门了。我确定我不会使用这种设计了。
CREATETABLEComments(CommentIdintPK,ArticleIdint,CommentBodyint,FOREIGNKEY(ArticleId)REFERENCESArticles(Id))父子关系表:
Comment表:
TreePaths表:
优点:
1、查询所有后代节点(查子树):
SELECTc.*FROMCommentAScINNERJOINTreePathstonc.CommentId=t.descendantWHEREt.ancestor=4结果如下:
SELECTc.*FROMCommentAScINNERJOINTreePathstonc.CommentId=t.ancestorWHEREt.descendant=6显示结果如下:
3、插入新节点:
INSERTINTOTreePaths(ancestor,descendant)SELECTt.ancestor,8FROMTreePathsAStWHEREt.descendant=5UNIONALLSELECT8,8执行以后:
至于Comment表那就简单得不说了。
4、删除叶子节点:
比如删除叶子节点7,应删除所有TreePaths表中后代为7的行:
DELETEFROMTreePathsWHEREdescendant=75、删除子树:
DELETEFROMTreePathsWHEREdescendantIN(SELECTdescendantFROMTreePathsWHEREancestor=4)另外,移动节点,先断开与原祖先的关系,然后与新节点建立关系的SQL语句都不难写。
另外,闭包表还可以优化,如增加一个path_length字段,自我引用为0,直接子节点为1,再一下层为2,一次类推,查询直接自子节点就变得很简单。
其实,在以往的工作中,曾见过不同类型的设计,邻接表,路径枚举,邻接表路径枚举一起来的都见过。
每种设计都各有优劣,如果选择设计依赖于应用程序中哪种操作最需要性能上的优化。
下面给出一个表格,来展示各种设计的难易程度:
1、邻接表是最方便的设计,并且很多软件开发者都了解它。并且在递归查询的帮助下,使得邻接表的查询更加高效。
2、枚举路径能够很直观地展示出祖先到后代之间的路径,但由于不能确保引用完整性,使得这个设计比较脆弱。枚举路径也使得数据的存储变得冗余。
3、嵌套集是一个聪明的解决方案,但不能确保引用完整性,并且只能使用于查询性能要求较高,而其他要求一般的场合使用它。