怎么在数据库中存储一棵树51CTO博客 - 凯发娱乐

怎么在数据库中存储一棵树51CTO博客

2019-03-06 10:21:56 | 作者: 涵亮 | 标签: 节点,存储,数据库 | 浏览: 2080

树形结构的数据在项目开发中比较常见,比方比较典型的是论坛主题留言。

每一个主题(节点)能够有n个留言(子节点)。这些留言又能够有自己的留言。因而这种结构就是一颗树。本文评论的是数据库中怎么存储这种树形结构。

假设有如下一棵树:

办法一

留意:本例中的数据库是SQLite,因而SQL句子只对SQLite有用,其他数据库能够参阅该写法。

要存储于数据库中,最简略直接的办法,就是存储每个元素的父节点ID。

暂时把这种办法命名依靠父节点法,因而表结构规划如下:

存储的数据如下格局:

这种结构下,假如查询某一个节点的直接子节点,十分简单,比方要查询D节点的子节点。

select * from tree1 where parentid=4

假如要刺进某个节点,比方在D节点下,再次刺进一个M节点。

只需求如下SQL:

INSERT INTO tree1 (value,parentid) VALUES(M,4);

这种结构在查找某个节点的一切子节点,就稍显杂乱,无论是SELECT仍是DELETE都或许涉及到获取一切子节点的问题。比方要删去一个节点而且该节点的子节点也要悉数删去,那么首要要取得一切子节点的ID,由于子节点并不仅仅直接子节点,还或许包括子节点的子节点。比方删去D节点及其子节点,必须先查出D节点下的一切子节点,然后再做删去,SQL如下:

select nodeid from tree1 where parentid=4 --回来8,9
select nodeid from tree1 where parentid in (8,9) --回来10,11,12
select nodeid from tree1 where parentid in (10,11,12) --回来空
delete from tree1 where nodeid in (4,8,9,10,11,12)

假如是只删去D节点,关于其它节点不做删去而是做提高,那么必须先修正子节点的parentid,然后才干删去D节点。

正如上面演示的,关于这种依靠父节点法,最大的缺陷就是无法直接取得某个节点的一切子节点。因而假如要select一切的子节点,需求繁琐的过程,这不利于做聚合操作。

关于某些数据库产品,支撑递归查询句子的,比方微软的SQL Server,能够运用CTE技能完成递归查询。比方,要查询D节点的一切子节点。只需求如下句子:

WITH tmp AS(
SELECT * FROM Tree1 WHERE nodeid = 4
UNION ALL
SELECT a.* FROM Tree1 AS a,tmp AS b WHERE a.parentid = b. nodeid
)
SELECT * FROM tmp

可是关于那些不支撑递归查询的数据库来说,完成起来就比较杂乱了。


办法二

还有一种比较土的办法,就是存储途径。暂时命名为途径枚举法。

这种办法,将存储根结点到每个节点的途径。

这种数据结构,能够一眼就看出子节点的深度。

假如要查询某个节点下的子节点,只需求依据path的途径去匹配,比方要查询D节点下的一切子节点。

select * from tree2 where path like %/4/%

或许出于功率考虑,直接写成

select * from tree2 where path like 1/4/%

假如要做聚合操作,也很简单,比方查询D节点下一共有多少个节点。

select count(*) from tree2 where path like '1/4/%';

要刺进一个节点,则略微费事点。要刺进自己,然后查出父节点的Path,而且把自己生成的ID更新到path中去。比方,要在L节点后边刺进M节点。

首要刺进自己M,然后得到一个nodeid比方nodeid=13,然后M要刺进到L后边,因而,查出L的path为1/4/8/12/,因而update M的path为1/4/8/12/13

update tree2 set
path=(select path from tree2 where nodeid=12) --此处开端拼接
||last_insert_rowid()||/
where
nodeid= last_insert_rowid();

这种办法有一个显着的缺陷就是path字段的长度是有限的,这意味着,不能无约束的增加节点深度。因而这种办法适用于存储小型的树结构。

办法三

下面介绍一种办法,称之为闭包表。

该办法记录了树中一切节点的联系,不仅仅仅仅直接父子联系,它需求运用2张表,除了节点表本身之外,还需求运用1张表来存储节先人点和子孙节点之间的联系(一起增加一行节点指向本身),而且依据需求,能够增加一个字段,表明深度。因而这种办法数据量许多。规划的表结构如下:

Tree3表:

NodeRelation表:

如比方中的树,刺进的数据如下:

Tree3表的数据

NodeRelation表的数据

能够看到,NodeRelation表的数据量许多。可是查询十分便利。比方,要查询D节点的子元素

只需求

select * from NodeRelation where ancestor=4;

要查询节点D的直接子节点,则加上depth=1

select * from NodeRelation where ancestor=4 and depth=1;

要查询节点J的一切父节点,SQL:

select * from NodeRelation where descendant=10;

假如是刺进一个新的节点,比方在L节点后增加子节点M,则刺进的节点除了M本身外,还有对应的节点联系。即还有哪些节点和新刺进的M节点有子孙联系。这个其实很简略,只要和L节点有子孙联系的,和M节点必定会有子孙联系,而且和L节点深度为X的和M节点的深度必定为X+1。因而,在刺进M节点后,找出L节点为子孙的那些节点作为和M节点之间有子孙联系,刺进到数据表。

INSERT INTO tree3 (value) VALUES(M);--刺进节点
INSERT INTO  NodeRelation(ancestor,descendant,depth)
select n.ancestor,last_insert_rowid(),n.depth+1--此处深度+1作为和M节点的深度
from NodeRelation n
where n.descendant=12
Union ALL
select  last_insert_rowid() ,last_insert_rowid(),0 --加上本身

在某些并不需求运用深度的情况下,乃至能够不需求depth字段。

假如要删去某个节点也很简单,比方,要删去节点D,这种情况下,除了删去tree3表中的D节点外,还需求删去NodeRelation表中的联系。

首要以D节点为子孙的联系要删去,一起以D节点的子孙为子孙的这些联系也要删去:

delete from NodeRelation where descendant in 
(select descendant from NodeRelation where ancestor=4 );--查询以D节点为先人的那些节点,即D节点的子孙。

这种删去办法,尽管完全,可是它也删去了D节点和它本来的子节点的联系。

假如仅仅想分裂D节点和A节点的联系,而关于它原有的子节点的联系予以保存,则需求参加约束条件。

约束要删去的联系的先人不以D为先人,即假如这个联系以D为先人的,则不必删去。因而把上面的SQL加上条件。

delete from NodeRelation where descendant in 
(select descendant from NodeRelation where ancestor=4 );--查询以D节点为先人的那些节点,即D节点的子孙。
and ancestor not in (select descendant from NodeRelation  where ancestor =4 )

上面的SQL用文字描述就是,查询出D节点的子孙,假如一个联系的先人不归于D节点的子孙,而且这个联系的子孙归于D节点的子孙,就删去它。

这样的删去,保存了D节点本身子节点的联系,如上面的比方,实际上删去的节点联系为:

假如要删去节点H,则为

总结:

上面首要讲了3种方法,各有长处缺陷。能够依据实际需求,挑选适宜的数据模型。


---------------------------------

参阅资料 《SQL Antipatterns》


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

猜您喜欢的文章