php无限级分类 - 无限级数据排序

之前一直用classcode来组建栏目,因为数据库访问量小,算法简单,而且容易理解,很适合简单的栏目列表结构。

如今要做栏目列表相对复杂,免不了采用pid递归的方法,找到以下方法,第三种算法实属巧妙,学习之。

转自:http://www.luocheng.cn/article-view-235.html

我们经常遇到这样的问题,读取无限级分类数据,通常运用在地区、类别、商品类目等。
通常数据库设计如下:

id name   pid
1  北京   0
2  重庆   0
3  北部新区 2
4  江北区  2
pid记录了上级ID(父ID)

初级方法:

最简单的思路或者说常规的思路就是递归算法了。递归算法是比较快的和准确的,但是有一个问题就是会比较浪费不必要的资源,递归算法执行的过程中会开启N个函数入口,也就是函数需要一直保存状态等待起递归的运算结果。例如这个树形有5层*60行,则在递归算法中浪费的运算至少60次,并且保持5个函数一直是运算中状态,不合理的是同样要做60+次的数据库查询,因为不管其有没有子类,算法执行过程中都需要去重复执行递归运算,事实上实际执行过程中不止这个数。

可以写个简单的例子来测试递归算法调用函数的次数。

$db = new MysqlDb();
$num = 0;
function treeArray($pid) {
 global $db, $num;
 $num++;
 $data = $db -> getAll("SELECT * FROM geo WHERE pid = ".$pid); //返回一个二维数组
 $result = array();
 foreach($data as $val) {
  $val['child'] = treeArray($val['id']);
  $result[] = $val;
 }
 return $result;
}
print_r(treeArray(0)); //树形的结果
var_dump($num);

中级方法:

然后我们系统越作越大了,数据库资源紧张了,我们要求在不改变数据库结构的同时尽可能的减少数据库的操作。那么这样做就需要我们有一算法来给你的数据排序了。

$num = 0;
  
function treeArray() {
 global $num, $db;
 $data = $db -> getALl("SELECT * FROM geo");
 $result = array();
 foreach($data as $val) {
  $num++;
  if($val['pid'] == 0) {
   $val['child'] = getChild($val['id'], $data);
   $result[] = $val;
  }
 }
 return $result;
}
function getChild($pid, $data) {
 global $num;
 $result = array();
 foreach($data as $val) {
  $num++;
  if($val['pid'] == $pid) {
   $val['child'] = getChild($val['id'], $data);
   $result[] = $val;
  }
 }
 return $result;
} 
print_r(treeArray());
var_dump($num);

高级方法:

好了,我们最起码实现了不用多次请求数据库了,不过在作数组遍历的时候我们做了很多次运算,然后我们的系统功能模块越来越多,其中树形结构数据这一块的调用也特别多,程序执行速度越来越不进人意了。我们则需要设计一个速度更快,消耗资源更少的算法。这里我用了php里的变量引用,其它语言里肯定也有这种引用方式,有些类似于C语言的指针。

function treeArray() {
  
 global $db;
 $data = $db -> getAll("SELECT * FROM geo");
 $result = array();
 //定义索引数组,用于记录节点在目标数组的位置 
 $I = array();
 foreach($data as $val) {
  if($val['pid'] == 0) {
   $i = count($result);
   $result[$i] = $val;
   $I[$val['id']] = & $result[$i];
  } else {
   $i = count($I[$val['pid']]['child']);
   $I[$val['pid']]['child'][$i] = $val;
   $I[$val['id']] = & $I[$val['pid']]['child'][$i];
  }
 }
 return $result;
}
print_r(treeArray());
若您觉得我的博文对您有帮助,欢迎点击下方按钮对我打赏
打赏