最近参与了公司的一个项目,其中有一个网盘的模块,在查询给定目录下所有子文件和子目录的时候,使用的递归的方法。

我们使用的是MySQL数据库,不像Oracle,MySQL是不支持递归的,但是我们可以通过函数自己来实现递归查询。

写在最前

是我错怪了MySQL,是我的查询方式错了,说的具体点就是WHERE FIND_IN_SET(id, getChilds('1001'))这个子句是有问题的,每次比较都会调用getChilds(str)这个函数,自然速度就慢了。所以解决方案就是缓存查询到的结果就好了,看下面的SQL语句。可能你要看完文章再回来看,才会比较清楚。

SELECT *
FROM
    netdisk_file,
    ( SELECT getAllChilds ( '188b30f7a50c43cb9a6c83e1c549bdbf' ) AS ids ) tmp
WHERE
    FIND_IN_SET( id, tmp.ids );

MySQL的递归方法

只需要了解一下MySQL函数的定义方法,还有几个内置函数的用法即可。

1、 FIND_IN_SET(str,strlist)

str代表要查询的字符串,strlist是给定的一个以逗号分隔的字符串;此函数用于查询str字符串在strlist中的位置,下标从1开始,如果没有找到,则返回0。

例如执行下面的子句,将返回2,因为MySQL在给定逗号分隔字符串的第二个位置。

SELECT FIND_IN_SET('MySQL', 'Oracle, MySQL, MariaDB, PostgreSQL');

而在对表的查询中,FIND_IN_SET还有另一种用法。例如下面的子句,将返回用户表中所有id在给定的逗号分隔字符串中的用户记录。

SELECT * FROM user WHERE FIND_IN_SET(id, '1921, 1231, 5654'); 

2、 CONCAT(str1,str2,...)

这是最基本的字符串拼接函数,用于连接N个子串,例如下面的语句,执行后将返回MySQL

SELECT CONCAT('My', 'SQL');

3、 CONCAT_WS(separator,str1,str2,...)

CONCAT拼接的时候是直接将字符串连在一起的,并没有分隔符,如果需要指定分隔符,就需要用到CONCAT_WS函数。

第一个参数separator传入分隔符,后面传入需要拼接的N个子串。例如下面的语句,执行后将返回My_SQL

SELECT CONCAT_WS('_', 'My', 'SQL');

4、 GROUP_CONCAT(expr)

GROUP_CONCAT函数可以分组的同时,把字段以特定分隔符拼接成字符串。

直接看下面这个例子,结果将返回user表中所有id,并以逗号分隔的字符串1921, 1231, 5654

SELECT GROUP_CONCAT(id) FROM user;

看完了上面几个函数,我想你大概知道怎么实现递归查询了吧?

我们需要使用GROUP_CONCAT函数,查询当前节点下所有子节点的ID,并且拼接成逗号分隔字符串,然后传递给FIND_IN_SET函数。

CREATE FUNCTION `getAllChilds` (
    `rootId` VARCHAR ( 36 )) RETURNS VARCHAR ( 1000 ) CHARSET utf8 BEGIN
    DECLARE
        sTemp VARCHAR ( 1000 );
    DECLARE
        sTempChd VARCHAR ( 1000 );
    
    SET sTemp = '$';
    
    SET sTempChd = CAST( rootId AS CHAR );
    WHILE
            sTempChd IS NOT NULL DO
            
            SET sTemp = CONCAT_WS( ',', sTemp, sTempChd );
        SELECT
            GROUP_CONCAT( id ) INTO sTempChd 
        FROM
            nd_person_file 
        WHERE
            FIND_IN_SET( parent_id, sTempChd ) > 0;
        
    END WHILE;
    RETURN sTemp;

END

来理解一下这个函数:

  1. CREATE FUNCTION getAllChilds创建一个函数,并且指定传入的参数为rootId 类型为VARCHAR(36)

RETURNS VARCHAR(1000)用来定义返回值参数类型。

  1. BEGINEND中间是函数体,写具体的逻辑。
  2. declare 用来声明变量,这里定义的sTemp即作为整个函数的返回值,是用来拼接成最终我们需要的以逗号分隔的递归串的;而sTempChd是为了记录下边WHILE循环中临时生成的所有子节点以逗号拼接成的字符串。
  3. SET用来给变量赋值。此处把传进来的根节点rootId赋值给sTempChd
  4. WHILE DO, END WHILE为循环语句,循环逻辑包含在内。循环体内,先用CONCAT_WS函数将临时生成的sTempChd拼接到最终结果sTemp中。然后以FIND_IN_SET(parent_id, sTempChd) > 0为条件,遍历在sTempChd中的所有parent_id,寻找以此为父节点的所有子节点id,并且通过GROUP_CONCAT(id) INTO sTempChd把这些子节点id都用逗号拼接起来,并覆盖更新sTempChd

等下次循环进来时,就会再次拼接sTemp,并再次查找所有子节点的所有子节点。循环往复,一层一层的向下递归遍历子节点。直到判断sTempChd为空,说明所有子节点都已经遍历完了,就结束整个循环。

  1. RETURN sTemp将sTemp作为函数返回值返回。

事实上,我们一直都是这么做的,但是在后来的测试中,暴露出了致命的问题。

我们的数据库使用的主键UUID长度为36位,我们用到了GROUP_CONCAT函数拼接字符串,但是,在MySQL中,这个函数能拼接的字符串长度是有限制的,默认为1024字节。

通过 show variables like "group_concat_max_len";

这个对于递归查询还是非常致命的。如果递归的子节点数量较多,尤其是我们的ID长度为36位,很容易超过最大长度。事实上也确实如此,递归出的文件列表并不完整。

所以解决方法就是修改group_concat_max_len的数值,以支持更大长度的字符串,方法有以下两种。

  1. 执行语句SET GLOBAL group_concat_max_len=102400;,这种方式会在MySQL重启后失效。
  2. 将上述参数写入SQL配置文件my.cnf,增加group_concat_max_len=102400

按照估算,对于36位的ID,最多可以支持2844个子节点的查询。

另一种递归思路

上述问题是开发过程中没有发现的,因为没有测试那么多的文件查询,问题暴露出来之后,我索性进行了更暴力的实验。使用shell脚本创建1000个文本文件,上传到网盘系统内,然后使用递归查询这1000个文件。

结果是正确的,但是耗时居然达50S!

而后我想起当初在编写回收站相关逻辑的时候,加入了存储文件逻辑路径的字段path(我们底层使用对象存储,用户看到的文件路径只是逻辑上的关系),当初只是为了还原文件的时候,能够还原到原来的位置。但是这个不经意的字段,在这里起到了巨大的作用!

因为网盘系统是不允许有重名文件存在的,所以文件的路径path也就是唯一的值,所以我们查询子集的操作就变成了下面这样:

SELECT * FROM netdisk_file 
WHERE path 
LIKE CONCAT(( 
    SELECT path FROM netdisk_file WHERE id = '188b30f7a50c43cb9a6c83e1c549bdbf' ),
    '%' 
) 
AND id != '188b30f7a50c43cb9a6c83e1c549bdbf';

类比到其他的树结构,我们可以使用ID来构建path,这样在查询子集的时候的效率只需要遍历一次全表。

最后修改:2021 年 05 月 29 日 06 : 21 PM