VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)
首页 - 经验之谈 - 关于bbs树形结构的各种方法例子!
发表评论(0)作者:bigeagle, 平台:VB6.0+Win98, 阅读:11556, 日期:2000-12-26
bbs的树形结构显示可以有很多种方法,其中比较容易想到的是递归和排序串方法,但这两种方法并不是很好,那么怎样才算是比较合理的算法呢?
    递归方法不用讲,大家都知道怎么用,先讲讲排序串方法,最简单的排序串方法可以这样用,只用一个id就可以完成树型,向这样
1  001
2  002
3  001001
4  001001001
5  001002001
用这个字符串排序后就变成这样:
001
   001001
         001001001
   001002001
002
这种方法容易实现,但缺点也是很明显,一个是回帖数受限制,另一个随着回帖增加会越来越长,影响数据库效率。  

下面一种方法是李龙的,属于变通的排序串方法
DDL
--------------
CREATE TABLE dbo.Message
(
    ID          numeric(18,0) IDENTITY(1000,1),
    DateAndTime datetime      DEFAULT getdate() NOT NULL,
    AuthorID    numeric(18,0) NOT NULL,
    Subject     nvarchar(250) NOT NULL,
    Body        ntext         NULL,
    LinkURL     nvarchar(100) NULL,
    TextForLink nvarchar(50)  NULL,
    ImageURL    nvarchar(100) NULL,
    Class       int           DEFAULT 0 NOT NULL,
    ClientInfo  nvarchar(250) NULL,
    RemoteAddr  nvarchar(50)  NULL,
    CONSTRAINT PK_BBSMessage
    PRIMARY KEY NONCLUSTERED (ID,AuthorID)
)
go
CREATE TABLE dbo.MsgRefTab
(
    MsgID      numeric(18,0) NOT NULL,
    ParentID   numeric(18,0) NOT NULL,
    AncestorID numeric(18,0) NOT NULL,
    ChildNum   numeric(18,0) DEFAULT 0 NOT NULL,
    LinkStr    nvarchar(250) NOT NULL,
    CONSTRAINT PK_BBSRefTab
    PRIMARY KEY NONCLUSTERED (MsgID)
)
go
-----------------
存储过程:
-----------------
-- 抽出
CREATE PROCEDURE sp_Summary
@HaveBody bit,
@from numeric,
@to numeric
AS
IF (@HaveBody = 1)
select t.ID,t.DateAndTime,m.Nickname as
Author,m.Email,t.Subject,t.Body,t.LinkURL,t.TextForLink,t.ImageURL,s.ChildNu
m,s.ParentID
from Message t
  ,MsgRefTab AS s
  ,(SELECT MsgID FROM MsgRefTab WHERE ParentID = 0) AS f
  ,Members AS m
where t.ID=s.MsgID
  and f.MsgID = s.AncestorID
  and f.MsgID between @from and @to
  and m.MemberID = t.AuthorID
order by s.AncestorID,s.LinkStr
ELSE
select t.ID,t.DateAndTime,m.Nickname as
Author,m.Email,t.Subject,t.LinkURL,t.TextForLink,t.ImageURL,s.ChildNum,s.Par
entID
from Message t
  ,MsgRefTab AS s
  ,(SELECT MsgID FROM MsgRefTab WHERE ParentID = 0) AS f
  ,Members AS m
where t.ID=s.MsgID
  and f.MsgID = s.AncestorID
  and f.MsgID between @from and @to
  and m.MemberID = t.AuthorID
order by s.AncestorID,s.LinkStr
go

-- 加贴

CREATE PROCEDURE sp_Add_Message
@AuthorID numeric,
@Subject nvarchar(250),
@Body  ntext,
@LinkURL nvarchar(100),
@TextForLink nvarchar(50),
@ImageURL nvarchar(100),
@ParentID numeric,
@ID  numeric OUTPUT,
@ChildNum numeric OUTPUT,
@LinkStr nvarchar(250) OUTPUT,
@AncestorID numeric OUTPUT
AS
INSERT INTO Message(
  AuthorID,
  Subject,
  Body,
  LinkURL,
  TextForLink,
  ImageURL)
VALUES(
  @AuthorID,
  @Subject,
  @Body,
  @LinkURL,
  @TextForLink,
  @ImageURL)

SELECT @ID = @@IDENTITY

UPDATE MsgRefTab
SET
  ChildNum = ChildNum+1
WHERE
  MsgID = @ParentID

SELECT @ChildNum = ChildNum,
  @LinkStr = LinkStr,
  @AncestorID = AncestorID
FROM MsgRefTab
WHERE
  MsgID = @ParentID
go

---
是基于这样的想法:
贴子和跟贴都放在message表里,另有MsgRefTab对每一条信息都有描述。
父贴ParentID,0为不是子贴
祖宗贴AncestorID
直接跟贴数ChildNum
联接串LinkStr,学问都在这里,所有的跟贴都用一个数字字符串表示
如是
1011--->            为空
1012--->001         1011的跟贴,父贴LinkStr+父贴的子贴数+1
1013--->001001      1012的跟贴,父贴LinkStr+父贴的子贴数+1
1018--->001001001   1013的跟贴,父贴LinkStr+父贴的子贴数+1
1014--->001002      1012的跟贴,父贴LinkStr+父贴的子贴数+1
1017--->001002001   1014的跟贴,父贴LinkStr+父贴的子贴数+1

部分演示数据:
MsgID ParentID AncestorID ChildNum LinkStr
1010  0        1010       0
1011  0        1011       1
1012  1011     1011       3        001
1013  1012     1011       1        001001
1014  1012     1011       1        001002
1015  0        1015       0
1017  1014     1011       0        001002001
1018  1013     1011       0        001001001

下面这种方法是大怪兽和怡红公子现在采用的方法

create table forum
(
ID int NOT NULL IDENTITY,/*帖子序列号*/
rootID int NOT NULL, /*根帖子序列号*/
parentID int NOT NULL default=0,/*双亲帖子序列号*/
indent tinyint,/*缩进*/
order tinyint,/*同主题帖子排序*/
username varchar(40) NOT NULL,/*用户名*/
time daytime NOT NULL,/*贴帖子时间*/
IP varchar(15) NOT NULL,/*发帖子的IP*/
subject varchar(60) NOT NULL,/*帖子题目*/
text text,/*帖子正文*/
bytes int,/*帖子字数*/
status bit,/*状态*/
hits tinyint,/*hit数*/
primary key(ID) /*主关键字*/
)

简单地说用3个列描述层次结构
1.rootid   2.indent  3.同一个root下,order_no



1号贴
2号贴
3号贴
5号贴
4号贴
6号贴


这个结构的存储格式如下
id rootid indent 一个root下,order_no
1 1 0 0
2 1 1 1
3 1 2 2
4 4 0 0
5 1 1 3
6 4 1 1


按rootid,"一个root下,order_no"排序,
按indent缩进
即得树状到帖子列表

indent是4byte整数,从0开始的话,支持2147483648层
你要是定成numberic,那我也说不清支持几层


下面这种方法是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系统调用的开销来要小得多,另外,对系统内存
的要求降低到了最小,因此理论上认为是划算的。

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