|
|
Posted on 2006-10-15 03:16 大大毛 阅读(874) 评论(0) 编辑 收藏 所属分类: SQL
树型结构在应用中被广泛的运用，在数据操作上需要一定的技巧来进行处理：
在表结构的定义上，有多种方式可以采用。
.数据表：
a.单向链表式的结构 ( 这是藕给它起的名称，因为它与链表的结构相似，除了必要的自身描述外，就只包含父节点的位置)
DDL示例：
--相当于单向链表
create table linkTree (
id varchar(10) primary key, --节点自身ID
nodeContent varchar(50), --节点内容
parentId varchar(10) default '' --父节点ID
)
优点：
.列宽固定，表结构易维护；
.查找指定节点的上/下游节点效率高；
.维护树型结构方便(增/删层)；
缺点，如在下列情况中，都需要多次Select完成：
.从指定节点开始列出全部子树 ( 除 Oracle 提供支持外 )；
.返回从指定节点A到其子节点B的路径 ( B 与 A 的层数相差会大于 1 )；
DML示例：
向下查找及统计子节点(仅一层)
(1)通过父节点的ID
  通过父节点的ID
--查找子节点
select
*
from
linkTree
where
parentId = '01'
--统计子节点数量
select
parentId,
count(*) 'count'
from
linkTree
where
parentId = '01'
group by
parentId
(2)通过父节点的内容
条件列nodeContent上存在唯一性约束
--查找子节点
select
*
from
linkTree
where
parentId = (select id from linkTree where nodeContent = 'Root')
--统计子节点数量
select
parentId,
count(*) 'count'
from
linkTree
where
parentId = (select id from linkTree where nodeContent = 'Root')
group by
parentId
由于条件列无唯一性约束，所以在查找时有可能会返回一个记录集，需要做一些处理：
条件列nodeContent上无唯一性约束
--查找子节点,此处仅返回具有子节点的父节点行,如果需要返回全部则用right join
select
sub.id parentId,
main.id,
main.nodeContent
from
linkTree main
join (select id from linkTree where nodeContent = 'depart1') sub on main.parentId = sub.id
order by
parentId
--统计子节点数量,使用right join返回全部统计数
select
parentId,
count(id) 'count'
from (
select
sub.id parentId,
main.id
from
linkTree main
right join (select id from linkTree where nodeContent = 'depart1') sub on main.parentId = sub.id
) tree
group by
parentId
(3)查找兄弟节点
查找兄弟节点
--使用唯一列
select
parentId,
id brotherId,
nodeContent
from
linkTree
where
parentId = (select parentId from linkTree where id='01')
--使用非唯一列,由于一父多子的对应关系,因此需要注意使用distinct关键字
select
sub.parentId,
main.id brotherId,
main.nodeContent
from
linkTree main
join (select distinct parentId from linkTree where nodeContent = 'depart1') sub on main.parentId = sub.parentId
order by
parentId
(4)遍历树
由于链表式表结构的特点，决定了无法用通用的单次 Select 完成操作，对于不同的 DBMS 可以采取不同的策略：
如Oracle
select * from linkTree start with id='00' connect by PRIOR id = parentId;
如Ms-SQL2000
表的结构决定了数据只能逐层查找，网上常见的有使用存储过程进行递归返回表变量来实现。
这里我用循环的方式来实现，效率比递归+表变量要高。
Ms-SQL2000遍历树
 --这里定义的两个参数
declare
@level int, --查找层次
@start varchar(2); --开始节点ID
select @level = 3,@start = '00'; --示例赋参
--临时变量
declare @flag int; --当前处理节点的层次
declare
@t table (
id varchar(2),
nodeContent varchar(20),
parentId varchar(2),
site varchar(200),
flag int
);
--初始化
set @flag = 1;
insert into @t
select
linkTree.*,
linkTree.id,
@flag
from
linkTree
where
id = @start
--循环查找,结束条件(1.达到指定查找层次;2.没有任何匹配记录;)
while @@rowcount > 0 and @flag < @level
begin
set @flag = @flag + 1; --查找层次递增
--向下查找匹配子节点
insert into @t
select
linkTree.id,
linkTree.nodeContent,
linkTree.parentId,
t.site + linkTree.id,
@flag
from
@t t join linkTree on linkTree.parentId = t.id
where
t.flag = @flag - 1
end
--结果输出
select * from @t order by site 注：这里引入一个site列，是为了能够在输出时更加好的进行排序，因为在最终输出至网页时很有可能是顺序向下输出的，这里正好体现出这种结构。
b.位置描述式的结构 ( 这是藕给它起的名称，它有一个列，该列描述了当前节点在树中的位置)
DDL示例：
create table siteTree (
id varchar(2) primary key,
nodeContent varchar(20),
site varchar(200)
)
例子：
01 Root 01
02 dep1 0102
03 dep2 0103
04 dep11 010201
优点：
由于该表结构中带一个位置描述列site，因此对于关于树的遍历等问题的解决将变得异常的轻松。位置列按从根结点到当前结点的ID连接而成。
缺点：
有利即有弊，位置描述列也同时突出该种结构的缺点，它最大的缺点就是树的层次不可能是无穷的，由于它由整个路径的ID连接而已，因此该列的宽度并不是固定的，如根节点的长度将是ID列的宽度，而当前节点位置列所需要空间 = 当前节点层次 * ID列宽度。
针对链表式结构的优点，这里就成了缺点，层次间的增删将变得较为困难。
遍历树：
--输出指定节点的全部子节点
select * from siteTree where CHARINDEX('00',site)=1 order by site
|