父子ID法无限分类的简单实现算法

1、引言
无限分类在很多应用中是会经常用到的，比如CMS的文章分类表，工厂生产的BOM物料，在线商店Products产品分类表，等等。
很多初学者对无限分类的算法还是不能深刻的理解，七月十五在这里献丑，为大家初略的讲述一下无限分类表的基本算法。
关键词： 无限分类, 族谱, 递归, SQL

2、数据结构（族谱）
我们以一个家族的族谱来构建一个无限分类。其数据结构如下。 可以看到我们只需要设计一个ID跟一个PARENT(来自其内部ID)，就可以构建出整个族谱之间的联系。
比如：
1)、已知任一ID，可以求得祖先族系树
如已知 ID=11（外孙）, 很容易就跟据ID跟PARENT的关系查得祖先树(含自身)如下： 2)、已知任一ID，可以求其后代(含自己)列表
比如已知ID=4（自己），跟据ID和PARENT关系可以查得后代如下： 3、SQL
根据以上的数据结构我们创建一个MySQL<span href="tag.php?name=%CA%FD%BE%DD%BF%E2" class="t_tag">数据库</span> 4、算法
其余的与无限分类无关的算法，我这里就不演示了。与无限分类有关的算法有两个。
其一、祖先树。（我们以一维数组来取得所有列的详细数据）
其二、后代表。（因为涉及到实际应用的关联操作，我们这里给出求出一组指定id的所有后代id集合的一维数组的方法）
1)、祖先树
以指定的id求得其父母辈的id，如果存在，则再以求得id求父母辈的id，直到求不到其父母辈的id为止，返回一个二维数组。
2)、后代ID表
以指定的id求得其子女的id,如果存在，则再以求得的id来求子女id，直到求不到其子女id为止，返回一个含有所有求得id的一维数组。

5、代码
[php]
<?php
/**
* 族谱
*
* 以一个实例演示简单无限分类的算法
*
* @copyrihgt HentStudio, 2008
* @author 七月十五 <[email protected]>
* @version $Id: family.php, v 0.0.1 2008/09/23 16:07:25 uw Exp $
*/

/**
* 获取祖先树二维数组，长幼逆序，不含己身
* @param int $id 己身所在id
* @return array
*/
function _getForefathers($id) {
    $data = array();
    $sql = "
        SELECT *
        FROM family
        WHERE id = (
            SELECT parent
            FROM family
            WHERE id = '" . $id ."')
        ;";
    $re = <span href="tag.php?name=mysql" class="t_tag">mysql</span>_query($sql);
    if(mysql_num_rows($re)) {   /* 如果存在有祖先 */
        $data[] = $rs = mysql_fetch_assoc($re);
        $data = array_merge($data, _getForefathers($rs['id'])); /* 递归查询 */
        return $data;
    } else {
        return $data;
    }
}

/**
* 获取祖先树二维数组，长幼顺序，含己身
* @param int $id 己身所在id
* @return array
*/
function getForefathers($id) {
    return array_reverse(array_merge(array(mysql_fetch_assoc(mysql_query("SELECT * FROM family WHERE id = '" . $id . "'; "))), _getForefathers($id)));
}

/**
* 获取指定id的所有后代，不含指定id
* @param mixed $id 指定id, 有可能是array
* @return array 所有后代id的一维数组
*/
function _getOffspring($id) {
    $data = array();
    $ids = array();
    if(!is_array($id)) { $id = array($id); }
    $id = implode(', ', $id);
    $sql = "
        SELECT *
               FROM family
               WHERE parent IN (" . $id . ") ;";
    $re = mysql_query($sql);
    if(mysql_num_rows($re)) {
        while($rs = mysql_fetch_assoc($re)) {
                   $ids[] = $rs['id'];
               }
               $ids = array_merge($ids, _getOffspring($ids));
               return $ids;
    } else {
        return $ids;
    }
}

/**
* 获得指定id的所有后代，含指定id
* @param mixed $id 指定id, 有可能是array
* @return array 所有后代的和指定id的一维数组
*/
function getOffspring($id) {
    if(!is_array($id)) { $id = array($id); }
    return array_merge($id, _getOffspring($id));
}


/* 主程序 */
ini_set('default_charset', 'utf-8');    /* 设定HTML输出编码为utf-8 */
mysql_connect('localhost', 'root', ''); /* 连接MySQL */
mysql_select_db('family');              /* 打开family数据库 */
mysql_query("SET NAMES 'utf8'");        /* 设定数据库输出编码 */

echo '<pre>';
var_dump(getForefathers(11));           /* 输出ID=11的祖先树 */
var_dump(getOffspring(array(3, 4)));     /* 输出ID=3及ID=4的后代ID表 */
echo '</pre>';
[/php]

6、附件
family.zip (1.73 KB)

7、结语
当然以上只实现了无限分类的基本算法，对于无限分类的数据结构的分析还有很多的版本，不同的版本实现也是不一样的。
我这里只给出var_dump的内容，具体到应用里如何使用，相信大家都能掌握。实用代码我就不画蛇添足了。帖图两张以飨读者。
如果无限分类能在SQL层面求得结果的话那是最好的，比如以一句或若干句SQL求得，或以SQL的存储过程求得。七月十五才疏学浅，目前只能从外部程序（PHP）层面实现了无限分类的上述功能。如果大家有更好的解决方法，欢迎指教，谢谢。

• 祖先导航树
  
  下载 (24.92 KB)
  

  2008-9-23 17:03
• 删除指定的IDs及其所有后代
  
  下载 (29.57 KB)
  

  2008-9-23 17:03

[以上两图来自LeoPHP的example的RBAC]

8、补充
一直想利用一句SQL来求解，以SQL递归可以实现。
现公布第二个问题的SQL递归不完善的求解方法（不含己身）
但这个SQL还不能实现任意深度的查询。 第一个问题的SQL就留给大家思考写出来吧。

[本文为七月十五原创，转载请注明出自PHPChina]

知道原理 但是怎么显示树形菜单  原理是什么？

循环查询我是强烈反对的

少量数据时未为不可，看应用需要
PHP对递归的支持的确是有些诟病，据说用了栈，数据量大时有溢出的危险

数据量大的时候用左右值最好

左右值也是无限分类的一种算法。
但是恰好相反，在分类数据量大的时候不推荐。
算法也比较麻烦，添加和编辑一个分类时会涉及到很多分类的改动。
适合数据量小且不经常改动的无限分类。


其实分类一般数据量不会很大，算法和思路简明者取胜，个人比较倾向于“ID，父ID 递归”来解决无限分类问题。

左右值无限分类算不请参阅： http://bbs.phpchina.com/viewthread.php?tid=46175

[ 本帖最后由 七月十五 于 2008-9-24 22:05 编辑 ]

呵呵，空间换时间，如果数据量不大，直接将全部数据都读到一个数组里面，然后再处理会更好。你还可以在表里面加一些冗余字段以提高速度和减少读取的数据量。

那么递归的数量限制到底是多少？
多大的数量递归会导致溢出或效率低下？
没人给出具体数据，我也没见到有关的测试文献。
我想无限分类这么一点数据量还不足以把PHP递归给撑死了。
其实PHP递归完全可以加以控制很好的运用。
如果因一点点的不足而不用递归，岂非因噎废食！

[ 本帖最后由 七月十五 于 2008-9-24 22:33 编辑 ]

呵呵，你的无限分类绝对不会将PHP递归撑死。因为数据库会在递归死掉之前崩溃。

愿闻其详，敬请指教。

呵呵，假设PHP的递归能支持到1000万层，你的无限分类算法能支持500万次数据库查询么？
所以我认为你的无限分类算法会在递归溢出之前先让数据库崩溃。当然小数据量是不会导致php的递归溢出的，因此我说的情况出现只是理论上的。在应用上通过限制数据量可以避免这个问题，但既然是限制了数据量那么就是有限分类算法了。
如果你将数据表的数据控制在1000行内，按照你的算法最坏的情况恐怕一次搜索要执行1000次数据库查询。而如果你将这1000行的数据一次读取出来，保存在数组里面，然后再搜索数组，效率是不是会提高很多呢？况且分类大多时候检索的多，更新的少，你还可以将数据缓存起来那效率就更高了。

这里有一个和你差不多的算法，看看大家的评论吧
http://bbs.phpchina.com/viewthre ... p;extra=&page=5

1、代码比较散乱，思路还算清晰。
2、没有进行函数封装或类封装来返回数据，而是直接输出。
3、混杂HTML和PHP，不适合用在MVC的应用中。
4、都是ID，父ID算法的无限分类，用到递归，效率应该也不会差很远。
5、大数量级的无限分类在实际应用中毕竟很少。
6、可以在SQL的层面上做文章，比如ORACLE就直接一句SQL搞定无限分类递归查询。还可以用MySQL的存储过程来算出祖先及后代。

要考虑到一个页面多人访问的情况下，查询次数会累加的。尽可能减少数据库查询压力是PHP优化中很重要的原则。

存储过程和不断查表没什么两样

这种方法很容易为新手所采用，在数据量并不大的情况下它可以解决问题。
一旦使用到递归，就应该考虑到溢出的可能性。
LZ可以把这种方法结合缓存使用，毕竟在实际应用中，分类一般也只有几层。或者，将数据取出来，使用数组方法处理。

不过，
在以由父到子类的实际应用中(只取子类，这种应用是实际中最常见的)，这种方法是可行的。直接查询当前分类的子类即可，只需要一次查询。
所以，LZ这种方法同样具有十分好的应用价值。

所以一开始我是想最好能从SQL层面上求解的，用一句SQL或存储过程来优化求解。一来可以免除PHP递归的不良支持，二来可以在SQL层面最优化查询。但MySQL似乎不能一句搞定。
您所说的无限分类意味着无限数据（海量），这个观点不敢赞同，无限分类是相对于固定级分类（如二级、三级）来说，所以无限分类应该理解为“不固定分类级深度的动态分类”，用到10级深度分类以上及有1000多个分类的应用，应该非常罕见了；用到100级深度及10000多个分类的应用，基本上算是绝迹。而PHP及MySQL在这个数据级上应该游刃有余，轻松应付。

在数据量不是非常大的情况下，这种无限分类的算法还算实用。
当然把所有分类一次性读出后再以数组的方式来解决，也许是更好的方法。
1、数据库压力减轻，免除频繁查询数据库。
2、更好的模块化，函数或方法里不再出现数据库相关操作。传入的参数是一个二维数组（引用&）。
3、分类数据量很大时，比较消耗资源。
4、因为一开始即读取被缓存的缘故，得到的分类数据可能不是即时的，对数据库的操作可能有冲突或过期的风险。

对于getElder取父辈（叔伯）分类和getChildren取子分类，因为比较简单我没有帖出来。在后面的两个图上有体现。另外对于分类的操作（增加，读取，更新，删除，合并，移动），五个方法getElder（取父辈），getChildren（取子类），getOffspring（取后代），getForefather（祖先树），getSelf（取自身） 结合可以轻松搞定。

[ 本帖最后由 七月十五 于 2008-9-25 10:11 编辑 ]

[php]
//我写的下拉列表栏目显示
function treelm(&$row,$id,$repeat){
    $pre = str_repeat('  ',$repeat);
    $pre .= $repeat > 0 ? '|-' : '';
    foreach($row as $val){
        if( $val['parent'] == $id ){
            $tmpstr .= "<option value = '{$val['id']}'>{$pre}{$val['title']}</option>\r\n";
            $tmpstr .= treelm($row,$val['id'],$repeat+1);
        }
    }
    return $tmpstr;
}
[/php]

[ 本帖最后由 七月十五 于 2008-9-25 10:12 编辑 ]

不要担心，这种方法即使是用在淘宝一类的商品分类上都没问题
只要是一级一级浏览的，这种设计是可行的。

一级一级的浏览用 getChildren 即可搞定，一句SQL。
用在后台里需要用到列出全部后代。
比如“奶制品”下面有“奶粉”、“液态奶”、“奶糖”三个大类，还有N多小类。
因为“三聚氰胺”需在禁止奶制品上架，只要对“奶制品” getOffspring 一下，然后locked掉，就全部OK了:sweat:

楼主的分类算法里面没有设置级别控制的。。。如果从淘宝商品分类的最顶级其搜索后代，按照楼主的的代码恐怕会将全部商品分类都搜索出来。只怕就是数据库撑着住也会变得很缓慢。
假如楼主觉得这种分类方法简单好用，我建议不妨在数据表中添加一个level字段或者在函数里面传入一个level参数，这样可以控制你想检索的级别。比如你想检索从祖父到你自己这一辈中的所有亲人，按照你目前的算法怕是不好实现

如果要检索中间的2级怎么办呢？

UNIQUE KEY (parent, name)          tukiz33

作用于后辈树的时候
这种作用一般有两种：
一种是前台的查询，比如“体育用品”这一分类的产品列表，该列表则将"体育用品"下面所有后辈树分类下的产品都列出来。这时候如果是SQL解决的话？你需要考虑到这一个问题，缓存或其他测度过有效的方式都是解决办法，这时候应该避免用递归。
另一种是后台的分类操作，其实跟前面基本是一个问题，但事实上缓存本身的产生一般来说是由后台操作完成的，这时候用递归是难免的了。那就要设计好递归，最大限度地减轻数据库负担。
做到只于后台递归，前台不用。

当然，实际应用中还会碰到很多的问题，所以这种设计你把它定位在雏形阶段（也就是当成只是保存分类与分类关系）就好了。

没错，看我楼上的分析。
当要列表或搜索后代的时候，千万避免直接递归，应在中间作过滤处理(至少一次从缓存中取得相应的分类ID)

事实上对分类本身并无太大问题
问题的关键在于分类下的数据


在实际应用中应该有两大问题：1 取后辈分类树   2 取当前及后辈分类下的(产品)数据
而问题2的解决是需要先解决问题1的。

千万不要脱离问题2的考虑

对于无限分类的算法的确要很好的构思，所以我在标题上有所说明“简单无限分类的实现算法”，如果应用做得像淘宝或拍拍那么大，对于无限分类的算法要考虑的东西很多。

此帖本是砖头，引出很多玉来，谢谢大家点评。一次性读出数组缓存后处理不失为一个好方法。继续讨论，看看还有什么更好的解决方案。

---------------------------------------------------------
。如果从淘宝商品分类的最顶级其搜索后代
--------------------------------------------------------
这个才是真正应该讨论的!:biggrin:

还有一个问题，如何有效得取出直系祖先树。

现在把关键技术问题总结一下：
1、已知ID（多个ID？），如何求得后代分类树？及如何显示成树状？
2、已知ID（多个ID？），如何求得后代下所有产品？及如何排序、分页？
3、已知ID，如何求得直系祖先树？（用于导航）