mysql巧妙化解递归查询树形数据 | 纯sql

刺骨的言语ヽ痛彻心扉 2023-09-24 14:18 60阅读 0赞

## 前言 ##

*  开发中树形结构应该是很常见的一种数据结构了。而在数据库方面往往也都伴随相应的树形设计。在 `mysql` 中通过 `parent_id` 来绑定其上游，从而达到树形结构的存储，但是在查询的过程中就需要我们将 `List` 列表转成我们理想中的 `Tree` 树。

## 构建树 ##

List<Location> locations = this.baseMapper.selectList(queryWrapper);
    Map<String, List<Location>> collect = locations.stream().collect(Collectors.groupingBy(Location::getId));
    List<QueryLocationDto> resultList = new ArrayList<>();
    List<Location> parentLocation = getParentLocation(1, collect, id);
    if (CollectionUtils.isNotEmpty(parentLocation)) {
        for (Location location : parentLocation) {
            QueryLocationDto dto = new QueryLocationDto();
            BeanUtils.copyProperties(location, dto);
            resultList.add(dto);
        }
    }
    复制代码

private List<Location> getParentLocation(int level, Map<String, List<Location>> collect, String id) {
            List<Location> locationList = new ArrayList<>();
            if (collect.containsKey(id)) {
                Location location = collect.get(id).get(0);
                locationList.add(location);
                String superid = location.getSuperid();
                locationList.addAll(getParentLocation(level + 1, collect, superid));
            }
            return locationList;
        }
    复制代码

*  相信大部分我们 都是通过 `Java` 来处理的。 其中 `getParentLocation` 就是用递归不断的去构建上下级关系。这种方式也是我比较推荐的，因为这样就把职责分的很清楚 `Java` 负责处理业务 ，`数据库` 就仅仅用来做数据的持久化，这也方便我们对数据库切换与升级。否则在更换其他数据库时还需要考虑是否支持递归属性。

public <T> List<OperatorTree> getTree(List<T> parentList , Map<?, List<T>> collectMap, OperatorTreeInterface operatorTreeInterface) throws InvocationTargetException, IllegalAccessException, NoSuchMethodException {
            if (org.apache.commons.collections4.CollectionUtils.isEmpty(parentList)) {
                return new ArrayList<>();
            }
            List<OperatorTree> list = new ArrayList<>();
            OperatorMapping operatorMapping = operatorTreeInterface.operatorMapping();
            for (T t : parentList) {
                OperatorTree tree = new OperatorTree();
                tree.setId(BeanUtils.getProperty(t, operatorMapping.getId()));
                tree.setLabel(BeanUtils.getProperty(t, operatorMapping.getLabel()));
                tree.setRealData(t);
                if (collectMap.containsKey(tree.getId())) {
                    List<T> ts = collectMap.getOrDefault((tree.getId()), new ArrayList<>());
                    tree.setChildren(getTree(ts, collectMap, operatorTreeInterface));
                } else {
                    try {
                        List<T> ts = collectMap.getOrDefault(Long.valueOf(tree.getId()), new ArrayList<>());
                        tree.setChildren(getTree(ts, collectMap, operatorTreeInterface));
                    } catch (Exception e) {
                        tree.setChildren(getTree(new ArrayList<>(), collectMap, operatorTreeInterface));
                    }
                }
                list.add(tree);
            }
            return list;
        }
    复制代码

*  有的时候为了能够量产化，这里我也针对项目的场景利用泛型进行一次封装。有兴趣可以自己针对自己的项目场景进行封装。这样树形与列表的转换就无须每次冗余了。然而今天我们的重点是如何利用 `mysql` 来实现递归查询， 虽然这种方式个人不推荐使用，但我们还是需要了解 `mysql` 的特性的。

![format_png][]

*  如图我们先在数据库中创建一张 `test` 表， 表里构建一棵树出来。 `祖父→父亲→孙子` 。

> 请根据选中节点查询其上游关系

*  啥意思呢？就是根据你我想找到你家血脉关系。

![format_png 1][]

*  这个业务本身没有难点，我们只需要一步一步的去寻找即可。但是从技术层面上看就有点搞头了。首先我们不确定是多少层，这就无法通过代码堆砌的方法进行实现了。只能动态的去递归查询。

SELECT t2.id, t2.`name`,t1.lvl
    FROM
        (
            SELECT 
            @r AS _id,
            (SELECT @r := parent_id FROM test WHERE id = _id) AS parent_id,
            @l := @l + 1 AS lvl
            FROM
            (SELECT @r := 3, @l := 0) vars, test AS h
            WHERE @r <> 0 
        ) t1
    JOIN test t2
    ON t1._id = t2.Id
    order by t1.lvl
    复制代码

![format_png 2][]

*  通过上述代码我们即可完成家族血脉的查询。能够清楚的查出家族的具体支脉。

## 解析 ##

*  上面的 `sql` 虽然能够实现递归，但是好像和我们平时接触的 `sql` 不大一样。这里我们简单分析下

*  首先 `mysql` 是支持我们用户定义对象的。比如下面这个 `sql`

set @name = '123';
    select @name from dual;
    复制代码

*  执行上面的sql 你会发现查出来的就是 `123` 。 这就是使用到 `mysql` 中变量定义功能。 通过 `@` 来进行对象的定义以及赋值。

![format_png 3][]

*  首先 `mysql`的执行顺序是由里及外 。 就是说越在内部越先执行。所以针对上面的 `SQL` 我们将它整理下顺序能够得出。

![format_png 4][]

*  注意 `(SELECT @r := parent_id FROM test WHERE id = _id) AS parent_id,` 这段sql 实际上归属于第二层。图示中并没有列出，太占地方了。

### 第三层 ###

*  有了上面的两个知识点铺垫，现在我们直接看 `SELECT @r := 3, @l := 0` 是不是就很容易明白了呢？ `r、l` 就是 `mysql` 中定义出来的两个变量。分别是`3,0` 。和我们上面演示案列中 `select @name from dual` 是一个意思。
 *  至于 `(SELECT @r := 3, @l := 0) vars, test AS h`这段就更好理解了。test本身就是一张物理表 ， 我们定义出来的两个变量也可以理解成一张表。在mysql中查询两种表是为了区分开来正常都是需要各自取别名的。所以我们定义的变量就是 `vars` 别名 。 `test` 别名 `h`。

### 第二层 ###

SELECT 
            @r AS _id,
            (SELECT @r := parent_id FROM test WHERE id = _id) AS parent_id,
            @l := @l + 1 AS lvl
            FROM
            (SELECT @r := 3, @l := 0) vars, test AS h
            WHERE @r <> 0 
    复制代码

*  第二层可以说是递归的核心 。这里我们需要明白 上述代码为什么会产生递归的效果呢？首先我们知道 `mysql` 存在 `左外连接`、`右外连接`、`内连接` 。除了这三种还有一种就是 `笛卡尔积`连接。什么意思呢？

![format_png 5][]

*  也就是说上面我们的sql `FROM (SELECT @r := 3, @l := 0) vars, test AS h` 就是为了给我们构建出一个笛卡尔积 ，而我们定义的变量其实就是一张表里的一条数据，所以这里就是将 `test` 表所有记录都提取出来。

![format_png 6][]

![format_png 7][]

*  也就是说我们第二层的sql 就是将 test表全部查出来，然后将其字段进行扩展。说白了这种方式并不是一种真正的递归。但是因为引入了一个变量，所以在扩充的时候和递归一个效果。
 *  但是笛卡尔积查询出来的数据是无法保证两张表的关联性的，所以我们并没有将 `h` 表相关字段查出来，因为那根本没用。剩下的就是我们一开始说的一步一步的查询扩充字段了

### 第一层 ###

*  第一层就简单很多了 ，因为第二层就已经查询出来相关的树形数据了，但是因为第二层使用的笛卡尔积 `h` 表信息没法使用，仅仅使用了其数量。那么我们的名称这个时候还没有，第一层的作用就是将节点名称扩充出来。

## 总结 ##

*  最后我们简单总结下，`mysql` 的查询递归正常使用存储过程来实现。但是上面提到的方法巧妙的实现了递归的效果。理论上上述方法和存储过程相比存在一个优点就是不会死循环。

[format_png]: https://img-blog.csdnimg.cn/img_convert/b08d7ef0cfab3a6e2e2c8fd39cc115b2.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/9e5270d9050ba34b74829c11b89639db.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/64e52923f3c81341bc884967ca39b425.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/45748f3014b8033ac59c8c7adf5426a4.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/e9dc0fff7dbda1d3f06be44118f72237.webp?x-oss-process=image/format,png
[format_png 5]: https://img-blog.csdnimg.cn/img_convert/2a79c25f3848f953391854c4f3025edd.webp?x-oss-process=image/format,png
[format_png 6]: https://img-blog.csdnimg.cn/img_convert/e915f0349eaf102a23655864b9ca9f4f.webp?x-oss-process=image/format,png
[format_png 7]: https://img-blog.csdnimg.cn/img_convert/065e93e8240caaf0f1f85de5249df531.webp?x-oss-process=image/format,png