SQL Story（十一）－－樹(shù)狀表游戲
2024-07-21 02:08:55
供稿：網(wǎng)友
國(guó)內(nèi)最大的酷站演示中心!
樹(shù)狀結(jié)構(gòu)的存儲(chǔ)與管理，是每一個(gè)在關(guān)系型數(shù)據(jù)庫(kù)平臺(tái)上工作的程序員早晚都要遇到的問(wèn)題。說(shuō)大不大，怎么都能解決，說(shuō)小不小，處理不好，有的是麻煩等著你。仁者見(jiàn)仁，智者見(jiàn)智，公說(shuō)公有理，婆說(shuō)婆有理（誰(shuí)用機(jī)箱砸我？機(jī)箱是個(gè)好東西，亂丟會(huì)摔壞硬盤(pán)的，你看我話沒(méi)說(shuō)完你又把顯示器丟了……），咳咳，好吧，閑話少說(shuō)，我們從最大路的處理風(fēng)格談一談吧。這里面的大部分內(nèi)容并非我的獨(dú)創(chuàng)，從很久很久以前，數(shù)據(jù)庫(kù)程序員們就這樣做啦。
樹(shù)狀表的結(jié)構(gòu)化表達(dá)
在一切開(kāi)始前，我們先就樹(shù)狀表的表示方式達(dá)成一個(gè)共識(shí)。在關(guān)系型數(shù)據(jù)庫(kù)中，我們當(dāng)然沒(méi)有辦法這樣直接表示一個(gè)樹(shù)：
a
b c
d e f g
相應(yīng)的，我們會(huì)把它變形為平面表，這種變形讓我想起拓?fù)鋷缀危?br>
r n1 n2
a b d
a b e
a c f
a c g
存儲(chǔ)結(jié)構(gòu)
稍有經(jīng)驗(yàn)的朋友，大概都不會(huì)試著把樹(shù)狀結(jié)構(gòu)一層一列的存進(jìn)去了吧。這樣做的問(wèn)題是顯而易見(jiàn)的：與表中存儲(chǔ)的信息結(jié)構(gòu)不同，表的結(jié)構(gòu)應(yīng)該是相對(duì)固定的，不能隨便改動(dòng)。而對(duì)于層數(shù)不能固定的普通樹(shù)狀結(jié)構(gòu)，這是不可思議的。沒(méi)有必要討論過(guò)多的錯(cuò)誤，我們選擇一個(gè)相對(duì)正確的方式――把樹(shù)狀結(jié)構(gòu)抽象成適合關(guān)系數(shù)據(jù)庫(kù)的形式。
只考慮某一個(gè)節(jié)點(diǎn)的話，和這個(gè)節(jié)點(diǎn)相關(guān)的信息是：它的唯一標(biāo)識(shí)、父節(jié)點(diǎn)、子節(jié)點(diǎn)、數(shù)據(jù)信息。這其中只有子節(jié)點(diǎn)的數(shù)目不定。不過(guò)如果每一個(gè)節(jié)點(diǎn)都確定了自己的父節(jié)點(diǎn)，顯然可以省略子節(jié)點(diǎn)。這樣一來(lái)，一個(gè)節(jié)點(diǎn)需要存儲(chǔ)三部分信息――它的唯一標(biāo)識(shí)、父節(jié)點(diǎn)、數(shù)據(jù)信息。一個(gè)理想的treeview表只需要三個(gè)節(jié)點(diǎn)就可以了，用sql語(yǔ)句來(lái)表達(dá)就是
create table [dbo].[treeview] (
[id] [char] (10) primary key,
[pid] [char] (10) foreign key references [dbo].[treeview],
[data] [char] (10)
)
id是當(dāng)前節(jié)點(diǎn)的唯一標(biāo)識(shí)號(hào)，顯然它應(yīng)當(dāng)是主鍵；我們建立的是一個(gè)自閉的存儲(chǔ)結(jié)構(gòu)，每一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)也應(yīng)當(dāng)出自表中存儲(chǔ)的節(jié)點(diǎn)，所以pid列引用id作為外鍵；至于data，它是節(jié)點(diǎn)中的信息，通常和樹(shù)的結(jié)構(gòu)沒(méi)有絕對(duì)關(guān)系。我把這三列全設(shè)成char(10)，是為了后面做演示更方便，當(dāng)然也有人喜歡用自動(dòng)標(biāo)識(shí)列來(lái)做主鍵，在這種場(chǎng)合，也自有其優(yōu)點(diǎn)。為了維護(hù)數(shù)據(jù)的完整性或存儲(chǔ)、檢索等方面的考慮，實(shí)用中我們可能會(huì)采用更復(fù)雜的結(jié)構(gòu)，不過(guò)骨干就這樣子了。這個(gè)結(jié)構(gòu)從數(shù)學(xué)上講很簡(jiǎn)潔，而且是自洽的。如果一個(gè)節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)，那么它的pid就等于它自己的id。這并不違反我們關(guān)于主外鍵的定義。
信息的管理與使用
樹(shù)表的結(jié)構(gòu)確定后，問(wèn)題就集中在如何讀寫(xiě)其中的數(shù)據(jù)。
增加節(jié)點(diǎn)：增加一個(gè)葉節(jié)點(diǎn)很簡(jiǎn)單，只要指定這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，把它“掛接”到treeview中。從遞歸的角度來(lái)看，我們可以重復(fù)這一步驟，真到插入一個(gè)完整的子樹(shù)。相對(duì)而言，比較麻煩的是，如何把一個(gè)子節(jié)點(diǎn)插入到現(xiàn)有的樹(shù)中間，而不是最末端。比如存在一個(gè)節(jié)點(diǎn)n，它的根為r，現(xiàn)在要在r和n之間插入一個(gè)新節(jié)點(diǎn)n’，我們可以這樣做：把n’掛在r下面，作為它的子節(jié)點(diǎn)，然后把n的父節(jié)點(diǎn)指定為n’即可。
修改節(jié)點(diǎn)：這里指修改樹(shù)結(jié)構(gòu)，改變某一節(jié)點(diǎn)的父節(jié)點(diǎn)，在這種結(jié)構(gòu)中，修改是很方便的，只要調(diào)用標(biāo)準(zhǔn)的update就可以。
刪除節(jié)點(diǎn)：刪除節(jié)點(diǎn)時(shí)要注意這個(gè)節(jié)點(diǎn)下面還有沒(méi)有子節(jié)點(diǎn)，如果有，我們通常以兩種方式處理，一是把相關(guān)子節(jié)點(diǎn)全刪掉，如果是ms sql server 2000這樣的系統(tǒng)，你可以很簡(jiǎn)單的在建表時(shí)將外鍵約束指定為支持級(jí)聯(lián)刪除，自己寫(xiě)一個(gè)級(jí)聯(lián)刪除比較麻煩，不過(guò)也不是不可能，重點(diǎn)在于，為這個(gè)過(guò)程建立遞歸。簡(jiǎn)要示例如下：
--定義存儲(chǔ)過(guò)程
create procedure deletenode
@nodeid char(10)
as
begin
--以當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)作為記錄集建立游標(biāo)
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)--判斷記錄集是否成功打開(kāi)
begin
if (@@fetch_status <> -2)
begin
--遞歸調(diào)用
exec deletenode @childnode
end
fetch next from childnodes into @childnode
end
close childnodes
deallocate childnodes
--代碼執(zhí)行到這里，可以確定@nodeid不再有子節(jié)點(diǎn)，現(xiàn)在，我們刪除它
delete from treeview where id = @nodeid
end;
當(dāng)然，這是一種比較低效的設(shè)計(jì)，每一個(gè)將要?jiǎng)h除的節(jié)點(diǎn)都要執(zhí)行一次delete，比較有效率的方法是多深入一層，操作當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)。有興趣的讀者可以一試。
查詢：樹(shù)狀表的查詢是最有趣的內(nèi)容之一。當(dāng)然僅僅查出某一個(gè)節(jié)點(diǎn)的信息沒(méi)有太大的意思，我們希望的是得到從當(dāng)前節(jié)點(diǎn)一直向下（通常是到最底層）的完整子樹(shù)。這同樣需要一個(gè)遞歸。讓我們從一個(gè)歸納法游戲開(kāi)始，事先，我們先在treeview中插入以下數(shù)據(jù)：
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
歸納法第一步，當(dāng)然是構(gòu)造初值，查詢子樹(shù)的根節(jié)點(diǎn)就是標(biāo)準(zhǔn)的sql，select id, data form treeview where id = …，在這里有一個(gè)細(xì)節(jié)，查找表中所有的根節(jié)點(diǎn)（細(xì)心的讀者可能早就發(fā)現(xiàn)，我們?cè)O(shè)計(jì)的這個(gè)treeview可以存儲(chǔ)任意多個(gè)樹(shù)）可以通過(guò)select r.id, r.data form treeview r where r.id = r.pid來(lái)實(shí)現(xiàn)。簡(jiǎn)單起見(jiàn)，我們就從這里起步吧。
第二步，選擇出前兩層也不難，
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
我們要注意的是加藍(lán)的部分，這是增加一層后做改動(dòng)的部分。
很容易，我們得到前三層，
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
同樣的，我們重點(diǎn)觀察加藍(lán)的部分。相信經(jīng)過(guò)這兩步，大家會(huì)發(fā)現(xiàn)其中的規(guī)律?，F(xiàn)在我們可以把這個(gè)過(guò)程自動(dòng)化了……
……
不知道大家是否還記得前幾集里那個(gè)關(guān)于四色問(wèn)題的笑話，我又一次犯了這樣的錯(cuò)誤。一個(gè)多月以來(lái)，我就陷在這里不能自拔。顯然，我低估了問(wèn)題的難度。這個(gè)問(wèn)題似乎不能轉(zhuǎn)化為一個(gè)簡(jiǎn)單表達(dá)式，只能通過(guò)一個(gè)遞歸的流程來(lái)實(shí)現(xiàn)。而流程化的程序又非sql所長(zhǎng)。這里面有著各種各樣的麻煩。相信試過(guò)的朋友都有體會(huì)?，F(xiàn)在我使用的架構(gòu)問(wèn)題是顯然的，它需要明確知道到底從子樹(shù)的頂點(diǎn)向下到底有多少層。所以，計(jì)算樹(shù)的層數(shù)就首先被提了出來(lái)。
但是，但是，但是……（我簡(jiǎn)直沒(méi)臉見(jiàn)人啦）我一直找不到一個(gè)簡(jiǎn)潔優(yōu)雅的方法。一個(gè)多月的時(shí)間就這么過(guò)去了。我不得不一點(diǎn)點(diǎn)放棄我的原則（此乃人生墮落之始?。?。最后，我得承認(rèn)，要想寫(xiě)出一個(gè)優(yōu)雅的樹(shù)狀表選擇來(lái)，對(duì)我還是比較困難的。所以，在這一篇文章里，我們先討論到這里，樹(shù)狀表的選擇――其實(shí)應(yīng)該說(shuō)樹(shù)狀視圖構(gòu)造，還是留到下次再討論吧。
