一道Postgresql递归树题

上帝

修改于 2020-09-27 14:48:53

4610

修改于 2020-09-27 14:48:53

文章被收录于专栏：影子影子

源数据

id	p_id	name
1	0	防控点级别
2	0	道路标准
3	0	应急响应等级
10000	1	一级
10001	1	二级
10002	1	三级
10003	1	四级
10004	1	五级
10005	2	主干路
10006	2	次干路
10007	2	支路
10008	2	城市下立交区

- 排列结果

id	p_id	name
1	防控点级别	0
10000	一级	1
10001	二级	1
10002	三级	1
10003	四级	1
10004	五级	1
2	道路标准	0
10005	主干路	2
10011	边支路1	10005
10012	边支路2	10005
10006	次干路	2
10007	支路	2
10008	城市下立交区	2
3	应急响应等级	0

chapter Two:亮出SQL

思考完毕，想必这会儿可以小试牛刀了，这就提供下SQL

以下为create 及必要的insert语句

DROP TABLE IF EXISTS "dicts";
CREATE TABLE "public"."dicts" (
"id" int8 NOT NULL,
"p_id" int8,
"name" varchar(50) COLLATE "pg_catalog"."default"
);

INSERT INTO "dicts" VALUES (10000, 10013, '一级');
INSERT INTO "dicts" VALUES (10001, 10013, '二级');
INSERT INTO "dicts" VALUES (10002, 10013, '三级');
INSERT INTO "dicts" VALUES (10003, 10013, '四级');
INSERT INTO "dicts" VALUES (10004, 10013, '五级');
INSERT INTO "dicts" VALUES (10005, 10011, '主干路');
INSERT INTO "dicts" VALUES (10006, 10011, '次干路');
INSERT INTO "dicts" VALUES (10007, 10011, '支路');
INSERT INTO "dicts" VALUES (10008, 10011, '城市下立交区');
INSERT INTO "dicts" VALUES (10011, 99999, '防控点级别');
INSERT INTO "dicts" VALUES (10012, 99999, '应急响应等级');
INSERT INTO "dicts" VALUES (10013, 99999, '道路标准');

chapter Three:再思考

可能很多IT朋友都很急不可耐想知道答案哈哈?，答案或许重要或许也不重要，首先您得有一个思考的过程，一开始我的思考过程是这样的：

思考一：这可能就是个普通排序，我直接建一个数字列标记下不久得了(to simple...，如果真这样还用考嘛)
思考二：拿出首列作为一个表和剩余列(也作为一个表)做联合查询。。。不行不行，SQL太复杂，后面也没法排序这是个问题
思考三：使用递归函数，但是递归通常只取出指定记录下级及分支级记录，如果整体取出SQL太复杂(涉及到循环排序)。。。这是个思路，但不完美

思考结果：

我仔细的分析了题目，得出如下结论: 这是一颗带有递归结构(思路)的递归树，之所以特意注明**递归结构**是因为递归出来的数据必须有一个带有树结构的字段，

不然之后无法使用排序生成最终结果

虽说递归解决了问题的第一步，后面我又碰到了问题的下一个重点：如何实现**树结构**字段列，终于我从实践中找到了三个解决方案：

方案一: 将递归后的结果按虚拟列(递归顺序列)及**p_id**列排序，这样貌似很简单，SQL走起

- 以下为SQL语句

-- SQL语句
with recursive tmp as
(
    select id, name, p_id,id::text as pcode from dicts where p_id=0
    union all
    select origin.id, origin.name, tmp.id as p_id, tmp.id::text as pcode from tmp
    join dicts as origin on origin.p_id = tmp.id
)
select * from tmp order by pcode asc,p_id asc;

-  以下为执行结果

id	p_id	name	pcode
1	防控点级别	0	1
10004	五级	1	1
10000	一级	1	1
10001	二级	1	1
10002	三级	1	1
10003	四级	1	1
2	道路标准	0	2
10005	主干路	2	2
10006	次干路	2	2
10007	支路	2	2
10008	城市下立交区	2	2
3	应急响应等级	0	3

结果也对，但是如果id列是varchr(字符串)类型，这个排列顺序结果就有问题，例如这样

id	p_id	name	pcode
1	防控点级别	0	1
10004	五级	1	1
10000	一级	1	1
10001	二级	1	1
10002	三级	1	1
10003	四级	1	1
10012	边支路2	10005	10005
10011	边支路1	10005	10005
2	道路标准	0	2
10005	主干路	2	2
10006	次干路	2	2
10007	支路	2	2
10008	城市下立交区	2	2
3	应急响应等级	0	3

注：我将id及p_id改为varchar类型并插入两行记录10012及10011)

chapter Four:最终解决

可以看到，以上默认递归排序在**id**及**p_id**为数字时是符合题目答案的，不过即使这俩字段是数字在这两种情况下也是有问题的:

这棵树有三级及更多级时
手动ID大小反序时
递归相关字段为字符时(上文已提到)

对于这头两个种情况这里不做深入，各位自行测试哈哈哈?

下面我就放出个人觉得合适的方案

方案二

-  使用递归+array函数将每次循环时产生的`depth`(虚拟字段)及`id`字段放进`path`(虚拟字段)并按其排序

    - SQL实现语句

WITH RECURSIVE tt (ID, NAME, p_id, PATH, DEPTH) AS (
    SELECT ID, NAME, p_id, ARRAY[ID] AS PATH, 1 AS DEPTH FROM dicts WHERE p_id='0'
    UNION ALL
    SELECT  D.ID, D.NAME, D.p_id, tt.PATH||D.ID, tt.DEPTH + 1 AS DEPTH
    FROM dicts D
    JOIN tt ON D.p_id = tt.ID
    )
    SELECT ID, NAME, p_id,DEPTH,PATH FROM tt
    ORDER BY PATH;

    - SQL输出结果

id	name	p_id	depth	path
1	防控点级别	0	1	{1}
10000	一级	1	2	{1,10000}
10001	二级	1	2	{1,10001}
10002	三级	1	2	{1,10002}
10003	四级	1	2	{1,10003}
10004	五级	1	2	{1,10004}
2	道路标准	0	1	{2}
10005	主干路	2	2	{2,10005}
10011	边支路1	10005	3	{2,10005,10011}
10012	边支路2	10005	3	{2,10005,10012}
10006	次干路	2	2	{2,10006}
10007	支路	2	2	{2,10007}
10008	城市下立交区	2	2	{2,10008}
3	应急响应等级	0	1	{3}

方案二
使用__递归__+__窗口函数__将每次循环时产生的depth(虚拟字段)及窗口函数产生的序列放进path(虚拟字段)并按其排序
SQL实现语句

WITH RECURSIVE T (id, name, p_id,path,DEPTH) AS (
SELECT ID, NAME, p_id, row_number() over(order by id asc)::text AS PATH, 1 AS DEPTH FROM dicts WHERE p_id=0
UNION ALL
SELECT  D.ID, D.NAME, D.p_id, T.PATH||'-'||row_number() over(PARTITION by t.path order by d.id asc), T.DEPTH + 1 AS DEPTH FROM dicts D
JOIN T ON D.p_id = T.ID
)
SELECT ID, NAME,p_id,DEPTH,PATH FROM T
ORDER BY PATH asc;

SQL输入结果

id	name	p_id	depth	path
1	防控点级别	0	1	1
10000	一级	1	2	1-1
10001	二级	1	2	1-2
10002	三级	1	2	1-3
10003	四级	1	2	1-4
10004	五级	1	2	1-5
2	道路标准	0	1	2
10005	主干路	2	2	2-1
10011	边支路1	10005	3	2-1-1
10012	边支路2	10005	3	2-1-2
10006	次干路	2	2	2-2
10007	支路	2	2	2-3
10008	城市下立交区	2	2	2-4
3	应急响应等级	0	1	3