Category Tree

backend

A Category Tree consists of one or more root categories, each of which can have subcategories under it. Standard Responses are nodes under categories or subcategories in the Category Tree.

前言

    树形结构的数据在很多开发场合中都有用到，例如：权限树，分类树，省市区树形结构展示，有必要在这里做一下归纳总结，主要有2种方式。


分类表sql及数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
CREATE TABLE `category` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT COMMENT '主键',
  `parent_id` bigint(20) NOT NULL DEFAULT '0' COMMENT '父级id',
  `name` varchar(64) NOT NULL COMMENT '分类名称',
  `description` varchar(255) DEFAULT NULL COMMENT '分类描述',
  `level` tinyint(2) DEFAULT '1' COMMENT '分类等级',
  `delete_state` tinyint(1) DEFAULT '0' COMMENT '是否删除：0-否，1-是',
  `created` datetime NOT NULL COMMENT '创建时间',
  `updated` datetime NOT NULL COMMENT '更新时间',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=9 DEFAULT CHARSET=utf8 COMMENT='分类表';

insert into `category` (`id`, `parent_id`, `name`, `description`, `level`, `delete_state`, `created`, `updated`) values('1','0','英超','英超','1','0','2020-08-01 21:25:20','2020-08-01 21:25:22');
insert into `category` (`id`, `parent_id`, `name`, `description`, `level`, `delete_state`, `created`, `updated`) values('2','1','利物浦','利物浦','2','0','2020-08-01 21:25:43','2020-08-01 21:25:45');
insert into `category` (`id`, `parent_id`, `name`, `description`, `level`, `delete_state`, `created`, `updated`) values('3','1','切尔西','切尔西','2','0','2020-08-01 21:26:06','2020-08-01 21:26:08');
insert into `category` (`id`, `parent_id`, `name`, `description`, `level`, `delete_state`, `created`, `updated`) values('4','2','利物浦青年队','利物浦青年队','3','0','2020-08-01 21:26:32','2020-08-01 21:26:34');
insert into `category` (`id`, `parent_id`, `name`, `description`, `level`, `delete_state`, `created`, `updated`) values('5','3','切尔西青年队','切尔西青年队','3','0','2020-08-01 21:26:59','2020-08-01 21:27:01');
insert into `category` (`id`, `parent_id`, `name`, `description`, `level`, `delete_state`, `created`, `updated`) values('6','0','德甲','德甲','1','0','2020-08-01 21:27:17','2020-08-01 21:27:19');
insert into `category` (`id`, `parent_id`, `name`, `description`, `level`, `delete_state`, `created`, `updated`) values('7','6','拜仁','拜仁','2','0','2020-08-01 21:27:34','2020-08-01 21:27:37');
insert into `category` (`id`, `parent_id`, `name`, `description`, `level`, `delete_state`, `created`, `updated`) values('8','6','多特','多特','2','0','2020-08-01 21:27:52','2020-08-01 21:27:53');

对象：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@Data
public class CateTreeDTO implements Serializable {
    /**
     * 主键
     */
    @JsonSerialize(using = ToStringSerializer.class)
    private Long id;
    /**
     * 父级id
     */
    @JsonSerialize(using = ToStringSerializer.class)
    private Long parentId;
    /**
     * 分类名称
     */
    private String name;
    /**
     * 下级节点对象集合
     */
    private List<CateTreeDTO> children;
}

一、在程序中递归封装数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//==========================Service==========================
@Autowired
    private CategoryMapper categoryMapper;

    @Override
    public Result listCateTree() {
        List<CateTreeDTO> categoryList = categoryMapper.findAll();
        if (CollectionUtils.isEmpty(categoryList)) {
            return new Result();
        }
        List<CateTreeDTO> roots = new LinkedList<>();
        applyRoots(roots, categoryList);
        if (!CollectionUtils.isEmpty(roots)) {
            //递归回设下级节点
            for (CateTreeDTO root : roots) {
                recursionChild(root, categoryList);
            }
        }
        return new Result(roots);
    }

    /**
     * 递归回设下级节点
     */
    private void recursionChild(CateTreeDTO root, List<CateTreeDTO> categoryList) {
        Iterator<CateTreeDTO> iterator = categoryList.iterator();
        List<CateTreeDTO> childs = new LinkedList<>();
        while (iterator.hasNext()) {
            CateTreeDTO next = iterator.next();
            if (root.getId().equals(next.getParentId())) {
                childs.add(next);
                recursionChild(next, categoryList);
            }
        }
        if (!CollectionUtils.isEmpty(childs)) {
            root.setChildren(childs);
        }

    }

    /**
     * 查询根节点
     */
    private void applyRoots(List<CateTreeDTO> roots, List<CateTreeDTO> categoryList) {
        Iterator<CateTreeDTO> iterator = categoryList.iterator();
        while (iterator.hasNext()) {
            CateTreeDTO next = iterator.next();
            if (next.getParentId() == CategoryEnum.CATEGORY_ROOT.getValue()) {
                roots.add(next);
                iterator.remove();
            }
        }
    }
 //==========================Mapper========================== 
 @Select("SELECT " +
            "  `id`," +
            "  `parent_id` parentId," +
            "  `name`" +
            "FROM" +
            "  `category` ")
    List<CateTreeDTO> findAll();

控制台sql打印：

1
2
3
2020-08-23 16:59:42.055 DEBUG 268040 --- [nio-8080-exec-9] c.a.a.mapper.CategoryMapper.findAll      : ==>  Preparing: SELECT `id`, `parent_id` parentId, `name`FROM `category` 
2020-08-23 16:59:42.055 DEBUG 268040 --- [nio-8080-exec-9] c.a.a.mapper.CategoryMapper.findAll      : ==> Parameters: 
2020-08-23 16:59:42.057 DEBUG 268040 --- [nio-8080-exec-9] c.a.a.mapper.CategoryMapper.findAll      : <==      Total: 8

这种方法数据库只需执行一条sql，减轻数据库压力，但是需要在程序中递归封装子分类，子分类越多就越消耗性能。

二、在数据库中递归封装数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//==========================Service==========================
@Override
    public Result queryCateTree() {
        List<CateTreeDTO> cateTree = categoryMapper.queryAll();
        return new Result(cateTree);
    }
//==========================Mapper========================== 
     @Select("SELECT " +
            "  `id`," +
            "  `parent_id` parentId," +
            "  `name`" +
            "FROM" +
            "  `category` WHERE `parent_id`=0 ")
    @Results({
            @Result(column = "id", property = "id", jdbcType = JdbcType.BIGINT, id = true),
            @Result(column = "parent_id", property = "parentId", jdbcType = JdbcType.BIGINT),
            @Result(column = "name", property = "name", jdbcType = JdbcType.VARCHAR),
            @Result(column = "id", property = "children", jdbcType = JdbcType.ARRAY, many = @Many(fetchType = FetchType.EAGER, select = "com.arsenal.mapper.CategoryMapper.queryById")),
    })
    List<CateTreeDTO> queryAll();

    @Select("SELECT " +
            "  `id`," +
            "  `parent_id`," +
            "  `name`" +
            "FROM" +
            "  `category`" +
            " WHERE parent_id = #{id} ")
    @Results({
            @Result(column = "id", property = "id", jdbcType = JdbcType.BIGINT, id = true),
            @Result(column = "parent_id", property = "parentId", jdbcType = JdbcType.BIGINT),
            @Result(column = "name", property = "name", jdbcType = JdbcType.VARCHAR),
            @Result(column = "id", property = "children", jdbcType = JdbcType.ARRAY, many = @Many(fetchType = FetchType.EAGER, select = "com.arsenal.mapper.CategoryMapper.queryById")),
    })
    List<CateTreeDTO> queryById(@Param("id") Long id);

控制台sql打印：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2020-08-23 17:20:46.802 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryAll     : ==>  Preparing: SELECT `id`, `parent_id` parentId, `name`FROM `category` WHERE `parent_id`=0 
2020-08-23 17:20:46.815 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryAll     : ==> Parameters: 
2020-08-23 17:20:46.830 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ====>  Preparing: SELECT `id`, `parent_id`, `name`FROM `category` WHERE parent_id = ? 
2020-08-23 17:20:46.830 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ====> Parameters: 1(Long)
2020-08-23 17:20:46.832 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ======>  Preparing: SELECT `id`, `parent_id`, `name`FROM `category` WHERE parent_id = ? 
2020-08-23 17:20:46.832 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ======> Parameters: 2(Long)
2020-08-23 17:20:46.834 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ========>  Preparing: SELECT `id`, `parent_id`, `name`FROM `category` WHERE parent_id = ? 
2020-08-23 17:20:46.834 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ========> Parameters: 4(Long)
2020-08-23 17:20:46.835 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : <========      Total: 0
2020-08-23 17:20:46.836 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : <======      Total: 1
2020-08-23 17:20:46.837 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ======>  Preparing: SELECT `id`, `parent_id`, `name`FROM `category` WHERE parent_id = ? 
2020-08-23 17:20:46.837 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ======> Parameters: 3(Long)
2020-08-23 17:20:46.839 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ========>  Preparing: SELECT `id`, `parent_id`, `name`FROM `category` WHERE parent_id = ? 
2020-08-23 17:20:46.839 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ========> Parameters: 5(Long)
2020-08-23 17:20:46.839 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : <========      Total: 0
2020-08-23 17:20:46.840 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : <======      Total: 1
2020-08-23 17:20:46.840 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : <====      Total: 2
2020-08-23 17:20:46.842 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ====>  Preparing: SELECT `id`, `parent_id`, `name`FROM `category` WHERE parent_id = ? 
2020-08-23 17:20:46.842 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ====> Parameters: 6(Long)
2020-08-23 17:20:46.843 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ======>  Preparing: SELECT `id`, `parent_id`, `name`FROM `category` WHERE parent_id = ? 
2020-08-23 17:20:46.844 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ======> Parameters: 7(Long)
2020-08-23 17:20:46.844 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : <======      Total: 0
2020-08-23 17:20:46.845 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ======>  Preparing: SELECT `id`, `parent_id`, `name`FROM `category` WHERE parent_id = ? 
2020-08-23 17:20:46.846 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : ======> Parameters: 8(Long)
2020-08-23 17:20:46.847 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : <======      Total: 0
2020-08-23 17:20:46.847 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryById    : <====      Total: 2
2020-08-23 17:20:46.848 DEBUG 270836 --- [nio-8080-exec-2] c.a.a.mapper.CategoryMapper.queryAll     : <==      Total: 2

这种方法需要在数据库递归查询子分类，需要执行多条sql，比较消耗数据库性能。但是无需在程序种再封装子类，因为在数据库递归查询时已经封装好了。对程序性能影响不大。

查询结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
{
    "code": 200,
    "message": "success",
    "data": [
        {
            "id": "1",
            "parentId": "0",
            "name": "英超",
            "children": [
                {
                    "id": "2",
                    "parentId": "1",
                    "name": "利物浦",
                    "children": [
                        {
                            "id": "4",
                            "parentId": "2",
                            "name": "利物浦青年队",
                            "children": null
                        }
                    ]
                },
                {
                    "id": "3",
                    "parentId": "1",
                    "name": "切尔西",
                    "children": [
                        {
                            "id": "5",
                            "parentId": "3",
                            "name": "切尔西青年队",
                            "children": null
                        }
                    ]
                }
            ]
        },
        {
            "id": "6",
            "parentId": "0",
            "name": "德甲",
            "children": [
                {
                    "id": "7",
                    "parentId": "6",
                    "name": "拜仁",
                    "children": null
                },
                {
                    "id": "8",
                    "parentId": "6",
                    "name": "多特",
                    "children": null
                }
            ]
        }
    ],
    "time": 1598173182057
}

三. 建议

一般情况下，建议使用第一种方法查询这些树形结构数据，数据库的性能相对比较珍贵。还有这些分类数据一般是热点数据，放入缓存中，可以减轻数据压力，提高程序性能。

查询叶子节点sql

1
2
3
4
5
6
SELECT 
  * 
FROM
  category a 
WHERE 
  (SELECT COUNT(1) FROM category b WHERE b.parent_id = a.id) = 0 ;

延伸

    Java树形结构解析
    java实现tree树形结构
    JAVA 快速构建树形结构
    一条sql查出树形结构数据
    java递归生成树形结构菜单

Article Title:Category Tree

Article Author:Funing Ma

Release Time:2020-06-16 18:18:18

Last Update:2020-08-23 23:09:15

Original Link:https://mafuning.github.io/2020/06/16/2020-06-16-Category-Tree/

License Agreement: "CC-BY-SA-4.0"

Content
  1. 1. 前言
  2. 2. 一、在程序中递归封装数据
  3. 3. 二、在数据库中递归封装数据
  4. 4. 三. 建议
  5. 5. 延伸