SQL Story(十一)--树状表游戏

树状结构的存储与管理,是每一个在关系型数据库平台上工作的程序员早晚都要遇到的问题。说大不大,怎么都能解决,说小不小,处理不好,有的是麻烦等着你。仁者见仁,智者见智,公说公有理,婆说婆有理(谁用机箱砸我?机箱是个好东西,乱丢会摔坏硬盘的,你看我话没说完你又把显示器丢了……),咳咳,好吧,闲话少说,我们从最大路的处理风格谈一谈吧。这里面的大部分内容并非我的独创,从很久很久以前,数据库程序员们就这样做啦。

树状表的结构化表达

在一切开始前,我们先就树状表的表示方式达成一个共识。在关系型数据库中,我们当然没有办法这样直接表示一个树:

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 所长。这里面有着各种各样的麻烦。相信试过的朋友都有体会。现在我使用的架构问题是显然的,它需要明确知道到底从子树的顶点向下到底有多少层。所以,计算树的层数就首先被提了出来。

但是,但是,但是……(我简直没脸见人啦)我一直找不到一个简洁优雅的方法。一个多月的时间就这么过去了。我不得不一点点放弃我的原则(此乃人生堕落之始啊)。最后,我得承认,要想写出一个优雅的树状表选择来,对我还是比较困难的。所以,在这一篇文章里,我们先讨论到这里,树状表的选择――其实应该说树状视图构造,还是留到下次再讨论吧。

Published At
Categories with 数据库类
Tagged with
comments powered by Disqus