跳至正文

无限极分类的多种实现方式

递归

从数据库中查询出所有数据,然后递归处理

$category = [[
    'id' => 1,
    'pid' => 0,
    'name' => '1级分类',
], [
    'id' => 2,
    'pid' => 1,
    'name' => '2级分类',
], [
    'id' => 3,
    'pid' => 2,
    'name' => '3级分类',
], [
    'id' => 4,
    'pid' => 3,
    'name' => '4级分类',
], [
    'id' => 5,
    'pid' => 4,
    'name' => '5级分类'
], [
    'id' => 6,
    'pid' => 6,
    'name' => '6级分类'
]];

//递归成树形
function recurSionToTree(array $array = [], $pid = 0)
{
    $result = [];

    foreach ($array as $key => $value) {

        if ($value['pid'] == $pid) {
            $children = recurSionToTree($array, $value['id']);

            if ($children) {
                $value['children'] = $children;
            }

            $result[] = $value;
        }
    }

    return $result;
}

引用

从数据库查询出所有数据,然后遍历

function refToTree($data)
{
    $items = array();

    foreach ($data as $v) {
        $items[$v['id']] = $v;
    }

    $tree = array();

    foreach ($items as $k => $item) {
        if (isset($items[$item['pid']])) {
            $items[$item['pid']]['children'][] = &$items[$k];
        } else {
            $tree[] = &$items[$k];
        }
    }

    return $tree;
}

冗余字段,空间换时间

参考连接:https://learnku.com/courses/ecommerce-advance/7.x/database-structure/9086

在开始之前,我们需要先整理好 categories 表的字段名称和类型:

字段名称描述类型加索引缘由
id自增长 IDunsigned big int主键
name类目名称varchar
parent_id父类目 IDunsigned big int, null外键
is_directory是否拥有子类目tinyint
level当前类目层级unsigned int
path该类目所有父类目 idvarchar

这里我们需要解释一下 path 字段的意义,在无限级分类的实现中我们经常会遇到以下几个场景:

  • 场景一:查询一个类目的所有祖先类目,需要递归地去逐级查询父类目,会产生较多的 SQL 查询,从而影响性能。
  • 场景二:查询一个类目的所有后代类目,同样需要递归地逐级查询子类目,同样会产生很多 SQL 查询。
  • 场景三:判断两个类目是否有祖孙关系,需要从层级低的类目逐级往上查,性能低下。

而 path 字段就是用于解决这些问题而存在的,path 字段会保存该类目所有祖先类目的 ID,并用字符 - 将这些 ID 分隔开,根类目的 path 字段为 -。比如如下类目:

[
    [
        "id" => 1,
        "name" => "手机配件",
        "parent_id" => null,
        "level" => 0,
        "path" => "-"
    ],
    [
        "id" => 2,
        "name" => "耳机",
        "parent_id" => 1,
        "level" => 1,
        "path" => "-1-"
    ],
    [
        "id" => 3,
        "name" => "蓝牙耳机",
        "parent_id" => 2,
        "level" => 2,
        "path" => "-1-2-"
    ],
    [
        "id" => 4,
        "name" => "移动电源",
        "parent_id" => 1,
        "level" => 1,
        "path" => "-1-"
    ],
];

对应的类目树如下:

手机配件(1)
 ├─ 耳机(2)
 │   └─ 蓝牙耳机(3)
 └─ 移动电源(4)

现在我们再来逐一分析刚刚的几个场景:

场景一,查询『蓝牙耳机』的所有祖先类目:取出 path 字段的值 -1-2-,以 - 为分隔符分割字符串并过滤掉空值,得到数组 [1, 2] ,然后使用 Category::whereIn('id', [1, 2])->orderBy('level')->get() 即可获得排好序的所有父类目。

场景二,查询『手机配件』的所有后代类目:取出自己的 path 值 -,然后追加上自己的 ID 字段得到 -1-,然后使用 Category::where('path', 'like', '-1-%')->get() 即可获得所有后代类目。

场景三,判断『移动电源』与『蓝牙耳机』是否有祖孙关系:取出两者中 level 值较大的类目『蓝牙耳机』的 path 值 -1-2- 并赋值给变量 $highLevelPath,取另外一个类目的 path 值并追加该类目的 ID 得 -1-4- 并赋值给变量 $lowLevelPath,然后只需要判断变量 $highLevelPath 是否以 $lowLevelPath 开头,如果是则有祖孙关系。

可以看到我们通过新增一个冗余的 path 字段,就能很好地解决性能问题,这是一种很典型的(存储)空间换(执行)时间策略。

预排序树

参考连接

https://www.jianshu.com/p/48f6db8ea524

https://www.cnblogs.com/sonicit/archive/2013/05/21/3090518.html