简单的树-阿里云开发者社区

开发者社区> eddie小英俊> 正文

简单的树

简介:
+关注继续查看

                                                       树还是树,你还须要考虑些什么呢?

                                                                            ——罗纳德·里根

引言

 今天我们来考虑这样一个问题,有关于树节点的操作。

问题一:一个公司里面有非常多的层级关系,那么怎样把公司的组织架构图的关系在数据库中保存呢?

问题二:我们知道我们寻常所写的博客有评论,评论这跟树类似有层叠关系,那么怎样在数据库中表示这样的关系呢?

 

邻接表

以下就是关于邻接表分层存储的结构关系

 

Comment_id

Parent_id

author

comment

1

Null

王三

你的博客写的不错

2

1

作者

谢谢夸奖

3

2

王四

不,我看过了,漏洞百出

4

1

李四

你什么眼神

5

4

作者

哎,不带这么骂人的

6

4

田七

请注意文明用语

 

 

 

 

非常多时候。我们都会採取这样的操作来设计我们的数据库,而这样的操作也会成为我们的默认方案,但我们会发现这里面存在一个问题,它无法满足树操作中最普通的一项:查询一个节点的全部后代,你能够使用一个关联查询来获取一条评论和它的直接后代

 获取后代

 

<span style="font-family:SimSun;font-size:18px;">select c1.*,c2.* from comments c1 left outer join comments c2
on c2.parent_id =c1.comment_id </span>


然而,这个查询仅仅能获取两层的数据,而我们就我们所了解的而言,树的特性是能够随意的扩展,因此你必须须要有方法来获取随意深度的数据。

比方,可能须要计算一个评论分支的数量等

当然在使用邻接表的时候,我们可以通过添加的连接的扩展来进行查询,例如以下的查询可以获得四层数据,不可以很多其它了:

四层查询

 

<span style="font-family:SimSun;font-size:18px;">select c1.*,c2.* from comments  c1   -- 1st level
left outer join comments  c2
on c2.parent_id=c1.comment_id        --2nd  level
left outer join comments c3
on c3.parent_id=c2.comment_id   --3rd  level
left outer join comments c4
on c4.parent_id=c3.comment_id   --4th</span>

我们看到这种查询非常笨拙,由于随着后代的逐渐添加,必须同等的添加连接的列。这使得运行一个聚合函数变得极其困难。

优点

1.添加一个叶子节点

<span style="font-family:SimSun;font-size:18px;">insert into comments(comment_id,parent_id,author,comment) values('8','6','王小','规范我们的用语')</span>

2.改动一个节点的位置或者一棵树的位置也是简单的

<span style="font-family:SimSun;font-size:18px;">update comments set parent_id='3' where comment_id=5</span>

3.假设从一棵树中删除一个节点会变得比較复杂。因此不得不运行多次的查询来找到全部的后代节点,然后逐个从最低级别開始删除这些节点以满足外键的完整性。

<span style="font-family:SimSun;font-size:18px;">select comment_id from comments where parent_id='4'  --返回5和6
  select comment_id from comments where parent_id='5'   --返回空值
  select comment_id from comments where parent_id='6'   --返回7
  select comment_id from comments where parent_id='7'   --返回 空值

  --进行删除操作
  delete from comments where comment_id in (4,5,6,7)</span>

 

4.假如要删除一个非叶子节点而且提升它的子节点,或者它的子节点移动到还有一个节点下,那么首先要改动子节点的Parent_id,然后才干删除这个节点。

 

<span style="font-family:SimSun;font-size:18px;"> select parent_id from comments where comment_id ='6'  --return 4
  update comments set parent_id=4 where parent_id=6   --变化其子节点的父节点位置
  delete from comments where comment_id='6'  --最后才干删除这个节点</span>

 

以上就是使用邻接表须要多步操作才干完毕的查询范例。你不得不写额外多的代码来维护。

 

合理使用邻接表

  不可否认。在某些情况下邻接表能够满足我们的需求。邻接表的优势在于能高速的获取一个给定节点的直接父子节点,它也非常easy插入新节点,假设这些是你的需求的话,刚好能够使用邻接表来满足需求。

 

 

路径枚举

路径枚举,顾名思义就是通过保存路径的方式来查询我们所须要的信息。路径枚举通过将全部祖先的信息联合成一个字符串,并保存为每一个节点的一个属性,非常巧妙的攻克了这个问题。

路径枚举引用的是一个完整路径。如/c/books/English的目录路径,当中cbook的父亲。这也就意味着booksenglish的父亲。

comments表中。我们使用path字段来存储从当前节点的最顶层祖先一直到它自己的路径。就像上面所提到的一样。

 

Comment_id

Path

author

comment

1

1/

王三

你的博客写的不错

2

1/2

作者

谢谢夸奖

3

1/2/3

王四

不。我看过了。漏洞百出

4

1/4

李四

你什么眼神

5

1/4/5

作者

哎,不带这么骂人的

6

1/4/6

田七

请注意文明用语

长处

通过这个表的设计,以后能够通过比較每一个节点的路径来查询一个节点的祖先。

查询1的全部后代

<span style="font-family:SimSun;font-size:18px;">select *
from comments as c
where c.path  like '1/' + '%'</span>

结果是查询的结果表中的所有path字段的值

 

通过上述可知,一旦你能够非常easy的获得一棵树或者从子孙节点到祖先节点的就能够实现很多其它的查询功能。

计算从评论#1扩展出来的全部评论中每一个用户的评论数量:

<span style="font-family:SimSun;font-size:18px;">select count(*) 
from comments as c
where c.path like '1/' + '%'
group by c.author </span>

插入一个节点

 

<span style="font-family:SimSun;font-size:18px;">insert into comments(comment_id,path,author,comment) values('9','1/6/9','王红','做得好')</span>

缺点

路径枚举也存在一个缺点,因为引用的是路径,所以我们无法确保路径中的节点确实存在,而且验证字符串的正确性开销非常大。

 

 

嵌套集

  嵌套集对此的解决方式是,为每个节点都匹配了对应的数字。能够将这两个数字称为nsleftnsright.

Nsleft:该数值小于该节点后全部后代的ID

Nsright:该数值大于该节点后全部后代的ID

注意:这些数值和comment_id没有不论什么关联。

 

例如以下图的分配方式

注意:编码的中的数字就是如图这样的方式所分配的

一旦为每一个节点分配了这些数字,就能够使用它们来找到给定节点的祖先和后代。

评论#4的全部后代。

<span style="font-family:SimSun;font-size:18px;">select c2.*
from comments c1
join comments c2
on c2.nsleft between c1.nsleft and c1.nsright 
where c1.comment_id='4'</span>

 

优势

当你想要删除一个非叶子节点时。它的后代会自己主动的取代被删除的节点。成为其直接祖先节点的直接后代。虽然每一个节点的左右两个值在演示样例图中是有序分配的,而每一个节点也总是和它相邻的父兄节点进行比較,但嵌套集设计并不必须保存分层关系。

因而当删除一个节点造成数值不连续时,并不会对树的结构产生不论什么影响。

 

比方:你能够计算给定节点的深度然后删除它的父亲节点。随后你再次计算这个深度时,它已经自己主动降低了一层。

<span style="font-family:SimSun;font-size:18px;">select c1.comment_id,count(c2.comment_id) as depth
from comments as c1
join comments as c2
on c1.nsleft between c2.nsleft and c2.nsright
where c1.comment_id =7
group by c1.comment_id 

--结果等于3

delete from comments where comment_id =6
select c1.comment_id,count(c2.comment_id) as depth
from comments as c1
join comments as c2
on c1.nsleft between c2.nsleft and c2.nsright
where c1.comment_id =7
group by c1.comment_id 
--结果等于2</span>

假设是简单高速地查询时整个程序中最重要的部分。嵌套集是最佳的选择,然而嵌套集的插入和移动节点时比較复杂的,应为须要又一次分配左右值,假设应用程序须要频繁的插入和删除节点。那么嵌套集并不合适。

 

 

哪种设计适合你

每种设计都有优劣。例如以下图

设计

查询子

查询树

插入

删除

引用完整性

邻接表

1

简单

困难

简单

简单

递归查询

1

简单

简单

简单

简单

枚举路径

1

简单

简单

简单

简单

嵌套集

1

困难

简单

困难

困难

 

小结

邻接表:最方便的设计,差点儿都会用到这样的方案。

递归查询:假设使用的数据库支持WITH递归查询。那么结合邻接表的话,查询会更高效

枚举路径:可以非常直观的展示出祖先到后代之间的路径。可是因为引用路径的问题,使得这个设计非常的脆弱。

嵌套集:不能确保引用完整性。最好在一个查询性能要求非常高而对其它需求要求一般的场合来使用它。

 

版权声明:本文博客原创文章,博客,未经同意,不得转载。






本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/4678696.html,如需转载请自行联系原作者


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
一文快速搞定Redis_数据类型及JavaApi操作
大家好,我是**ChinaManor**,直译过来就是中国码农的意思,我希望自己能成为国家复兴道路的铺路人,大数据领域的耕耘者,平凡但不甘于平庸的人。
7 0
计算机基础1 | 学习笔记
快速学习计算机基础1。
7 0
计算机基础2 | 学习笔记
快速学习计算机基础2。
10 0
Vue 仿钉钉流程图(流程节点绘制 vue+Ant【如果用其他UI库需要替换几个组件】 附 demo)
# [这里是git地址](https://gitee.com/xiaoyaoluntian/imitating-dingding-flow-chart/tree/comdemo/)
6 0
一文快速搞懂系列__一文快速搞懂SuperSet[实战案例]
大家好,我是**ChinaManor**,直译过来就是中国码农的意思,俺希望自己能成为国家复兴道路的铺路人,大数据领域的耕耘者,平凡但不甘于平庸的人。
8 0
数据类型-数值和字符串 | 学习笔记
快速学习数据类型-数值和字符串。
5 0
冬季实战营第一期学习报告
通过五天学习与实操,对ECS云服务器入门、快速搭建LAMP环境、部署MySQL数据库、回顾搭建Docker环境和Spring Boot以及使用PolarDB和ECS搭建门户网站操作,对本期学习与实操的认识。
7 0
Redis高可用架构演进
Redis是目前使用最广泛的缓存程序之一,也被应用于多种场景,例如数据缓存、分布式锁等,Redis官方提供了多种部署架构,以满足不同应用场景下对于高可用和扩展性的要求。
6 0
冬季实战营第一期:从零到一上手玩转云服务器实验报告
第一期主要进行了六次实验,分别是《动手实操ECS云服务器》、《动手实操快速搭建LAMP环境》、《使用ECS服务器部署MySQL数据库》、《通过workbench远程登录ECS,快速搭建Docker环境》、《从零搭建Spring Boot的Hello World》以及《使用PolarDB和ECS搭建门户网站》。首先远程登陆ECS实例,搭建LAMP环境,其中LAMP分别代表Linux、Apache、MySQL和PHP。然后配置及远程访问MySQL。冯晓帅老师在直播上带大家通过workbench登录ECS并快速搭建Docker环境,运行Spring Boot,最后安装WordPress并搭建博客。
8 0
MySQL高可用架构演进
MySQL是数据库领域当之无愧的霸主之一,其在各行各业被广泛应用,随着广泛使用,对于MySQL本身的高可用性的要求就是不可避免的话题,而MySQL的高可用方案也随着MySQL功能的完善经历了多次升级,本文将对MySQL的各种高可用架构进行分析,以此来了解架构的演进。
6 0
925
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载