一道Postgresql递归树题

微信扫一扫,分享到朋友圈

一道Postgresql递归树题

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

也是偶然的一次,群友出了一道题考考大家,当时正值疫情最最严重的三月(借口…),披着外套,天气也不是很好(借口…),耐着性子花了5分钟理解了下题,

第一个5分钟…无解,再第二个5分钟。。。无解,还第三个5分钟。。。终究无解( 之所以如此可能是题目太吸引我了吧
),之后又忙于各种琐事,一直到离职后重新找工作,

一再想想这事儿还是不能再拖了,终于 就到了今天…接下来开始表演了:joy::joy::joy:

chapter One:题目

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

    • 源数据
    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朋友都很急不可耐想知道答案哈哈:sunglasses:,答案或许重要或许也不重要,首先您得有一个思考的过程,一开始我的思考过程是这样的:

  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;
    • 以下为执行结果

      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
为数字时是符合题目答案的,不过即使这俩字段是数字在这两种情况下也是有问题的:

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

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

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

  • 方案二

    • 使用递归+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

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

finally:总结

首先,得说这是一道很好的SQL题,可不是嘛 ,让我忙活了好一会儿呢。。。,值得一提的是这道题可以考 递归
排序
ARRAY
(高级特性)、 类型及类型转换
、当然还有 窗口函数
,

如果真有某面试官考这个,可就真坑… ( ̄y▽, ̄)╭

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

微信扫一扫,分享到朋友圈

一道Postgresql递归树题

豆瓣8.1,一口气刷完,这“挖坟剧”太香了!

上一篇

《死亡搁浅》PC版发布升级档 现已支持8K显示

下一篇

你也可能喜欢

一道Postgresql递归树题

长按储存图像,分享给朋友