无限分类在很多应用中是会经常用到的，比如CMS的文章分类表，工厂生产的BOM物料，在线商店Products产品分类表，等等。
很多初学者对无限分类的算法还是不能深刻的理解，七月十五在这里献丑，为大家初略的讲述一下无限分类表的基本算法。
关键词： 无限分类, 族谱, 递归, SQL
2、数据结构（族谱）
我们以一个家族的族谱来构建一个无限分类。其数据结构如下。
CODE:
+---------------------------+
| ID | PARENT | NAME |
+----+--------+-------------+
| 1 | 0 | 祖父 |
+----+--------+-------------+
| 2 | 1 | 父亲 |
+----+--------+-------------+
| 3 | 1 | 叔伯 |
+----+--------+-------------+
| 4 | 2 | 自己 |
+----+--------+-------------+
| 5 | 4 | 儿子 |
+----+--------+-------------+
| 6 | 5 | 孙子 |
+----+--------+-------------+
| 7 | 2 | 姐妹 |
+----+--------+-------------+
| 8 | 3 | 表亲 |
+----+--------+-------------+
| 9 | 7 | 甥儿 |
+----+--------+-------------+
| 10 | 4 | 女儿 |
+----+--------+-------------+
| 11 | 10 | 外孙 |
+----+--------+-------------+
| 12 | 5 | 孙女 |
+----+--------+-------------+
| .. | ... | .... |
+---------------------------+可以看到我们只需要设计一个ID跟一个PARENT(来自其内部ID)，就可以构建出整个族谱之间的联系。比如：
1)、已知任一ID，可以求得祖先族系树
如已知 ID=11（外孙）, 很容易就跟据ID跟PARENT的关系查得祖先树(含自身)如下：
CODE:
array(
array(11, 10, 外孙),
array(10, 4, 女儿),
array(4, 2, 自己),
array(2, 1, 父亲)
array(1, 0, 祖父)
)2)、已知任一ID，可以求其后代(含自己)列表比如已知ID=4（自己），跟据ID和PARENT关系可以查得后代如下：
CODE:
array(
array(4, 2, 自己),
array(5, 4, 儿子),
array(6, 5, 孙子),
array(12, 5, 孙女),
array(10, 4, 女儿),
array(11, 10, 外孙)
)3、SQL根据以上的数据结构我们创建一个MySQL数据库
CODE:
CREATE DATABASE family DEFAULT CHARSET 'utf8';
USE family;
CREATE TABLE family (
id INT(10) UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
parent INT(10) UNSIGNED NOT NULL DEFAULT '0',
name CHAR(30) NOT NULL DEFAULT '',
UNIQUE KEY (parent, name)
);
INSERT INTO family (id, parent, name )
VALUES
( 1, 0, '祖父'),
( 2, 1, '父亲'),
( 3, 1, '叔伯'),
( 4, 2, '自己'),
( 5, 4, '儿子'),
( 6, 5, '孙子'),
( 7, 2, '姐妹'),
( 8, 3, '表亲'),
( 9, 7, '甥儿'),
( 10, 4, '女儿'),
( 11, 10, '外孙'),
( 12, 5, '孙女');4、算法其余的与无限分类无关的算法，我这里就不演示了。与无限分类有关的算法有两个。
其一、祖先树。（我们以一维数组来取得所有列的详细数据）
其二、后代表。（因为涉及到实际应用的关联操作，我们这里给出求出一组指定id的所有后代id集合的一维数组的方法）
1)、祖先树
以指定的id求得其父母辈的id，如果存在，则再以求得id求父母辈的id，直到求不到其父母辈的id为止，返回一个二维数组。
2)、后代ID表
以指定的id求得其子女的id,如果存在，则再以求得的id来求子女id，直到求不到其子女id为止，返回一个含有所有求得id的一维数组。
5、代码
6、附件
family.zip
(2008-09-23 17:03:16, Size: 1.73 KB, Downloads: 148)
7、结语
当然以上只实现了无限分类的基本算法，对于无限分类的数据结构的分析还有很多的版本，不同的版本实现也是不一样的。
我这里只给出var_dump的内容，具体到应用里如何使用，相信大家都能掌握。实用代码我就不画蛇添足了。帖图两张以飨读者。
如果无限分类能在SQL层面求得结果的话那是最好的，比如以一句或若干句SQL求得，或以SQL的存储过程求得。七月十五才疏学浅，目前只能从外部程序（PHP）层面实现了无限分类的上述功能。如果大家有更好的解决方法，欢迎指教，谢谢。
[以上两图来自LeoPHP的example的RBAC]
8、补充
一直想利用一句SQL来求解，以SQL递归可以实现。
现公布第二个问题的SQL递归求解方法（不含己身）
CODE:
SELECT p2 . *
FROM family AS p1, family AS p2
WHERE p1.id = p2.parent
AND (
p1.id = 4
OR p1.parent = 4
)第一个问题的SQL就留给大家思考写出来吧。[本文为七月十五原创，转载请注明出自PHPChina]
最新回复
QUOTE:
少量数据时未为不可，看应用需要PHP对递归的支持的确是有些诟病，据说用了栈，数据量大时有溢出的危险
QUOTE:
左右值也是无限分类的一种算法。但是恰好相反，在分类数据量大的时候不推荐。
算法也比较麻烦，添加和编辑一个分类时会涉及到很多分类的改动。
适合数据量小且不经常改动的无限分类。
QUOTE:
其实分类一般数据量不会很大，算法和思路简明者取胜，个人比较倾向于“ID，父ID 递归”来解决无限分类问题。左右值无限分类算不请参阅： http://bbs.phpchina.com/viewthread.php?tid=46175
[ 本帖最后由 七月十五 于 2008-9-24 22:05 编辑 ]
QUOTE:
那么递归的数量限制到底是多少？多大的数量递归会导致溢出或效率低下？
没人给出具体数据，我也没见到有关的测试文献。
我想无限分类这么一点数据量还不足以把PHP递归给撑死了。
其实PHP递归完全可以加以控制很好的运用。
如果因一点点的不足而不用递归，岂非因噎废食！
[ 本帖最后由 七月十五 于 2008-9-24 22:33 编辑 ]
QUOTE:
愿闻其详，敬请指教。QUOTE:
呵呵，假设PHP的递归能支持到1000万层，你的无限分类算法能支持500万次数据库查询么？所以我认为你的无限分类算法会在递归溢出之前先让数据库崩溃。当然小数据量是不会导致php的递归溢出的，因此我说的情况出现只是理论上的。在应用上通过限制数据量可以避免这个问题，但既然是限制了数据量那么就是有限分类算法了。
如果你将数据表的数据控制在1000行内，按照你的算法最坏的情况恐怕一次搜索要执行1000次数据库查询。而如果你将这1000行的数据一次读取出来，保存在数组里面，然后再搜索数组，效率是不是会提高很多呢？况且分类大多时候检索的多，更新的少，你还可以将数据缓存起来那效率就更高了。
http://bbs.phpchina.com/viewthre ... p;extra=&page=5
QUOTE:
1、代码比较散乱，思路还算清晰。2、没有进行函数封装或类封装来返回数据，而是直接输出。
3、混杂HTML和PHP，不适合用在MVC的应用中。
4、都是ID，父ID算法的无限分类，用到递归，效率应该也不会差很远。
5、大数量级的无限分类在实际应用中毕竟很少。
6、可以在SQL的层面上做文章，比如ORACLE就直接一句SQL搞定无限分类递归查询。还可以用MySQL的存储过程来算出祖先及后代。
QUOTE:
要考虑到一个页面多人访问的情况下，查询次数会累加的。尽可能减少数据库查询压力是PHP优化中很重要的原则。一旦使用到递归，就应该考虑到溢出的可能性。
LZ可以把这种方法结合缓存使用，毕竟在实际应用中，分类一般也只有几层。或者，将数据取出来，使用数组方法处理。
不过，
在以由父到子类的实际应用中(只取子类，这种应用是实际中最常见的)，这种方法是可行的。直接查询当前分类的子类即可，只需要一次查询。
所以，LZ这种方法同样具有十分好的应用价值。
QUOTE:
所以一开始我是想最好能从SQL层面上求解的，用一句SQL或存储过程来优化求解。一来可以免除PHP递归的不良支持，二来可以在SQL层面最优化查询。但MySQL似乎不能一句搞定。您所说的无限分类意味着无限数据（海量），这个观点不敢赞同，无限分类是相对于固定级分类（如二级、三级）来说，所以无限分类应该理解为“不固定分类级深度的动态分类”，用到10级深度分类以上及有1000多个分类的应用，应该非常罕见了；用到100级深度及10000多个分类的应用，基本上算是绝迹。而PHP及MySQL在这个数据级上应该游刃有余，轻松应付。
QUOTE:
在数据量不是非常大的情况下，这种无限分类的算法还算实用。当然把所有分类一次性读出后再以数组的方式来解决，也许是更好的方法。
1、数据库压力减轻，免除频繁查询数据库。
2、更好的模块化，函数或方法里不再出现数据库相关操作。传入的参数是一个二维数组（引用&）。
3、分类数据量很大时，比较消耗资源。
4、因为一开始即读取被缓存的缘故，得到的分类数据可能不是即时的，对数据库的操作可能有冲突或过期的风险。
对于getElder取父辈（叔伯）分类和getChildren取子分类，因为比较简单我没有帖出来。在后面的两个图上有体现。另外对于分类的操作（增加，读取，更新，删除，合并，移动），五个方法getElder（取父辈），getChildren（取子类），getOffspring（取后代），getForefather（祖先树），getSelf（取自身） 结合可以轻松搞定。
[ 本帖最后由 七月十五 于 2008-9-25 10:11 编辑 ]
[ 本帖最后由 七月十五 于 2008-9-25 10:12 编辑 ]
只要是一级一级浏览的，这种设计是可行的。
QUOTE:
一级一级的浏览用 getChildren 即可搞定，一句SQL。用在后台里需要用到列出全部后代。
比如“奶制品”下面有“奶粉”、“液态奶”、“奶糖”三个大类，还有N多小类。
因为“三聚氰胺”需在禁止奶制品上架，只要对“奶制品” getOffspring 一下，然后locked掉，就全部OK了