树状结构的存储与管理，是每一个在关系型数据库平台上工作的程序员早晚都要遇到的问题。说大不大，怎么都能解决，说小不小，处理不好，有的是麻烦等着你。仁者见仁，智者见智，公说公有理，婆说婆有理（谁用机箱砸我？机箱是个好东西，乱丢会摔坏硬盘的，你看我话没说完你又把显示器丢了……），咳咳，好吧，闲话少说，我们从最大路的处理风格谈一谈吧。这里面的大部分内容并非我的独创，从很久很久以前，数据库程序员们就这样做啦。
树状表的结构化表达
在一切开始前，我们先就树状表的表示方式达成一个共识。在关系型数据库中，我们当然没有办法这样直接表示一个树：
a
b c
d e f g
相应的，我们会把它变形为平面表，这种变形让我想起拓扑几何：
r n1 n2
a b d
a b e
a c f
a c g
存储结构
稍有经验的朋友，大概都不会试着把树状结构一层一列的存进去了吧。这样做的问题是显而易见的：与表中存储的信息结构不同，表的结构应该是相对固定的，不能随便改动。而对于层数不能固定的普通树状结构，这是不可思议的。没有必要讨论过多的错误，我们选择一个相对正确的方式――把树状结构抽象成适合关系数据库的形式。
只考虑某一个节点的话，和这个节点相关的信息是：它的唯一标识、父节点、子节点、数据信息。这其中只有子节点的数目不定。不过如果每一个节点都确定了自己的父节点，显然可以省略子节点。这样一来，一个节点需要存储三部分信息――它的唯一标识、父节点、数据信息。一个理想的TreeView表只需要三个节点就可以了，用SQL语句来表达就是
CREATE TABLE [dbo].[TreeView] (
[ID] [char] (10) PRIMARY KEY,
[PID] [char] (10) FOREIGN KEY REFERENCES [dbo].[TreeView],
[DATA] [char] (10)
)
ID是当前节点的唯一标识号，显然它应当是主键；我们建立的是一个自闭的存储结构，每一个节点的父节点也应当出自表中存储的节点，所以PID列引用ID作为外键；至于DATA，它是节点中的信息，通常和树的结构没有绝对关系。我把这三列全设成Char(10)，是为了后面做演示更方便，当然也有人喜欢用自动标识列来做主键，在这种场合，也自有其优点。为了维护数据的完整性或存储、检索等方面的考虑，实用中我们可能会采用更复杂的结构，不过骨干就这样子了。这个结构从数学上讲很简洁，而且是自洽的。如果一个节点没有父节点，那么它的PID就等于它自己的ID。这并不违反我们关于主外键的定义。
信息的管理与使用
树表的结构确定后，问题就集中在如何读写其中的数据。
增加节点：增加一个叶节点很简单，只要指定这个节点的父节点，把它“挂接”到TreeView中。从递归的角度来看，我们可以重复这一步骤，真到插入一个完整的子树。相对而言，比较麻烦的是，如何把一个子节点插入到现有的树中间，而不是最末端。比如存在一个节点N，它的根为R，现在要在R和N之间插入一个新节点N’，我们可以这样做：把N’挂在R下面，作为它的子节点，然后把N的父节点指定为N’即可。
修改节点：这里指修改树结构，改变某一节点的父节点，在这种结构中，修改是很方便的，只要调用标准的update就可以。
删除节点：删除节点时要注意这个节点下面还有没有子节点，如果有，我们通常以两种方式处理，一是把相关子节点全删掉，如果是MS SQL Server 2000这样的系统，你可以很简单的在建表时将外键约束指定为支持级联删除，自己写一个级联删除比较麻烦，不过也不是不可能，重点在于，为这个过程建立递归。简要示例如下：
--定义存储过程
CREATE PROCEDURE DeleteNode
@NodeID Char(10)
AS
BEGIN
--以当前节点的子节点作为记录集建立游标
DECLARE ChildNodes CURSOR
READ_ONLY
FOR SELECT ID FROM TreeView WHERE PID = @NodeID
DECLARE @ChildNode VARCHAR(40)
OPEN ChildNodes
FETCH NEXT FROM ChildNodes INTO @ChildNode
WHILE (@@fetch_status <> -1)--判断记录集是否成功打开
BEGIN
IF (@@fetch_status <> -2)
BEGIN
--递归调用
EXEC DeleteNode @ChildNode
END
FETCH NEXT FROM ChildNodes INTO @ChildNode
END
CLOSE ChildNodes
DEALLOCATE ChildNodes
--代码执行到这里，可以确定@NodeID不再有子节点，现在，我们删除它
DELETE FROM TreeView WHERE ID = @NodeID
END;
当然，这是一种比较低效的设计，每一个将要删除的节点都要执行一次Delete，比较有效率的方法是多深入一层，操作当前节点的子节点。有兴趣的读者可以一试。
查询：树状表的查询是最有趣的内容之一。当然仅仅查出某一个节点的信息没有太大的意思，我们希望的是得到从当前节点一直向下（通常是到最底层）的完整子树。这同样需要一个递归。让我们从一个归纳法游戏开始，事先，我们先在TreeView中插入以下数据：
|
ID |
PID |
DATA |
|
---------- |
---------- |
---------- |
|
ROOT |
ROOT |
ROOT |
|
N11 |
ROOT |
Node1-1 |
|
N12 |
ROOT |
Node1-2 |
|
N13 |
ROOT |
Node1-3 |
|
N21 |
N11 |
Node2-1 |
|
N22 |
N11 |
Node2-2 |
|
N23 |
N12 |
Node2-3 |
|
N24 |
N13 |
Node2-4 |
|
N31 |
N21 |
Node3-1 |
|
N32 |
N21 |
Node3-2 |
|
N33 |
N21 |
Node3-3 |
|
N34 |
N22 |
Node3-4 |
归纳法第一步，当然是构造初值，查询子树的根节点就是标准的SQL，SELECT ID, DATA FORM TreeView WHERE ID = …，在这里有一个细节，查找表中所有的根节点（细心的读者可能早就发现，我们设计的这个TreeView可以存储任意多个树）可以通过SELECT R.ID, R.DATA FORM TreeView R WHERE R.ID = R.PID来实现。简单起见，我们就从这里起步吧。
第二步，选择出前两层也不难，
SELECT R.ID, N1.ID, N1.DATA
FROM TreeView R
LEFT JOIN TreeView N1
ON R.ID = N1.PID
AND R.ID <> N1.ID
WHERE R.ID = R.PID
我们要注意的是加蓝的部分，这是增加一层后做改动的部分。
很容易，我们得到前三层，
SELECT R.ID, N1.ID, N2.ID, N2.DATA
FROM TreeView R
LEFT JOIN TreeView N1
ON R.ID = N1.PID
AND R.ID <> N1.ID
LEFT JOIN TreeView N2
ON N1.ID = N2.PID
AND N1.ID <> N2.ID
WHERE R.ID = R.PID
同样的，我们重点观察加蓝的部分。相信经过这两步，大家会发现其中的规律。现在我们可以把这个过程自动化了……
……
不知道大家是否还记得前几集里那个关于四色问题的笑话，我又一次犯了这样的错误。一个多月以来，我就陷在这里不能自拔。显然，我低估了问题的难度。这个问题似乎不能转化为一个简单表达式，只能通过一个递归的流程来实现。而流程化的程序又非SQL所长。这里面有着各种各样的麻烦。相信试过的朋友都有体会。现在我使用的架构问题是显然的，它需要明确知道到底从子树的顶点向下到底有多少层。所以，计算树的层数就首先被提了出来。
但是，但是，但是……（我简直没脸见人啦）我一直找不到一个简洁优雅的方法。一个多月的时间就这么过去了。我不得不一点点放弃我的原则（此乃人生堕落之始啊）。最后，我得承认，要想写出一个优雅的树状表选择来，对我还是比较困难的。所以，在这一篇文章里，我们先讨论到这里，树状表的选择――其实应该说树状视图构造，还是留到下次再讨论吧。 
|
本类阅读TOP10