在“中值排序基数法实现树状结构”中，为了解决回复限制的问题，我们可以增加第二(三、四……)基数字段。
其实在一般的bbs中，使用一个基数已经足够，因为一个贴子的回复太多或深度太大的时候，无论你的树状结构做得多好，由于屏幕的限制(显示折行)，显示总会乱，因此不如象在《补充》一文中，达到一定深度或个数时，后面的贴子采用平行显示的方法，不过那部分已经不再是树状结构了。
原理：在贴子显示的order by子句中，如果排序基数相同，则根据第二基数排序，从而避免树状结构限制。
一、在bbs的内容表中再增加一个第二基数字段ordernums，同第一基数一样，可为int或numeric，看需要定。
这样在表中增加了四个冗余字段，rootid——用于记录根id，deep——用于记录回复的深度(为0时表示根贴)，ordernum——第一排序基数，ordernums——第二排序基数
表forum与(只列与树状结构有关的字段)：
id rootid deep ordernum ordernums
其中id、rootid、deep均为int型(deep可为tinyint型)，ordernum为int或float型，ordernums(默认值为0)同ordernum。
例：(在此为了简单，使用一个小的起始排序基数，且为int型，以清楚观察什么时候第二排序基数起作用)。
(下面所说的排序均指按ordernum从小到大，ordernums从小到大排序，即order by ordernum,ordernums)
(下面所说的精度为后贴与前贴的ordernum的差，精度标记指的是这个差大于某个值这个条件，比如(后贴的ordernum-前贴的ordernum)>1)
id rootid deep ordernum ordernums
1 0 0 0 0
2 1 1 8 0
_____________________________________
3 1 1 4 0 回复第1贴，第一基数取1、2贴的第一基数中值即(0+8)/2=4
排序后结果为：
id rootid deep ordernum ordernums
1 0 0 0 0
3 1 1 4 0
2 1 1 8 0
_____________________________________
4 1 2 6 0 回复第3贴，第一基数取3、2的第一基数中值即(4+8)/2
排序后结果为:
id rootid deep ordernum ordernums
1 0 0 0 0
3 1 1 4 0
4 1 2 6 0
2 1 1 8 0
_____________________________________
5 1 3 7 0 回复第4贴，第一基数取4、2的第一基数中值即(6+8)/2
排序后的结果为：
id rootid deep ordernum ordernums
1 0 0 0 0
3 1 1 4 0
4 1 2 6 0
5 1 3 7 0
2 1 1 8 0
_____________________________________
6 1 3 6 8 回复第4贴，第一基数取4、5的第一基数中值即(6+7)/2，因是int型，被截成了6
此时精度标记(暂设为1)已经不满足(即5的第一基数与4的第一基数差不大于1，为1)，此时在父贴的第二基数加上一起始值作为新贴的第二基数
排序后的结果为：
id rootid deep ordernum ordernums
1 0 0 0 0
3 1 1 4 0
4 1 2 6 0
6 1 3 6 8
5 1 3 7 0
2 1 1 8 0
_____________________________________
7 1 3 6 4 回复第4贴，第一基数取4、6的第一基数中值即(6+6)/2=6
此时精度标记(暂设为1)已经不满足(即4的第一基数与6的第一基数差不大于1，为0)，此时第二基数取6、4的第二基数中值(0+8)/2=4
排序后的结果为：
id rootid deep ordernum ordernums
1 0 0 0 0
3 1 1 4 0
4 1 2 6 0
7 1 3 6 4
6 1 3 6 8
5 1 3 7 0
2 1 1 8 0
这样排序基数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
#1 select 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
Java Asp PHP .Net XML C/C++ CGI VB Jsp J2ee J2se J2me EJB Servlet Tomcat Resin Struts Weblogic Eclipse ANT GUI JMS Web servise IDEA Webphere Hibernate Spring Jboss Applet Swing Socket Javamail Perl Ajax P2P 安全 模式 框架 测试 开源 游戏
Windows XP Windows 2000 Windows 2003 Windows Me Windows 9.x Linux UNIX 注册表 操作系统 服务器 应用服务器
