使用多中值排序基數(shù)實(shí)現(xiàn)大型樹狀結(jié)構(gòu)

在“中值排序基數(shù)法實(shí)現(xiàn)樹狀結(jié)構(gòu)”中，為了解決回復(fù)限制的問題，我們可以增加第二(三、四……)基數(shù)字段。
其實(shí)在一般的BBS中，使用一個(gè)基數(shù)已經(jīng)足夠，因?yàn)橐粋�(gè)貼子的回復(fù)太多或深度太大的時(shí)候，無論你的樹狀結(jié)構(gòu)做得多好，由于屏幕的限制(顯示折行)，顯示總會亂，因此不如象在《補(bǔ)充》一文中，達(dá)到一定深度或個(gè)數(shù)時(shí)，后面的貼子采用平行顯示的方法，不過那部分已經(jīng)不再是樹狀結(jié)構(gòu)了。
原理：在貼子顯示的order by子句中，如果排序基數(shù)相同，則根據(jù)第二基數(shù)排序，從而避免樹狀結(jié)構(gòu)限制。

一、在BBS的內(nèi)容表中再增加一個(gè)第二基數(shù)字段ordernumS，同第一基數(shù)一樣，可為int或numeric，看需要定。

這樣在表中增加了四個(gè)冗余字段，rootid——用于記錄根id，deep——用于記錄回復(fù)的深度(為0時(shí)表示根貼)，ordernum——第一排序基數(shù)，ordernumS——第二排序基數(shù)

表forum與(只列與樹狀結(jié)構(gòu)有關(guān)的字段)：
id rootid deepordernumordernumS
其中id、rootid、deep均為int型(deep可為tinyint型)，ordernum為int或float型，ordernumS(默認(rèn)值為0)同ordernum。

例：(在此為了簡單，使用一個(gè)小的起始排序基數(shù)，且為int型，以清楚觀察什么時(shí)候第二排序基數(shù)起作用)。
(下面所說的排序均指按ordernum從小到大，ordernumS從小到大排序，即order by ordernum,ordernumS)
(下面所說的精度為后貼與前貼的ordernum的差，精度標(biāo)記指的是這個(gè)差大于某個(gè)值這個(gè)條件，比如(后貼的ordernum-前貼的ordernum)>1)

id rootiddeepordernumordernumS
10000
21180
_____________________________________
31140回復(fù)第1貼，第一基數(shù)取1、2貼的第一基數(shù)中值即(0+8)/2=4

排序后結(jié)果為：
id rootiddeepordernumordernumS
10000
31140
21180
_____________________________________
41260回復(fù)第3貼，第一基數(shù)取3、2的第一基數(shù)中值即(4+8)/2

排序后結(jié)果為:
id rootiddeepordernumordernumS
10000
31140
41260
21180
_____________________________________
51370回復(fù)第4貼，第一基數(shù)取4、2的第一基數(shù)中值即(6+8)/2

排序后的結(jié)果為：
id rootiddeepordernumordernumS
10000
31140
41260
51370
21180
_____________________________________
61368 回復(fù)第4貼，第一基數(shù)取4、5的第一基數(shù)中值即(6+7)/2，因是int型，被截成了6
此時(shí)精度標(biāo)記(暫設(shè)為1)已經(jīng)不滿足(即5的第一基數(shù)與4的第一基數(shù)差不大于1，為1)，此時(shí)在父貼的第二基數(shù)加上一起始值作為新貼的第二基數(shù)
排序后的結(jié)果為：
id rootiddeepordernumordernumS
10000
31140
41260
61368
51370
21180
_____________________________________
71364 回復(fù)第4貼，第一基數(shù)取4、6的第一基數(shù)中值即(6+6)/2=6
此時(shí)精度標(biāo)記(暫設(shè)為1)已經(jīng)不滿足(即4的第一基數(shù)與6的第一基數(shù)差不大于1，為0)，此時(shí)第二基數(shù)取6、4的第二基數(shù)中值(0+8)/2=4


排序后的結(jié)果為：
id rootiddeepordernumordernumS
10000
31140
41260
71364
61368
51370
21180

這樣排序基數(shù)ordernum、ordernumS與回復(fù)深度deep一起就實(shí)現(xiàn)了如下的樹狀結(jié)構(gòu)：
id
1
3
 4
 7
 6
 5
2

在這可以看到，第一基數(shù)ordernum與第二基數(shù)ordernumS以及深度deep實(shí)現(xiàn)了樹狀結(jié)構(gòu)！


二、插入的實(shí)現(xiàn)(如何確定排序基數(shù)，下面所指貼子均為同一根下的子貼)
(一)根第一基數(shù)ordernum定為0
(二)所有貼子第二基數(shù)默認(rèn)為0
(三)第一條回復(fù)貼子基數(shù)定為2的整數(shù)次冪(如65536=2^16，可取更大的數(shù))
(四)回復(fù)樹中最后一條貼子時(shí)，基數(shù)取最后一貼的基數(shù)ordernum再加上2的整數(shù)次冪(同上)
(五)當(dāng)?shù)谝换鶖?shù)差大于精度標(biāo)記時(shí)，第一基數(shù)取中值，忽略第二基數(shù)(為0)
(五)當(dāng)?shù)谝换鶖?shù)差等于精度標(biāo)記時(shí)，第一基數(shù)取回復(fù)貼的第一基數(shù)，第二基數(shù)取回復(fù)貼的第二基數(shù)加上基數(shù)起始值
(六)當(dāng)?shù)谝换鶖?shù)差小于精度標(biāo)記時(shí)，第一基數(shù)取回復(fù)貼的第一基數(shù)，第二基數(shù)取前后貼的第二基數(shù)中值

如果要使用parentid字段，則更新相關(guān)的parentid，這里不再討論。

三、刪除的實(shí)現(xiàn)

刪除貼子(剪枝)時(shí)，當(dāng)：
(一)要?jiǎng)h除的是根貼時(shí)，將整個(gè)樹刪除即可
(二)要?jiǎng)h除的是子枝時(shí)，只需按ordernum和ordernumS排序，找出從指定要?jiǎng)h除的貼子開始的所有貼子(使用條件rootid=@rootid and (ordernum>@ordernum or ordernum=@ordernum and ordernumS>=@ordernumS))，從上到下逐個(gè)判斷深度是不是增加，如果增加則予以刪除。一旦發(fā)現(xiàn)深度等于或小于要?jiǎng)h貼子(枝頂)的深度，則馬上退出刪除。
如上例子中，要?jiǎng)h除4貼一個(gè)分枝，只需找出4后面的所有貼子，然后逐個(gè)往下判斷，如果深度大小4貼的深度則刪除，而一旦遇到深度等于或者小于4貼深度，則馬上退出刪除。結(jié)果是4、7、6、5滿足條件，這就是我們要?jiǎng)h除的子枝。
如果要增加parentid字段，則需判斷共刪除了多少個(gè)貼子，以例更新有關(guān)的parentid字段。
為了方便和提高速，使用操作API光標(biāo)的存儲過程來進(jìn)行。

四、顯示的實(shí)現(xiàn)
只需執(zhí)行select * from forum order by rootid+id-sign(rootid)*id desc,ordernum，ordernumS，然后結(jié)合deep就可實(shí)現(xiàn)樹狀的顯示。


五、具體實(shí)現(xiàn)方法(以存儲過程為例)

加貼存儲過程：(ordernum和ordernumS使用int型，設(shè)精度標(biāo)記為1)

CREATE PROCEDURE [add] @keyid int,@message varchar(50) OUTPUT———keyid為回復(fù)的貼子id號，如果是新貼則為0，@message為出錯(cuò)信息
AS
IF (@keyid=0)
INSERT INTO forum (rootid,deep,ordernum,ordernumS……) values(0,0,0,0……)
ELSE
BEGIN
 DECLARE @rootid int,@id int,@deep int,@begnum int,@endnum intt,@begS int,endS int,@ordernum int,@ordernumS int
 SELECT @rootid=0,@id=0,@deep=0,@begnum=0,@endnum=0,@ordernum=0,@ordernumS=0,@begS=0,@endS=0
 SELECT @rootid=rootid,@id=id,@begnum=ordernum,@begs=begs,@deep=deep from forum where id=@keyid
 IF (@id=0)
 BEGIN
SELECT @message='要回復(fù)的貼子已經(jīng)被刪除！'
return
 END
 ELSE
 BEGIN
IF (@rootid=0) SELECT @rootid=@id——回復(fù)的是根貼，取其id為新加貼的rootid
#1SELECT top 1 @endnum=ordernum,@endS=ordernumS where rootid=@rootid and id<>@id by ordernum,ordernumS ——取回復(fù)貼子后面的那條貼出來
if @endnum-@begnum>1
SELECT @ordernum=(@begnum+@endnum)/2,@ordernumS=0——精度大小精度標(biāo)記(在取為1)，忽略第二基數(shù)(定為0)
else
BEGIN
select case @endnum-begnum
case 1
select @ordernum=@begnum,@ordernumS=@begS+65536 ——在父貼的第二基數(shù)基礎(chǔ)上加一起始值作為新貼第二基數(shù)，實(shí)際應(yīng)用中可在此限制范圍以防溢出
case 0
select @ordernum=@begnum,@ordernumS=(@begS+endS)/2——取第二基數(shù)中值作為新貼第二基數(shù)
case else ——小于0(即@begnum=0)，表示#1句中沒有找到后面一條貼子，即要回復(fù)的是樹中的最后一條貼子
SELECT @ordernum=@begnum+65536,@ordernumS=0 ——實(shí)際應(yīng)用中可限制@ordernum的范圍，以免溢出
end select
END
INSERT into forum (rootid,deep,ordernum,orderS……) values(@rootid,@deep+1,@ordernum,@ordernumS……)
 END
END
Select @message='成功'
return



剪枝存儲過程：
CREATE PROCEDURE [del] @keyid int,@message varchar(50) OUTPUT———keyid為要?jiǎng)h除的貼子id號，如果是新貼則為0，@message為出錯(cuò)信息
AS
DECLARE @rootid int,@id int,@deep int,@deept int
SELECT @rootid=0,@id=0,@deep=0,@deept=0
SELECT @id=id,@rootid=rootid,@deept=deep from forum where id=@keyid
IF (@id=0)
BEGIN
 SELECT @message='該貼子不存在！"
 return
END
ELSE
BEGIN
if (@rootid=0) ——要?jiǎng)h的是根貼
delete from forum where id=@id or rootid=@id
else——剪子枝
BEGIN
DECLARE forum_cur CURSOR
 FOR
SELECT deep FROM forum WHERE rootid=@rootid and (ordernum>@ordernum or ordernum=@ordernum and ordernumS>=@ordernumS) order by ordernum,ordernumS
OPEN forum_cur
FETCH FROM forum_cur INTO @deep
DELETE FROM forum where CURRENT OF forum_cur——?jiǎng)h除最頂枝
WHILE @@fetch_status=0
BEGIN
FETCH FROM forum_cur INTO @deep
IF (@deep<=@tdeep) or @@fetch_status<>0——一旦發(fā)現(xiàn)深比枝頂?shù)纳钕嗟然蜻�要小或者游標(biāo)到了尾部，則馬上退出
BEGIN
select @message='成功刪除子枝'
CLOSE forum_cur
DEALLOCATE forum_cur
return
END
DELETE FROM forum WHERE CURRENT OF forum_cur
END
END
CLOSE freelt_cur
DEALLOCATE forum_cur
END
END

顯示(略)


過程看起來比使用單個(gè)排序基數(shù)復(fù)雜了不少，其實(shí)主要是判斷何時(shí)給第二基數(shù)賦值的問題。
注意事項(xiàng)：基數(shù)起始值不能取類型的最大值，比如int的最大限制為2^31，則基數(shù)起始值要預(yù)留空間，否則最后的子貼是無法回復(fù)的��！(或者如果限制了ordernum的范圍，雖然可以回復(fù)，但它是平行顯示的)
使用了兩個(gè)基數(shù)的時(shí)候，一個(gè)子貼的回復(fù)數(shù)最多了900左右(int類型,30*30)，14400(使用numeric類型時(shí)——此時(shí)的精度標(biāo)記得細(xì)加斟酌)，理論是有限制都是不夠的，但實(shí)際上并不需要這么多。
對于基數(shù)分布不均勻的問題是無法解決的，因?yàn)閷?shí)際上回復(fù)客戶回復(fù)哪條貼子是不可預(yù)測的。
使用2的冪作為基數(shù)，是很容易理解的——不易近起結(jié)果取近似值(除非達(dá)到了計(jì)算機(jī)的最大精度)，另一個(gè)原因是計(jì)算機(jī)使用二進(jìn)制進(jìn)行運(yùn)算，乘除2只是位移操作，速度要比其它數(shù)快得多(我是這么想的)。另一個(gè)個(gè)人的原因是因?yàn)槲覀�(gè)算法是源于以前的思想：收斂數(shù)列與遞歸算法。
由于增加了算法復(fù)雜程度和冗余字段，如非必要，實(shí)非不必。
其實(shí)我是沒有時(shí)間進(jìn)行測試的，如果由于考慮不周或者算法錯(cuò)誤引起無法使用，還請多多指教。

歡迎訪問我的個(gè)人主頁http://swuse.yeah.net