|
使用多中值排序基數實現大型樹狀結構
在“中值排序基數法實現樹狀結構”中，為了解決回復限制的問題，我們可以增加第二(三、四……)基數字段。
其實在一般的BBS中，使用一個基數已經足夠，因為一個貼子的回復太多或深度太大的時候，無論你的樹狀結構做得多好，由于屏幕的限制(顯示折行)，顯示總會亂，因此不如象在《補充》一文中，達到一定深度或個數時，后面的貼子采用平行顯示的方法，不過那部分已經不再是樹狀結構了。
原理：在貼子顯示的order by子句中，如果排序基數相同，則根據第二基數排序，從而避免樹狀結構限制。
一、在BBS的內容表中再增加一個第二基數字段ordernumS，同第一基數一樣，可為int或numeric，看需要定。
這樣在表中增加了四個冗余字段，rootid——用于記錄根id，deep——用于記錄回復的深度(為0時表示根貼)，ordernum——第一排序基數，ordernumS——第二排序基數
表forum與(只列與樹狀結構有關的字段)：
id rootid deepordernumordernumS
其中id、rootid、deep均為int型(deep可為tinyint型)，ordernum為int或float型，ordernumS(默認值為0)同ordernum。
例：(在此為了簡單，使用一個小的起始排序基數，且為int型，以清楚觀察什么時候第二排序基數起作用)。
(下面所說的排序均指按ordernum從小到大，ordernumS從小到大排序，即order by ordernum,ordernumS)
(下面所說的精度為后貼與前貼的ordernum的差，精度標記指的是這個差大于某個值這個條件，比如(后貼的ordernum-前貼的ordernum)>1)
id rootiddeepordernumordernumS
10000
21180
_____________________________________
31140回復第1貼，第一基數取1、2貼的第一基數中值即(0+8)/2=4
排序后結果為：
id rootiddeepordernumordernumS
10000
31140
21180
_____________________________________
41260回復第3貼，第一基數取3、2的第一基數中值即(4+8)/2
排序后結果為:
id rootiddeepordernumordernumS
10000
31140
41260
21180
_____________________________________
51370回復第4貼，第一基數取4、2的第一基數中值即(6+8)/2
排序后的結果為：
id rootiddeepordernumordernumS
10000
31140
41260
51370
21180
_____________________________________
61368 回復第4貼，第一基數取4、5的第一基數中值即(6+7)/2，因是int型，被截成了6
此時精度標記(暫設為1)已經不滿足(即5的第一基數與4的第一基數差不大于1，為1)，此時在父貼的第二基數加上一起始值作為新貼的第二基數
排序后的結果為：
id rootiddeepordernumordernumS
10000
31140
41260
61368
51370
21180
_____________________________________
71364 回復第4貼，第一基數取4、6的第一基數中值即(6+6)/2=6
此時精度標記(暫設為1)已經不滿足(即4的第一基數與6的第一基數差不大于1，為0)，此時第二基數取6、4的第二基數中值(0+8)/2=4
排序后的結果為：
id rootiddeepordernumordernumS
10000
31140
41260
71364
61368
51370
21180
這樣排序基數ordernum、ordernumS與回復深度deep一起就實現了如下的樹狀結構：
id
1
3
4
7
6
5
2
在這可以看到，第一基數ordernum與第二基數ordernumS以及深度deep實現了樹狀結構！
二、插入的實現(如何確定排序基數，下面所指貼子均為同一根下的子貼)
(一)根第一基數ordernum定為0
(二)所有貼子第二基數默認為0
(三)第一條回復貼子基數定為2的整數次冪(如65536=2^16，可取更大的數)
(四)回復樹中最后一條貼子時，基數取最后一貼的基數ordernum再加上2的整數次冪(同上)
(五)當第一基數差大于精度標記時，第一基數取中值，忽略第二基數(為0)
(五)當第一基數差等于精度標記時，第一基數取回復貼的第一基數，第二基數取回復貼的第二基數加上基數起始值
(六)當第一基數差小于精度標記時，第一基數取回復貼的第一基數，第二基數取前后貼的第二基數中值
如果要使用parentid字段，則更新相關的parentid，這里不再討論。
三、刪除的實現
刪除貼子(剪枝)時，當：
(一)要刪除的是根貼時，將整個樹刪除即可
(二)要刪除的是子枝時，只需按ordernum和ordernumS排序，找出從指定要刪除的貼子開始的所有貼子(使用條件rootid=@rootid and (ordernum>@ordernum or ordernum=@ordernum and ordernumS>=@ordernumS))，從上到下逐個判斷深度是不是增加，如果增加則予以刪除。一旦發現深度等于或小于要刪貼子(枝頂)的深度，則馬上退出刪除。
如上例子中，要刪除4貼一個分枝，只需找出4后面的所有貼子，然后逐個往下判斷，如果深度大小4貼的深度則刪除，而一旦遇到深度等于或者小于4貼深度，則馬上退出刪除。結果是4、7、6、5滿足條件，這就是我們要刪除的子枝。
如果要增加parentid字段，則需判斷共刪除了多少個貼子，以例更新有關的parentid字段。
為了方便和提高速，使用操作API光標的存儲過程來進行。
四、顯示的實現
只需執行select * from forum order by rootid+id-sign(rootid)*id desc,ordernum，ordernumS，然后結合deep就可實現樹狀的顯示。
五、具體實現方法(以存儲過程為例)
加貼存儲過程：(ordernum和ordernumS使用int型，設精度標記為1)
CREATE PROCEDURE [add] @keyid int,@message varchar(50) OUTPUT———keyid為回復的貼子id號，如果是新貼則為0，@message為出錯信息
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='要回復的貼子已經被刪除！'
return
END
ELSE
BEGIN
IF (@rootid=0) SELECT @rootid=@id——回復的是根貼，取其id為新加貼的rootid
#1SELECT top 1 @endnum=ordernum,@endS=ordernumS where rootid=@rootid and id<>@id by ordernum,ordernumS ——取回復貼子后面的那條貼出來
if @endnum-@begnum>1
SELECT @ordernum=(@begnum+@endnum)/2,@ordernumS=0——精度大小精度標記(在取為1)，忽略第二基數(定為0)
else
BEGIN
select case @endnum-begnum
case 1
select @ordernum=@begnum,@ordernumS=@begS+65536 ——在父貼的第二基數基礎上加一起始值作為新貼第二基數，實際應用中可在此限制范圍以防溢出
case 0
select @ordernum=@begnum,@ordernumS=(@begS+endS)/2——取第二基數中值作為新貼第二基數
case else ——小于0(即@begnum=0)，表示#1句中沒有找到后面一條貼子，即要回復的是樹中的最后一條貼子
SELECT @ordernum=@begnum+65536,@ordernumS=0 ——實際應用中可限制@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為要刪除的貼子id號，如果是新貼則為0，@message為出錯信息
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) ——要刪的是根貼
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——刪除最頂枝
WHILE @@fetch_status=0
BEGIN
FETCH FROM forum_cur INTO @deep
IF (@deep<=@tdeep) or @@fetch_status<>0——一旦發現深比枝頂的深相等或還要小或者游標到了尾部，則馬上退出
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
顯示(略)
過程看起來比使用單個排序基數復雜了不少，其實主要是判斷何時給第二基數賦值的問題。
注意事項：基數起始值不能取類型的最大值，比如int的最大限制為2^31，則基數起始值要預留空間，否則最后的子貼是無法回復的��！(或者如果限制了ordernum的范圍，雖然可以回復，但它是平行顯示的)
使用了兩個基數的時候，一個子貼的回復數最多了900左右(int類型,30*30)，14400(使用numeric類型時——此時的精度標記得細加斟酌)，理論是有限制都是不夠的，但實際上并不需要這么多。
對于基數分布不均勻的問題是無法解決的，因為實際上回復客戶回復哪條貼子是不可預測的。
使用2的冪作為基數，是很容易理解的——不易近起結果取近似值(除非達到了計算機的最大精度)，另一個原因是計算機使用二進制進行運算，乘除2只是位移操作，速度要比其它數快得多(我是這么想的)。另一個個人的原因是因為我個算法是源于以前的思想：收斂數列與遞歸算法。
由于增加了算法復雜程度和冗余字段，如非必要，實非不必。
其實我是沒有時間進行測試的，如果由于考慮不周或者算法錯誤引起無法使用，還請多多指教。
歡迎訪問我的個人主頁http://swuse.yeah.net
|
