如何在数据库中存储一棵树
树形结构的数据在项目开发中比较常见,比如比较典型的是论坛主题留言。每一个主题(节点)可以有n个留言(子节点)。这些留言又可以有自己的留言。因此这种结构
树形结构的数据在项目开发中比较常见,比如比较典型的是论坛主题留言。
每一个主题(节点)可以有n个留言(子节点)。这些留言又可以有自己的留言。因此这种结构就是一颗树。本文讨论的是数据库中如何存储这种树形结构。
假设有如下一棵树:
存储的数据如下格式:
这种结构下,如果查询某一个节点的直接子节点,十分容易,比如要查询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表:
如例子中的树,插入的数据如下:
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;上一篇: Hive 常见问题与技巧
下一篇: Linode LNMP服务器环境配置笔记