无限分类与树型论坛的实现方法
――浮点型字段排序法
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的最小整数就行了。
主要实现方法便如上面说的。
处理方法
<?php /* * ID: class FreeRoad * Author: Joe Teng <Joe_Teng@hotmail.com> * Notice: Infinite category maker. */ $arrDatabase = array ( "host" => '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 ) ; */ ?>
<?php include "freeroad.class.php"; $strQuery = " SELECT * FROM `menus` ORDER BY `mainid` ASC , `order` ASC "; $resResult = mysql_query ( &$strQuery , $resDbc ) ; while ( $arrRows = mysql_fetch_array ( $resResult )) { $intLevel = $arrRows["level"] ; $strSpace = '' ; for ( $i = 0 ; $i <= $intLevel ; $i++ ) { $strSpace .= " "; } if ( $i>1 ) { $strSpace .= '--'; } echo $strSpace . $arrRows["id"] . $arrRows["info"] ."<br>"; } 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 ) ; } ?>