使用多中值排序基数实现大型树状结构

使用多中值排序基数实现大型树状结构

    在“中值排序基数法实现树状结构”中，为了解决回复限制的问题，我们可以增加第二(三、四……)基数字段。
    其实在一般的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