树型论坛的快速算法
左轻侯
2001.10.9

树型论坛（即阶梯式论坛）的实现算法，是一直被讨论的问题。总结起来，一般无非是两种：第一是递归。这种方式最简单，思路最清楚，但是效率也最低，特别是进行页定位的时候。由于每进行一次递归调用，就必须执行一条数据库查询，使它在大量并发请求时的负载成为灾难性的。因此这种算法一般不实用。第二是增加一个排序字段，思路是使用一个特殊设计的字段，例如排序串或者中值排序基数，来实现贴子的插入，在显示的时候，只需要为每一个主贴执行一次查询，将所有得到的记录按序显示即可。这种方式在效率上有了很大提高，但是仍然不很理想，而且使得插入的代码增加了不必要的复杂性，同时还往往导致了支持层次有限制的问题。
有没有一种办法可以简单、高效地实现树型论坛呢？我想到了一种算法，在显示速度上应该超过我见的任何类似算法，实现起来也不复杂。
思路很简单：就是完全不理会树型结构本身，将整个论坛视为一个简单的顺序表。这样不论任何形式的页面，只需要一条查询即可得到。那么如何实现树型结构呢？方法是添加两个格式化字段，一个记录顺序表的次序，一个记录树的层次，对取得的记录集进行相应格式化，即可得到原汁原味的树型论坛。
具体实现方法如下：
1、数据库结构。只列出必需的字段，全部为int型：
id：贴子序号
ordernum：排序字段，按照显示顺序从大到小，最早的一条贴子为1
levelnum：树的层次，0为主贴，以此类推
2、显示。使用一条语句：“select * from article order by ordernum DESC”，得到需要的记录集。遍历记录集，检查它的levelnum字段，设置相应的缩进。为0则是主贴，不缩进，为1则缩进一层，以此类推，然后显示之。
3、插入。关键是如何设置ordernum字段。分为两种情况：
一是发新的主贴，相当于在顺序表的最后添加一条记录。这样最简单，只需要通过查询，得到max(ordernum)，然后将ordernum字段设置为该值加1即可。
二是跟贴，相当于在顺序表的中间插入一条记录。方法是，先得到插入点的ID（即跟贴的父贴ID），将该贴的ordernum值赋予新贴，然后将所有插入点之前（包括插入点本身）的记录的ordernum全部加1，等于让它们在顺序表中往后移一位，腾出位置。举例来说：要在一个ID为23的贴子之后跟贴，首先select得到ID23的ordernum，假设为18，将其赋予新贴的ordernum；然后执行“update article set ordernum = ordernum + 1 where ordernum >= 18”，将新贴之后的贴子全部后移。
效率分析：
显示速度应该不会更快了，仅仅是一条简单的select，对一个int字段进行排序，而且支持无限的回复层次。相比之下，递归需要为一个页面中的每一条贴子进行一次select，对datetime字段进行排序，而“主贴排序字段法”需要为每一个主贴进行一次select，对char字段进行排序。
最大的问题在于插入时，如果插入的位置很靠前，可能要更新大量记录的ordernum字段。但是经验告诉我们，这种树型论坛，回复一般都集中在第一二页，极少有人回复很久以前的贴子，所以偶尔为之，也不会增加太大的负担。如果你实在不放心，也可以用技术手段强制禁止回复一段时间之前的贴子。