如何在数据库中存储一棵树

树形结构的数据在项目开发中比较常见，比如比较典型的是论坛主题留言。每一个主题（节点）可以有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;