无限分类与树型论坛的实现方法
――浮点型字段排序法
joe teng 2005.6.12
在此我不想讨论其他实现方法的利与弊。
既然是使用字段排序，那么我们便设一个名为order的字段。问题是，在这里是使用整数还是使用浮点数类型呢？考虑到会有在两个连续order值中间插入新值的可能，自然是需要使用浮点类型了。
建一个menus表，我们还需要以下字段：
id ： 类别编号
mainid ： 主分类编号，但不作具体分类使用。如果在树型论坛里，它代表的是主题id
parentid ： 父类编号
level ： 类别级别，作用其实是方便显示的时候作其他处理
info ： 类别名称等。
由此可以得到menus的表结构：
create table `menus` (
`id` int( 10 ) unsigned not null auto_increment ,
`mainid` int( 10 ) unsigned not null ,
`parentid` int( 10 ) unsigned not null ,
`order` float unsigned not null ,
`level` smallint( 5 ) unsigned not null ,
`info` varchar( 128 ) not null ,
index ( `mainid` , `parentid` , `order` , `level` ) ,
unique (
`id`
)
) type = myisam ;
很容易可以看出，输入的时候是如此简单便实现树结构了:
select * from `menus` order by `mainid` asc, `order` asc ;
前提是添加类别的时候，order能正确排序。
添加根分类：
很简单,取得上一个主类的mainid， 如a_mainid，则新根分类的mainid则为a_mainid + 1。parentid 为 0 ， order 为0， level也为0， info则自行设定。
添加子分类：
核心思想是，取得新增子分类的前一个分类的order以及它后一个分类的order。
取得前一个分类的order是这里的难点，因为涉及到同级与非同级的情况。非同级的情况很简单，新增别类的前一个order其实就是它的父类的order。如果有同级分类，情况就很复杂了，因为它前面的同级分类有可能会拥有子分类，子分类下又可能还会有子分类，如此下来，要取得前一个order就很难了。
解决的办法有两个：
1.取得新增类同级的前一个类别,如类别a的id，使用递归的方法，直到取得a类别下最后最小分类的order，那便是要新增分类的前一个order了。这种方法的缺点是，如果a类别下有很多子分类，那么递归需要一定的时间。这种方法适用于普通的分类处理，不适用于树型论坛。不过总体来说，因为是添加类别的时候才使用递归，输出类别的时候跟前面一样，效率还是很高的。
2.作一个记录，记录着与a有关联的最后order。于是我们就需要增加一个表，建利关系树。这种关系树做起来很简单。表结构如下：
create table `menu_tree` (
`mainid` int(10) unsigned not null default '0',
`tree` text not null,
`order` float unsigned not null default '0',
key `mainid` (`mainid`,`order`),
fulltext key `tree` (`tree`)
) type=myisam;
(构建方式请看我后面给出的源码)
取得前一个order之后，要取得后一个order就很简单了。取同mainid下大于前一个order的最小order便是了。如果存在后一个order，那么新增order就取前一个order与后一个order的平均值。如果不存在后一个order，那说明新增类别是main下的最小order，取大于前一个order的最小整数就行了。
主要实现方法便如上面说的。
处理方法
'localhost', user => 'root', password => '123456', dbname => 'test'
);
$resdbc = mysql_connect ( $arrdatabase[host], $arrdatabase[user], $arrdatabase[password] );
mysql_select_db( $arrdatabase['dbname'] );
if ( ! class_exists ( freeroad ))
{
class freeroad
{
var $resdbc ;
var $strdatabase ;
var $strmenutable ;
var $strmenutreetable ;
var $strfiled_id = 'id' ;
var $strfiled_mainid = 'mainid' ;
var $strfiled_parentid = 'parentid' ;
var $strfiled_order = 'order' ;
var $strfiled_level = 'level' ;
function freeroad ( $resdbc , $strdatabase , $strmenutable , $strmenutreetable , $arrsetfileds = array() )
{
$this->resdbc = $resdbc ;
$this->strdatabase = $strdatabase;
$this->strmenutable = $strmenutable ;
$this->strmenutreetable = $strmenutreetable ;
if ( sizeof ( $arrsetfileds ) > 0 )
{
$this->strfiled_id = $arrsetfileds['id'] ;
$this->strfiled_mainid = $arrsetfileds['mainid'] ;
$this->strfiled_parentid = $arrsetfileds['parentid'] ;
$this->strfiled_order = $arrsetfileds['order'] ;
$this->strfiled_level = $arrsetfileds['level'] ;
}
}
function get_new_mainid ()
{
mysql_select_db ( $this->strdatabase , $this->resdbc ) ;
$strquery = select `$this->strfiled_mainid`
from `$this->strmenutable`
where `$this->strfiled_parentid` = 0
order by `$this->strfiled_id` desc limit 0 , 1 ;
$resresult = mysql_query ( &$strquery , $this->resdbc ) ;
while ( $arrrow = mysql_fetch_array ( $resresult ) )
{
$intlastedmainid = $arrrow[0] ;
}
$intlastedmainid = intval ( $intlastedmainid );
mysql_free_result ( $resresult ) ;
return $intlastedmainid + 1 ;
}
function get_level_lastest_id ( $intparentid )
{
mysql_select_db ( $this->strdatabase , $this->resdbc ) ;
$strquery = select `$this->strfiled_id`
from `$this->strmenutable`
where `$this->strfiled_parentid` = $intparentid
order by `$this->strfiled_id` desc limit 0 , 1 ;
$resresult = mysql_query ( &$strquery , $this->resdbc ) ;
while ( $arrrow = mysql_fetch_row ( $resresult ) )
{
$intlevellastestid = $arrrow[0] ;
}
mysql_free_result ( $resresult ) ;
return $intlevellastestid ;
}
function get_level_lastest_order ( $intparentid )
{
mysql_select_db ( $this->strdatabase , $this->resdbc ) ;
$strquery = select `$this->strfiled_order`
from `$this->strmenutable`
where `$this->strfiled_id` = $intparentid ;
$resresult = mysql_query ( &$strquery , $this->resdbc ) ;
while ( $arrrow = mysql_fetch_row ( $resresult ) )
{
$floselectitemorder = $arrrow[0] ;
}
mysql_free_result ( $resresult ) ;
$strquery = select `$this->strfiled_order`
from `$this->strmenutreetable`
where binary ( `tree`) like '%|$intparentid|%'
order by `$this->strfiled_order` desc limit 0 , 1 ;
//echo $strquery ;
$resresult = mysql_query ( &$strquery , $this->resdbc ) ;
while ( $arrrow = mysql_fetch_row ( $resresult ) )
{
$floselectitemlastestorder = $arrrow[0] ;
}
mysql_free_result ( $resresult ) ;
if ( ! $floselectitemlastestorder ) $floselectitemlastestorder = $floselectitemorder ;
return $floselectitemlastestorder ;
}
function get_elements ( $intparentid = 0 )
{
mysql_select_db ( $this->strdatabase , $this->resdbc ) ;
if ( $intparentid == 0 )
{
$intmainid = $this->get_new_mainid ( );
return array ( mainid => $intmainid , order => 0 , level => 0 ) ;
}
$strquery = select `$this->strfiled_mainid` , `$this->strfiled_order` , `$this->strfiled_level`
from `$this->strmenutable`
where `$this->strfiled_id` = $intparentid ;
$resresult = mysql_query ( &$strquery , $this->resdbc ) ;
while ( $arrrow = mysql_fetch_row ( $resresult ) )
{
$intmainid = $arrrow[0] ;
$floorder = $arrrow[1] ;
$intlevel = $arrrow[2] ;
}
mysql_free_result ( $resresult ) ;
if ( ! $intmainid ) return false ;
$intlevellastestid = $this->get_level_lastest_id ( $intparentid ) ;
// get pre order
if ( $intlevellastestid )
{
$flopreorder = $this->get_level_lastest_order ( $intlevellastestid );
// echo $flopreorder ;exit;
}
else
{
$flopreorder = $floorder ;
}
// get next order
$strquery = select `$this->strfiled_order`
from `$this->strmenutable`
where `$this->strfiled_mainid` = $intmainid and `$this->strfiled_order` > $flopreorder
order by `$this->strfiled_order` asc limit 0 , 1 ;
$resresult = mysql_query ( &$strquery , $this->resdbc ) ;
while ( $arrrow = mysql_fetch_row ( $resresult ) )
{
$flonextorder = $arrrow[0] ;
}
mysql_free_result ( $resresult ) ;
if ( ! $flonextorder )
{
$floneworder = floor ( $flopreorder + 1 ) ;
}
else
{
$floneworder = number_format ( ( $flopreorder + $flonextorder ) / 2 , 14 ) ;
}
$intnewlevel = $intlevel + 1 ;
return array ( mainid => $intmainid , order => $floneworder , level => $intnewlevel ) ;
}
function update_tree ( $intmainid , $intparentid , $floorder )
{
if ( !$intparentid ) return false ;
mysql_select_db ( $this->strdatabase , $this->resdbc ) ;
$strquery = select `tree`
from `$this->strmenutreetable`
where `mainid` = $intmainid and binary ( `tree`) like '%|$intparentid|'
order by `order` desc limit 0 , 1 ;
$resresult = mysql_query ( &$strquery , $this->resdbc ) ;
while ( $arrrow = mysql_fetch_row ( $resresult ) )
{
$strtree = $arrrow[0] ;
}
mysql_free_result ( $resresult ) ;
if ( ! $strtree )
{
$strquery = select `$this->strfiled_parentid`
from `$this->strmenutable`
where `$this->strfiled_id` = $intparentid ;
$resresult = mysql_query ( &$strquery , $this->resdbc ) ;
while ( $arrrow = mysql_fetch_row ( $resresult ) )
{
$intpreparentid = $arrrow[0] ;
}
mysql_free_result ( $resresult ) ;
if ( ! $intpreparentid )
{
$strpretree = '';
}
else
{
$strquery = select `tree`
from `$this->strmenutreetable`
where `mainid` = $intmainid and binary ( `tree`) like '%|$intpreparentid|'
order by `order` desc limit 0 , 1 ;
$resresult = mysql_query ( &$strquery , $this->resdbc ) ;
while ( $arrrow = mysql_fetch_row ( $resresult ) )
{
$strpretree = $arrrow[0] ;
}
mysql_free_result ( $resresult ) ;
}
$strnewtree = $strpretree . '|'. $intparentid . '|' ;
$strquery = insert into `$this->strmenutreetable`
values ( $intmainid, '$strnewtree', $floorder ) ;
$resresult = mysql_query ( &$strquery , $this->resdbc ) ;
@mysql_free_result ( $resresult ) ;
return true ;
}
else
{
$strquery = update `$this->strmenutreetable`
set `order` = $floorder
where `mainid` = $intmainid and `tree` = '$strtree' ;
$resresult = mysql_query ( &$strquery , $this->resdbc ) ;
@mysql_free_result ( $resresult ) ;
return true ;
}
}
}
}
/*
$pfreeroad = new freeroad ( $resdbc , $arrdatabase[dbname] , 'menus' , 'menu_tree' ) ;
$info = 'change here';
$intparentid = change here ;
$arritems = $pfreeroad->get_elements( $intparentid ) ;
$intmainid = $arritems['mainid'] ;
$floorder = $arritems['order'] ;
$intlevel = $arritems['level'] ;
$strquery = insert into `menus` values ( '' , $intmainid , $intparentid , $floorder , $intlevel, '$info' ) ;
$resresult = mysql_query ( &$strquery , $resdbc ) ;
$pfreeroad->update_tree ( $intmainid , $intparentid , $floorder ) ;
@mysql_close( $resdbc ) ;
*/
?>
1 )
{
$strspace .= '--';
}
echo $strspace . $arrrows[id] . $arrrows[info] .
;
}
if ( $_get[action] == 'add' )
{
$pfreeroad = new freeroad ( $resdbc , $arrdatabase[dbname] , 'menus' , 'menu_tree' ) ;
$info = 'f1';
$intparentid = 1 ;
$arritems = $pfreeroad->get_elements( $intparentid ) ;
$intmainid = $arritems['mainid'] ;
$floorder = $arritems['order'] ;
$intlevel = $arritems['level'] ;
$strquery = insert into `menus` values ( '' , $intmainid , $intparentid , $floorder , $intlevel, '$info' ) ;
$resresult = mysql_query ( &$strquery , $resdbc ) ;
$pfreeroad->update_tree ( $intmainid , $intparentid , $floorder ) ;
@mysql_close( $resdbc ) ;
}
?>
容易可以看出，输出的时候是如此简单便实现树结构了:
select * from `menus` order by `mainid` asc, `order` asc ;
前文输出写成输入了~~~ 晕倒。。
输出的时候，根据level来做树结构。