bbs树形结构的实现方法(三)
发布时间:2006-10-14 2:41:37   收集提供:gaoqian
【bigeagle】 于 2000-12-6 14:45:13 加贴在 Joy ASP ↑:

下面这种方法是white提出来的。

BBS数据库结构的浮点数表示法

BBS由一系列的文章组成,每篇文章有一些基本属性,比如作者,创建时间,文章编号等。其中最为重要的,用以表示树形结构的是层和序数。层表示位于文章树的第几层,最高层的帖子层等于0,其回复的层为1,回复的回复层为2,以此类推。所有层等于0的帖子依时间顺序其序数分别为1,2,3.....剩下的帖子的序数满足以下条件:当所有帖子按照树形显示的时候,其序数从大到小排列,没有例外。

上述方法具体到BBS的实现时,各种操作如下进行:
0、系统维护一个记数器,表示当前使用的整数序数。
1、显示帖子列表:依序数值的大小倒序简单地显示即可,帖子的层可帮助决定退格的多少。2、新加帖子:如果是层0上的帖子,则取下一个整数序数作为该帖子序数;如果是层L1帖子,其序数为N1,则新帖子的层L=L1+1,然后到数据库中查找序数为N1的帖子的下一条帖子,取其序数,假设为N2,则新帖子的序数N=(N1+N2)/2。3、删除帖子:假设是删除层L1,序数为N1的帖子及其所有跟贴,则取层同为L1的下一个帖子
的序数N2,然后删除所有序数为从N1到N2(不包括N2)的帖子。

上述方法的最大优势在于显示帖子列表时不需要进行任何额外的操作,速度异常的快,根本不需要进行任何的递归操作。另外就是分页异常的方便,如果按照每页固定主题数,那么可以在SQL查询中仅仅返回当前页的记录,可以将对系统的资源利用降低到最小。即使按照每页固定帖子总数,也可以限制SQL查询仅仅返回一页所需的记录。

下面是一个各种值的直观表示(为了容易理解,这里按照序数的升序排列,实际实现时将按降序,以让最后的帖子显示在最前面):

1.topic1(层=0,序数=1)
  5.Re:topic1(层=1,序数=1.125)
  4.Re:topic1(层=1,序数=1.25)
  3.Re:topic1(层=1,序数=1.5)
    6.Re:Re:topic1(层=2,序数=1.75)
      8.Re:Re:Re:topic1(层=3,序数=1.7875)
    7.Re:Re:topic1(层=2,序数=1.825)
2.topic2(层=0,序数=2)
  10.Re:topic2(层=1,序数=2.5)
9.topic3(层=0,序数=3)
  11.Re:topic3(层=1,序数=3.5)

从上面这个例子中可以看出,随着层的增加,以及跟帖的增多,其序数的尾数越来越多,因此,这种方法的一个可能的问题是,SQL SERVER中无法表示足够小的浮点数,以至于将两条帖子的序数认为是一样的了。经过实验知道,SQL SERVER的浮点数有8位,最多能支持一条帖子有1023条回贴。

上述方法的另一个缺点是帖子列表时要做浮点的比较,插入帖子的时候要做浮点的加法和除法,不过除法因为刚好是除以2,所以在浮点运算时只需要较少的操作。但这属于机器指令级的开销增长,比起在脚本或VB程序里的递归导致WINDOWS系统调用的开销来要小得多,另外,对系统内存的要求降低到了最小,因此理论上认为是划算的。

请您就这种方法的可行性进行分析论证,因为我想把它设计成能支持大容量用户访问的系统,所以务必经过周密的分析。


 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50