逻辑数据库设计单纯的树(邻接表路径枚举嵌套集闭包表)(引)海贼王&汉库克

这个需求并不简单,相互回复会导致无限多的分支,无限多的祖先-后代关系。这是一种典型的递归关系数据。

对于这个问题,以下给出几个解决方案,各位客观可斟酌后选择。

邻接表的方案如下(仅仅说明问题):

这种设计方式就叫做邻接表。这可能是存储分层结构数据中最普通的方案了。

图片说明存储结构:

邻接表的优缺分析

对于以上邻接表,很多程序员已经将其当成默认的解决方案了,但即便是这样,但它在从前还是有存在的问题的。

分析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、嵌套集是一个聪明的解决方案,但不能确保引用完整性,并且只能使用于查询性能要求较高,而其他要求一般的场合使用它。

THE END
1.8个数据库设计典型实例PowerBuilder进行信息系统开发的基本知识。下面将通过一个个实例来说明如何利用 PowerBuilder作为数据库前端开发工具,开发出具有使用价值的管理信息系统。 人事管理系统实例是本书的第一个例子。因此对于实例开发过程中所涉及到的一些知 识会有重点讲述。 随着计算机技术的飞速发展,计算机在企业管理中应用的普及,利用计算机...http://www.360doc.com/document/14/0214/20/15804455_352536542.shtml
1.一个简单数据库设计例子一个简单数据库设计例子 一个曾经做过的简单的管理系统中数据库设计的例子,包括设计表、ER图、建模、脚本. +++++++++++++++++++++++++++++++++++++++++++++++ 项目信息 Project Name:Book Manager System DB:MySQL5.5 DB Name:db_library Tables...https://blog.csdn.net/Jerry_1126/article/details/44337973
2.sqlserver架构设计mob649e8162842c的技术博客在开始设计之前,了解一些基本要素是非常重要的。这些要素包括: 表:数据存储的基本单元。 字段:表中的列,每个字段都有数据类型。 索引:用于提高查询性能。 关系:表与表之间的联系。 约束:用于限制数据的输入(如主键、外键、唯一约束等)。 三、设计一个简单的数据库 ...https://blog.51cto.com/u_16175492/12561233
3.AlphaFold3来了!全面预测蛋白质与所有生命分子相互作用及结构...(d) VMD:一个分子可视化程序,用于使用 3D 图形和内置脚本显示、动 态化和分析大型生物分子系统。 1.4 蛋白质设计的常用评估指标:NSR、RMSD、GDT、能量评分函数、可 溶性、与靶标之间的结合强度和特异性 3. 蛋白质数据库介绍 1.1 一级蛋白质序列数据库:UniProtKB ...https://cloud.tencent.com/developer/article/2437597
4.MySQL数据库实验实现简单数据库应用系统设计Mysql这篇文章主要介绍了MySQL数据库实验实现简单数据库应用系统设计,文章通过理解并能运用数据库设计的常见步骤来设计满足给定需求的概念模和关系数据模型展开详情,需要的朋友可以参考一下+ 目录 GPT4.0+Midjourney绘画+国内大模型 会员永久免费使用!【 如果你想靠AI翻身,你先需要一个靠谱的工具!】 观前提示:本篇内容为...https://www.jb51.net/article/252268.htm
5.蓝蓝高频面试之数据库系列第一期数据库基础20题前言[toc] 大家好,我是蓝蓝。数据库在国企,银行,研究所的面试过程中,是占比非常大的,也是及其可能被问的知识点,我将其分为四个部分,分为基础理论篇,事务篇,优化篇,大概一共100个题目,最后一部分是最高频的题目,大家加油哈,星球打卡时间为15天,完成打卡一定有https://m.nowcoder.com/discuss/353158849412669440
6.全国计算机二级考试哪个最简单全国计算机二级考试是全国计算机等级考试简称NCRE,是四个等级中的一个等级。包含语言程序设计,包括C、C++、Java、Visual Basic、WEB程序设计;数据库程序设计(包括VisualFoxPro、Access、MySql);MS office高级应用包括Word、EXCEL、PPT办公软件高级应用。计算机二级考试哪个最简单?下面百分网小编带大家一起来看看详细内容,希望...https://www.oh100.com/kaoshi/ncre2/tiku/482381.html
7.软件工程导论作业控制类:是用于对特定于一个或一些用例的控制行为建模的类。 实体类:是用来对必须存储的信息及关联行为建模的类。 5.6 按照设计模型的不同层次和功能,设计元素可以分哪些方面? 答:(1)体系结构元素;(2)构件级元素;(3)接口/界面元素:用户界面、构件接口、系统接口;(4)数据元素:数据库设计、数据结构设计;(5)部署...https://www.unjs.com/zuixinxiaoxi/ziliao/20170805000008_1416273.html
8.java毕业实习报告(精选11篇)在三个月里,所学知识的确有很多,java基础,数据库操作(oracle,mysql),SSH框架(hibernate,struts,spring),网页设计jsp技术等,总之学到了很多曾经陌生的技术。受益匪浅。 一、实习计划 7月10日:简单地了解公司的基本情况,进一步学习了java的基本知识。7月11日—7月13日:学习java相关的编程环境和运行环境的材料,准备...https://www.fwsir.com/Article/html/Article_20141119170516_283897.html
9.软件工程—精选习题集(含参考答案)总复习60道简答题因此,工程网络图是系统分析和系统设计的强有力的工具。19、动态联编答:动态联编指应用系统在运行过程中,当需要执行一个特定服务的时候,选择(或联编)实现该服务的适当算法的能力。20、系统流程图答:一个概括地描绘物理系统的传统工具,表达了数据在系统各部件之间流动的情况。https://www.jianshu.com/p/6875e17271d0
10.案例数据库设计9篇(全文)校企合作的此类实训项目中,进行数据库设计与实现所用知识、技术,基础来自于校内所学,但又远高于校内简单的数据库理论知识,是学生按软件工程流程做项目开发最重要的一个环节,数据库设计的好坏,直接影响后期软件开发和维护。 摘要:该文介绍了如何使用UML进行数据库设计。首先建立静态模型,然后根据映射策略将模型映射为数据...https://www.99xueshu.com/w/ikey3pf3ms57.html
11.什么是BI?企业数字化的规划和落地第三层,数据源层- 即BI的数据层,各个业务系统底层数据库的数据通过 ETL 的方式抽取到BI的数据仓库中完成 ETL 过程,建模分析等等,最终支撑到前端的可视化分析展现。 02、BI在企业IT信息化中的位置 这一点是所有企业如果规划要上BI项目的时候必须弄明白的:BI在IT信息化中到底处于一个什么样的位置?弄清楚定位是信息...https://maimai.cn/article/detail?fid=1778763808&efid=IIU4kC9omHSMNDd9brumRg
12.ASP.NETCore适用于.NET的开源Web框架.NET 是一个开发人员平台,由工具、编程语言、库组成,用于构建许多不同类型的应用程序。 ASP.NET Core 通过专门用于生成 web 应用的工具和库扩展了.NET 开发人员平台。 更深入发掘: 什么是 ASP.NET Core? 了解ASP.NET Core 通过我们的教程、视频课程和文档,了解 ASP.NET Core 提供的所有功能。 https://asp.net/
13.豆瓣967450 个成员 你来替我吃/用 27984 个成员 下班新生活计划 109315 个成员 再见爱人讨论组 2557 个成员 博士互助组---今天你毕业了吗 96234 个成员 法盲互助协会 149802 个成员 我又买鲜花啦 126005 个成员 人间情侣观察 203772 个成员 电影票房·资料库 49664...https://www.douban.com/
14.保障性理论基础在实施保障性分析的过程中,将收集的大量有关保障的数据与保障性分析记录(logistics support analysis record,LSAR),以一定的格式储存到电子计算机内,建立一个包括可靠性、维修性、测试性及各综合技术保障要素等信息在内的独立的保障性分析记录数据库,并在分析过程中不断地更新数据。该数据库用于装备综合技术保障和保障...https://mp.ofweek.com/im/a645693221836
15.积分商城数据库设计:构建一个完美的线上积分兑换平台(积分商城...随着互联网的发展,越来越多的企业开始在线上销售产品和服务。与此同时,也出现了越来越多的积分兑换平台,为消费者提供了更加便捷的积分兑换服务。然而,在构建一个完美的线上积分兑换平台的过程中,数据库设计是非常关键的。 本文将从以下三个方面来介绍积分商城数据库的设计: ...https://www.idc.net/help/150689/