2020年9月26日星期六

一道Postgresql递归树题

转载请注明出处: https://www.cnblogs.com/funnyzpc/p/13698249.html

也是偶然的一次，群友出了一道题考考大家,当时正值疫情最最严重的三月(借口...)，披着外套，天气也不是很好(借口...)，耐着性子花了5分钟理解了下题，
第一个5分钟...无解，再第二个5分钟。。。无解，还第三个5分钟。。。终究无解(之所以如此可能是题目太吸引我了吧)，之后又忙于各种琐事，一直到离职后重新找工作，
一再想想这事儿还是不能再拖了，终于 就到了今天...接下来开始表演了😂😂😂

chapter One:题目

  1. 将下表源数据排列成指定顺序(看完题目请先思考几分钟)

    • 源数据
    idp_idname
    10防控点级别
    20道路标准
    30应急响应等级
    100001一级
    100011二级
    100021三级
    100031四级
    100041五级
    100052主干路
    100062次干路
    100072支路
    100082城市下立交区
    • 排列结果
    idp_idname
    1防控点级别0
    10000一级1
    10001二级1
    10002三级1
    10003四级1
    10004五级1
    2道路标准0
    10005主干路2
    10011边支路110005
    10012边支路210005
    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朋友都很急不可耐想知道答案哈哈😎，答案或许重要或许也不重要，首先您得有一个思考的过程，一开始我的思考过程是这样的：

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

    • 以下为执行结果

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

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

    idp_idnamepcode
    1防控点级别01
    10004五级11
    10000一级11
    10001二级11
    10002三级11
    10003四级11
    10012边支路21000510005
    10011边支路11000510005
    2道路标准02
    10005主干路22
    10006次干路22
    10007支路22
    10008城市下立交区22
    3应急响应等级03

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

chapter Four:最终解决

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

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

对于这头两个种情况这里不做深入，各位自行测试哈哈哈😁
下面我就放出个人觉得合适的方案

  • 方案二

    • 使用递归+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输出结果
      idnamep_iddepthpath
      1防控点级别01{1}
      10000一级12{1,10000}
      10001二级12{1,10001}
      10002三级12{1,10002}
      10003四级12{1,10003}
      10004五级12{1,10004}
      2道路标准01{2}
      10005主干路22{2,10005}
      10011边支路1100053{2,10005,10011}
      10012边支路2100053{2,10005,10012}
      10006次干路22{2,10006}
      10007支路22{2,10007}
      10008城市下立交区22{2,10008}
      3应急响应等级01{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=0UNION ALLSELECT 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 DJOIN T ON D.p_id = T.ID)SELECT ID, NAME,p_id,DEPTH,PATH FROM TORDER BY PATH asc;

  • SQL输入结果

    idnamep_iddepthpath
    1防控点级别011
    10000一级121-1
    10001二级121-2
    10002三级121-3
    10003四级121-4
    10004五级121-5
    2道路标准012
    10005主干路222-1
    10011边支路11000532-1-1
    10012边支路21000532-1-2
    10006次干路222-2
    10007支路222-3
    10008城市下立交区222-4
    3应急响应等级013

    可以看到方案三的输出结构性更好(纯个人摸索出来的);另~,ARRAY的方案 得感谢网友的博文😃

finally：总结

首先，得说这是一道很好的SQL题，可不是嘛🤦🤦🤦，让我忙活了好一会儿呢。。。,值得一提的是这道题可以考递归、排序、ARRAY(高级特性)、类型及类型转换、当然还有窗口函数,
如果真有某面试官考这个，可就真坑...(￣y▽,￣)╭

另外,若内容有些许谬误恳请指正哈，各位周末愉快，同时预祝各位一线码农中秋快乐🌙

原文转载：http://www.shaoqun.com/a/477667.html

心怡科技：https://www.ikjzd.com/w/1327

sonar：https://www.ikjzd.com/w/215

trax：https://www.ikjzd.com/w/1489


转载请注明出处:https://www.cnblogs.com/funnyzpc/p/13698249.html也是偶然的一次，群友出了一道题考考大家,当时正值疫情最最严重的三月(借口...)，披着外套，天气也不是很好(借口...)，耐着性子花了5分钟理解了下题，第一个5分钟...无解，再第二个5分钟。。。无解，还第三个5分钟。。。终究无解(之所以如此可能是题目太吸引我了吧)，之后又忙于各种琐事，
cicpa：https://www.ikjzd.com/w/1375
西农：https://www.ikjzd.com/w/1368
在亚马逊上卖什么，更容易赚到钱？--卖家选品指南1：https://www.ikjzd.com/home/126164
如何优化YouTube视频获取更好的排名？：https://www.ikjzd.com/home/100000
案例分析：Google购物广告常见政策违规情况有哪些？：https://www.ikjzd.com/home/105818
发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)