数据库行数据转树状层级数据的两种后端实现方式

问题起源

最近在给公司的后台管理系统添加用户管理，部门管理，角色管理等等功能，设计到一个很重要的显示是，树状Tree来显示部门层级结构，如下图：

而数据库mysql中的数据是这样的：

是二维的，扁平的，一行一行的，准确的说，检索出来是一个条状的list，这个list通过parent_id有所关联。

那么，如何将其转换为树状层级结构呢？

通常由两种方式，一种是后台转换，在查询的时候，通过后台程序构造树状结构关联。一种是前端转换，通过javascript来将后端返回的列表list转换为一颗或多颗树。

后台转换

逐层查找

我们先来看看如何通过后端查询来进行转换：

首先查询根部节点：

public List<Record> getDeptTree() {
	List<Record> orgs = Db.find("SELECT dept_id as id, dept_name as `label` FROM sys_dept WHERE parent_id = 0 ORDER by order_num ASC ");
    for (Record o : orgs) {
        buildChildren(o);
    }
    return orgs;    
}

重点关注其中的方法buildChildren(Record dept)，这是一个递归函数：

private void buildChildren(Record org) {
    List<Record> children = getOrgChildren(org.getInt("id"));
    if (!children.isEmpty()) {
        for (Record r : children) {
            buildChildren(r);
        }
        org.set("children", children);
    }
}

private List<Record> getOrgChildren(Integer id) {
		List<Record> children = Db.find("SELECT dept_id as id, dept_name as `label` FROM sys_dept WHERE parent_id = ? ORDER by order_num ASC , id);
		return children;
	}

如此便将其数据从一行一行的数据表中构造为树状结构，如下所示：

[
    {
        "id": 100,
        "label": "若依科技",
        "children": [
            {
                "id": 101,
                "label": "深圳总公司",
                "children": [
                    {
                        "id": 103,
                        "label": "研发部门"
                    },
                    {
                        "id": 104,
                        "label": "市场部门"
                    },
                    {
                        "id": 105,
                        "label": "测试部门"
                    },
                    {
                        "id": 106,
                        "label": "财务部门"
                    },
                    {
                        "id": 107,
                        "label": "运维部门"
                    }
                ]
            },
            {
                "id": 102,
                "label": "长沙分公司",
                "children": [
                    {
                        "id": 108,
                        "label": "市场部门"
                    },
                    {
                        "id": 109,
                        "label": "财务部门"
                    }
                ]
            }
        ]
    }
]

上述算法是我们在自己的数据中重新实现的，

若依中的实现似乎是另一种方式。

检索全部数据算法构造

即一次性检索出全部的数据，然后通过算法来构造树状结构。若依中便是这样来实现的。

@Override
public List<TreeSelect> buildDeptTreeSelect(List<SysDept> depts)
{
    List<SysDept> deptTrees = buildDeptTree(depts);
    return deptTrees.stream().map(TreeSelect::new).collect(Collectors.toList());
}

/**
     * 构建前端所需要树结构
     * 
     * @param depts 部门列表
     * @return 树结构列表
     */
    @Override
    public List<SysDept> buildDeptTree(List<SysDept> depts)
    {
        List<SysDept> returnList = new ArrayList<SysDept>();
        List<Long> tempList = new ArrayList<Long>();
        for (SysDept dept : depts)
        {
            tempList.add(dept.getDeptId());
        }
        for (Iterator<SysDept> iterator = depts.iterator(); iterator.hasNext();)
        {
            SysDept dept = (SysDept) iterator.next();
            // 如果是顶级节点, 遍历该父节点的所有子节点
            if (!tempList.contains(dept.getParentId()))
            {
                recursionFn(depts, dept);
                returnList.add(dept);
            }
        }
        if (returnList.isEmpty())
        {
            returnList = depts;
        }
        return returnList;
    }

其中的判断语句：

if (!tempList.contains(dept.getParentId())) { ...将节点添加到返回列表中 }

判断的是，当前列表中是否有其父节点，如果某有，说明该节点是最顶级的节点。

再来看其中的递归方法recursionFn(depts, dept)

/**
     * 递归列表
     */
    private void recursionFn(List<SysDept> list, SysDept t)
    {
        // 得到子节点列表
        List<SysDept> childList = getChildList(list, t);
        t.setChildren(childList);
        for (SysDept tChild : childList)
        {
            if (hasChild(list, tChild))
            {
                recursionFn(list, tChild);
            }
        }
    }

这里的list总是完整检索的数据，而参数t表示以t为父节点的所有子节点。

获取节点子节点的函数：

/**
     * 得到子节点列表
     */
    private List<SysDept> getChildList(List<SysDept> list, SysDept t)
    {
        List<SysDept> tlist = new ArrayList<SysDept>();
        Iterator<SysDept> it = list.iterator();
        while (it.hasNext())
        {
            SysDept n = (SysDept) it.next();
            if (StringUtils.isNotNull(n.getParentId()) && n.getParentId().longValue() == t.getDeptId().longValue())
            {
                tlist.add(n);
            }
        }
        return tlist;
    }

总结

两种方式各有优劣，第二种方式数据库检索次数少，每次检索子节点不需要向数据库发起请求，但是其需要满足能够一次性查询出所有的数据；第一种方式数据库查询次数多，但是如果仅知道一个父节点id通过这种方式来构造数据比较直观，尤其是当你的数据库层级结构设计上没有ancestors字段时。