使用数据库实现树结构

引言

树形结构在实现分层结构时非常有用，这有助于软件开发人员为客户开发更贴近实际、更具可操作性的应用程序。例如，在实现“部门结构”、“产品树”或“未知深度层级”的组织结构图时，在数据库中使用这些结构是不可避免的。

在本文中，我们将回顾在数据库中维护树形结构所需的存储过程和函数。在本例中，我们使用了 Microsoft SQL Server 2008 作为我们的 DBMS。我们将看到如何使用 SQL 来列出、添加、编辑、删除、移动和复制树中的节点，以及如何通过删除孤立节点来维护我们的树。这些过程将帮助程序员轻松维护 Windows 或 Web 应用程序中的树形结构。在拥有了这些工具之后，程序员就可以提供一个用户友好的界面来处理树形结构了。

背景

树形结构由多个节点组成，每个节点都有一个父节点，并且不存在节点关系中的环。我们至少需要为每个节点提供一个 Identification 字段和一个指向其父节点的指针。很明显，根节点没有父节点。我们可以根据我们正在处理的问题，在每个节点的 'data structure' 中添加额外的信息。

Using the Code

创建

首先，我们应该在数据库中创建一个名为 TreeNodes 的 Tree 表。我们有一个标识字段、一个标题和一个指向父级标识的指针。

CREATE TABLE [dbo].[TreeNodes](
	[TN_ID] [int] IDENTITY(1,1) NOT NULL,
	[TN_Title] [nvarchar](200) NOT NULL,
	[TN_ParentID] [int] NULL,
 CONSTRAINT [PK_TreeNodes] PRIMARY KEY CLUSTERED
(
	[TN_ID] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, _
IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

GO

ALTER TABLE [dbo].[TreeNodes]  WITH CHECK ADD  CONSTRAINT _
[FK_TreeNodes_TreeNodes] FOREIGN KEY([TN_ParentID])
REFERENCES [dbo].[TreeNodes] ([TN_ID])
GO

ALTER TABLE [dbo].[TreeNodes] CHECK CONSTRAINT [FK_TreeNodes_TreeNodes]
GO

插入

现在，我们应该实现我们的代码来轻松地添加、编辑、删除和移动树中的节点。

对于插入操作，我们只有两种情况：

1. 没有父节点的节点
2. 有父节点的节点

所以这是我们的插入存储过程：

CREATE PROCEDURE [dbo].[sp_insertTreeNode]
@parentid int,
@nt nvarchar(200),
@newid int output
AS
insert into TreeNodes (TN_Title, TN_ParentID)
   values(@nt, @parentid)
set @newid = SCOPE_IDENTITY()

我们返回 @newid，它被填充了新插入的标识值，供调用者进行进一步操作。

更新

之后，我们有 Update 过程来更新节点中的信息。

CREATE PROCEDURE [dbo].[sp_updateTreeNode]
@tn_id int,
@newTitle nvarchar(200)
AS
update TreeNodes set tn_title = @newTitle
where tn_id = @tn_id      

删除

然后，我们应该能够删除一个节点。我们应该首先处理删除其子节点，否则我们的数据库中就会出现孤立节点。我们将递归删除子节点。

在递归调用存储过程和用户定义函数时，可能会遇到两个障碍。首先，您可能会遇到最大嵌套调用错误；其次，如果您使用了全局游标名称，可能会遇到全局游标名称冲突错误。我未能找到克服 SQL Server 2008 中 32 级嵌套过程调用限制的解决方案，而要解决后者的问题，您可以考虑使用此配置命令：

alter database DBName set CURSOR_DEFAULT  LOCAL

所以这是我们的删除过程：

CREATE PROCEDURE [dbo].[sp_deleteTreeNode]
@tn_id int
AS
if (@@NESTLEVEL=1)
	alter database DBName set CURSOR_DEFAULT  LOCAL

declare @child_count int

select @child_count=  count(*) from treenodes where tn_parentid=@tn_id

if @child_count>0
begin
	--firstly delete child nodes recursively
	declare @child_id int
	DECLARE child_nodes  CURSOR FOR
		SELECT tn_id FROM treenodes
		WHERE tn_parentid = @tn_id

	OPEN child_nodes

	FETCH NEXT FROM child_nodes INTO @child_id

	WHILE @@FETCH_STATUS = 0
	BEGIN
	   exec sp_deleteTreeNode @child_id

	   FETCH NEXT FROM child_nodes INTO @child_id
	END

	CLOSE child_nodes
	DEALLOCATE child_nodes
end

--delete a node without any child
delete from treenodes where tn_id= @tn_id

它首先递归删除子节点，然后从树中删除请求的节点。

请注意，将 CURSOR_DEFAULT 设置为 LOCAL 可以防止在具有 static 游标名称的递归存储过程中出现错误。

如果您的 DBMS 支持级联删除，并且您也使用了删除触发器来删除子节点，那么您也可以考虑使用级联删除作为直接删除子节点的替代方法。

移动

移动节点：

CREATE PROCEDURE [dbo].[sp_moveTreeNode]
@tn_id int,
@newParent int
AS
update TreeNodes set TN_ParentID = @newParent
where tn_id = @tn_id

列表

要在应用程序中列出节点，我们应该列出一个节点的子节点，然后深入一级。递归检索节点并在每个深度构建树是一种非常清晰的实现方法。

CREATE PROCEDURE [dbo].[sp_listNodes]
@tn_id as int
AS
select * from TreeNodes
where TN_ParentID= @tn_id
order by TN_ParentID

要获取根节点列表，应该将 @tn_id 参数设置为 null 来调用它。

子树列表

有时，拥有节点所有子节点的列表会很有用。

CREATE FUNCTION [dbo].[fn_listSubTreeNodes]
(
@tn_id int
)
RETURNS
@res TABLE
(
	cn_id int
)
AS
BEGIN
	if @tn_id<1
		RETURN

	insert into @res values(@tn_id);

	declare @child_count int
	select @child_count=  count(*) from treenodes where tn_parentid=@tn_id
	if @child_count>0
	begin
		declare @child_id int
		DECLARE child_nodes  CURSOR FOR
			SELECT tn_id FROM treenodes
			WHERE tn_parentid = @tn_id

		OPEN child_nodes

		FETCH NEXT FROM child_nodes INTO @child_id

		WHILE @@FETCH_STATUS = 0
		BEGIN

			insert @res
			select * from DBName.dbo.fn_listSubTreeNodes(@child_id)

		   FETCH NEXT FROM child_nodes INTO @child_id
		END

		CLOSE child_nodes
		DEALLOCATE child_nodes
	end

	RETURN
END

在这种情况下，我们使用了表值函数以递归方式累积结果。请注意，观察节点包含在结果中。您可以使用 @@NESTLEVEL 变量来避免将根节点添加到结果集中（当它为 1 时）。

感谢 Mika Wendelius 指出使用通用表表达式（CTE），这里是列出子树节点的另一种实现方法：

CREATE PROCEDURE [dbo].[sp_listSubTreeNodes]
@tn_id as int
AS
BEGIN
with subtree(tn_id , tn_title , tn_parentid)
as
(
select * from TreeNodes where TN_ID = @tn_id
union all
select e.TN_ID, e.TN_Title ,e.TN_ParentID from TreeNodes _
as e inner join subtree on subtree.TN_ID=e.TN_ParentID
)
select * from subtree
END

复制

一些用户可能希望将我们的树的某些部分复制到它的另一部分，因此我们应该有一个 copyTree 过程。

CREATE PROCEDURE [dbo].[sp_copyTree]
@src_tn_id as int,
@tgt_tn_id as int
AS
declare @newTarget as int

if (@@NESTLEVEL=1)
	alter database DBName set CURSOR_DEFAULT  LOCAL

insert into TreeNodes(TN_ParentID, TN_Title) values _
(@tgt_tn_id, (select tn_title from TreeNodes where TN_ID=@src_tn_id))
set @newTarget = SCOPE_IDENTITY()

declare @child_count int
select @child_count=count(*) from treenodes where tn_parentid=@src_tn_id

if @child_count>0
begin
	declare @child_id int
	DECLARE child_nodes  CURSOR FOR
		SELECT tn_id FROM treenodes
		WHERE tn_parentid = @src_tn_id

	OPEN child_nodes

	FETCH NEXT FROM child_nodes INTO @child_id

	WHILE @@FETCH_STATUS = 0
	BEGIN
	   exec sp_copyTree @child_id , @newTarget
	   FETCH NEXT FROM child_nodes INTO @child_id
	END

	CLOSE child_nodes
	DEALLOCATE child_nodes
end

它从源节点开始，将其所有子节点复制到它们相应的父节点。

孤儿！

父节点不在数据库中的节点是孤立节点。通过在数据库中使用约束，您可能不会有孤立节点，但如果某些情况下您认为由于应用程序故障或缺乏约束而可能存在孤立节点，那么您应该决定是残酷地删除孤立节点，还是让它们被新父节点收养！如果您是那个残酷的人，这里是解决方案：

CREATE PROCEDURE [dbo].[sp_removeOrphans]
AS
declare @orphanCount int

select @orphanCount = COUNT(*) from TreeNodes where _
(TN_ParentID not in (select TN_ID from TreeNodes))  and  (TN_ParentID is not null)
while (@orphanCount >0)
begin
	delete TreeNodes where (TN_ParentID not in _
	(select TN_ID from TreeNodes))  and  (TN_ParentID is not null)
	select @orphanCount = COUNT(*) from TreeNodes where _
	(TN_ParentID not in (select TN_ID from TreeNodes))  _
	and  (TN_ParentID is not null)
end

它只会删除它找到的尽可能多的孤立节点！
但是，如果有一天您想恢复它们，只需将它们的根节点父节点设置为 null 或新的现有节点即可。

最后

它需要一个用户友好的界面来在数据库树中列出、添加、删除、编辑、移动或复制节点。

记住，此树的约束是嵌套过程调用的级别，对于 SQL Server 2008，默认级别为 32，以及全局游标名称，这已通过此命令解决：

alter database DBName set CURSOR_DEFAULT  LOCAL

请注意，此模型不是树形结构的最优设计模型，但它可以启发一些人在数据库中使用它们。
有关实现树的其他方法，请参阅此页面底部的 Member 3377871 的评论。

非常感谢。

关注点

当我执行递归过程时，SQL Server 出现了一些错误，让我陷入了麻烦，但我设法在 Google 上搜索问题，并最终找到了解决全局游标名称冲突的方案。

此外，SQL Server 2008 中嵌套过程调用的限制为 32，这使得每个程序员都犹豫不决，并因此限制了我们的树深度为 32 层。

历史

• 2011 年 2 月 25 日：首次发布