采用左右值編碼的設(shè)計(jì)方案，在進(jìn)行類(lèi)別樹(shù)的遍歷時(shí)，由于只需進(jìn)行2次查詢(xún)，消除了遞歸，再加上查詢(xún)條件都為數(shù)字比較，效率極高，類(lèi)別樹(shù)的記錄條目越多，執(zhí)行效率越高。看到這里，相信不少人對(duì)這種設(shè)計(jì)方案有所心動(dòng)了，下面讓我們接著看看如何在這種表結(jié)構(gòu)中實(shí)現(xiàn)插入、刪除、同層平移節(jié)點(diǎn)（變更同層節(jié)點(diǎn)排序）的功能。
?
假定我們要在節(jié)點(diǎn)“肉類(lèi)”下添加一個(gè)子節(jié)點(diǎn)“牛肉”，該樹(shù)將變成：
???????????????????????????????????? 1商品18+2
????????????????????? +--------------------------------------------+
??????????????? 2食品11+2????????????????????????????????? 12+2電器17+2
????????? +-----------------+??????????????????????????????????? +-------------------------+
??? 3肉類(lèi)6+2?? 7+2蔬菜類(lèi)10+2???????? 13+2電視機(jī)14+2??? 15+2電冰箱16+2
??? +-------------+
4豬肉5? 6牛肉7? 8+2白菜9+2
?
看完上圖相應(yīng)節(jié)點(diǎn)左右值的變化后，相信大家都知道該如何寫(xiě)相應(yīng)的sql腳本吧？下面我給出相對(duì)完整的插入子節(jié)點(diǎn)的存儲(chǔ)過(guò)程：
CREATE?PROCEDURE?[dbo].[AddSubNodeByNode]
(
??? @type_id?int,
??? @name?varchar(50)
)
AS
declare?@rgt?int
if?exists (select?1?from tree where type_id=@type_id)
??? begin
?????? SET XACT_ABORT ON
?????? BEGIN?TRANSACTION
??????? select?@rgt=rgt from tree where type_id=@type_id
??????? update tree set rgt=rgt+2?where rgt>=@rgt
??????? update tree set lft=lft+2?where lft>=@rgt
??????? insert?into tree (name,lft,rgt) values (@name,@rgt,@rgt+1)???
??????? COMMIT?TRANSACTION
?????? SET XACT_ABORT OFF???
??? end
go
?
然后，我們刪除節(jié)點(diǎn)“電視機(jī)”，再來(lái)看看該樹(shù)會(huì)變成什么情況：
??????????????????????????????????????????? 1商品20-2
?????????????????????? +-----------------------------------+
??????????????? 2食品13??????????????????????????????? 14電器19-2
????????? +-----------------+???????????????
?????? 3肉類(lèi)8????????? 9蔬菜類(lèi)12????????????? 17-2電冰箱18-2
??? +----------+
4豬肉5? 6牛肉7? 10白菜11
?
　　相應(yīng)的存儲(chǔ)過(guò)程如下：
CREATE?PROCEDURE?[dbo].[DelNode]?
??? @type_id?int
AS
declare?@lft?int
declare?@rgt?int
if?exists (select?1?from tree where type_id=@type_id)
??? begin
?????? SET XACT_ABORT ON
?????? BEGIN?TRANSACTION
??????? select?@lft=lft,@rgt=rgt from tree where type_id=@type_id
??????? delete?from tree where lft>=@lft?and rgt<=@rgt
??????? update tree set lft=lft-(@rgt-@lft+1) where lft>@lft
??????? update tree set rgt=rgt-(@rgt-@lft+1) where rgt>@rgt
??????? COMMIT?TRANSACTION
?????? SET XACT_ABORT OFF???
End
?
　　注意：因?yàn)閯h除某個(gè)節(jié)點(diǎn)會(huì)同時(shí)刪除該節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)，而這些被刪除的節(jié)點(diǎn)的個(gè)數(shù)為：(被刪節(jié)點(diǎn)的右值-被刪節(jié)點(diǎn)的左值+1)/2，而任何一個(gè)節(jié)點(diǎn)同時(shí)具有唯一的左值和唯一的右值，故刪除作廢節(jié)點(diǎn)后，其他相應(yīng)節(jié)點(diǎn)的左、右值需要調(diào)整的幅度應(yīng)為：減少(被刪節(jié)點(diǎn)的右值-被刪節(jié)點(diǎn)的左值+1)。
?
? 最后，讓我們看看平移節(jié)點(diǎn)“電器”，將其和其所有子孫節(jié)點(diǎn)移動(dòng)到節(jié)點(diǎn)“食品”之前后，該樹(shù)會(huì)變成什么情況：
?
　　　　　　　　　　　　　1商品18
+-----------------------------------+
??????????????? 14-12電器17-12????????????????????? 2+4食品13+4
?????????????????????????????????????????????????????????????? +----------------------+???????????????
???????????? 15-12電冰箱16-12????? 3+4肉類(lèi)8+4????? 9+4蔬菜類(lèi)12+4???????
??????????????????????????????????????????????? +-------------------+
????????????????????????????????????? 4+4豬肉5+4???? 6+4牛肉7+4 10+4白菜11+4
?
大家仔細(xì)觀(guān)察一下交換后同層2個(gè)節(jié)點(diǎn)和其所有子孫節(jié)點(diǎn)左右值的變化，可以發(fā)現(xiàn)一個(gè)明顯的規(guī)律，那就是，節(jié)點(diǎn)“電器”及其所有子孫節(jié)點(diǎn)的左右值均減少12，而節(jié)點(diǎn)“食品”及其所有子孫節(jié)點(diǎn)的左右值均增加4。而節(jié)點(diǎn)“電器”+其子孫節(jié)點(diǎn)的數(shù)量為2，節(jié)點(diǎn)“食品”+其子孫節(jié)點(diǎn)的數(shù)量為6，這其中有什么聯(lián)系嗎？還記得我在刪除節(jié)點(diǎn)的存儲(chǔ)過(guò)程后面的注釋嗎？任何一個(gè)節(jié)點(diǎn)同時(shí)具有唯一的左值和唯一的右值。讓我們把節(jié)點(diǎn)數(shù)量*2，正好和節(jié)點(diǎn)左右值需要調(diào)整的幅度相等。由此規(guī)律，我們可以編寫(xiě)出類(lèi)似下面的存儲(chǔ)過(guò)程來(lái)實(shí)現(xiàn)節(jié)點(diǎn)同層前移的功能：
CREATE?PROCEDURE?[dbo].[MoveNodeUp]?
??? @type_id?int
AS
declare?@lft?int
declare?@rgt?int
declare?@layer?int
if?exists (select?1?from tree where type_id=@type_id)
??? begin
?????? SET XACT_ABORT ON
?????? BEGIN?TRANSACTION
??????? select?@lft=lft,@rgt=rgt,@layer=layer from TreeView where type_id=@type_id
??????? if?exists (select?*?from TreeView where rgt=@lft-1?and layer=@layer)
?????????? begin
?????????????? declare?@brother_lft?int
?????????????? declare?@brother_rgt?int
?????????????? select?@brother_lft=lft,@brother_rgt=rgt from TreeView where rgt=@lft-1?and layer=@layer
?????????????? update tree set lft=lft-(@brother_rgt-@brother_lft+1) where lft>=@lft?and rgt<=@rgt
?????????????? update tree set lft=lft+(@rgt-@lft+1) where lft>=@brother_lft?and rgt<=@brother_rgt
?????????????? update tree set rgt=rgt-(@brother_rgt-@brother_lft+1) where rgt>@brother_rgt?and rgt<=@rgt
?????????????? update tree set rgt=rgt+(@rgt-@lft+1) where lft>=@brother_lft+(@rgt-@lft+1) and rgt<=@brother_rgt
?????????? end
??????? COMMIT?TRANSACTION
?????? SET XACT_ABORT OFF???
??? end
?
　　注意：節(jié)點(diǎn)的同層平移可以采用臨時(shí)表來(lái)做中介，降低代碼的復(fù)雜度。不用臨時(shí)表來(lái)處理也行，但是update語(yǔ)句順序一定要考慮周詳。否則，一旦出現(xiàn)bug，對(duì)整個(gè)類(lèi)別表的破壞是驚人的，強(qiáng)烈推薦在做上述工作前對(duì)類(lèi)別表進(jìn)行完整備份。
?
　　同層下移的存儲(chǔ)過(guò)程和同層上移類(lèi)似，有興趣的朋友可以自己動(dòng)手編寫(xiě)體味一下其中的細(xì)節(jié)，我就不在這里列出來(lái)了。
?
　　最后，我對(duì)上面這種左右值編碼實(shí)現(xiàn)無(wú)限分級(jí)類(lèi)別樹(shù)的方案做一個(gè)總結(jié)：
　　優(yōu)點(diǎn)：在消除遞歸的前提下實(shí)現(xiàn)了無(wú)限分級(jí)，而且查詢(xún)條件是基于整形數(shù)字比較的，效率很高。可以進(jìn)行先序列表，添加，修改，刪除，同層平移等常規(guī)操作，基本滿(mǎn)足需求。
　　缺點(diǎn)：由于這種左右值編碼的方式和常見(jiàn)的阿拉伯?dāng)?shù)字直觀(guān)排序不同，再加上節(jié)點(diǎn)在樹(shù)中的層次，順序不是直觀(guān)顯示出來(lái)，而必須通過(guò)簡(jiǎn)單的公式計(jì)算后得到，需要花費(fèi)一定的時(shí)間對(duì)其數(shù)學(xué)模型進(jìn)行深入理解。而且，采用該方案編寫(xiě)相關(guān)存儲(chǔ)過(guò)程，新增，刪除，同層平移節(jié)點(diǎn)需要對(duì)整個(gè)樹(shù)進(jìn)行查詢(xún)修改，由此導(dǎo)致的代碼復(fù)雜度，耦合度較高，修改維護(hù)的風(fēng)險(xiǎn)較高。?

文章來(lái)源:http://x-spirit.spaces.live.com/Blog/cns!CC0B04AE126337C0!368.entry