PostgreSQL中的递归

PostgreSQL中的递归常用于解决树形结构的模型，常用的需求有：查询根节点、层级、路径、是否叶子节点、是否死循环等，下面通过实例讲解如何解决这些问题。

• 实例数据准备

test=> CREATE TABLE sys_cbp_test (id INT,parent_id INT);
CREATE TABLE
test=> INSERT INTO sys_cbp_test
test-> VALUES
test->     (1, NULL),
test->     (2, 1),
test->     (3, 2),
test->     (4, 3),
test->     (5, 1),
test->     (6, 5),
test->     (7, 2),
test->     (8, 6),
test->     (5, 8),    --此次存在死循环
test->     (20, NULL),
test->     (21, 20),
test->     (22, 21);
INSERT 0 12
test=> SELECT * FROM sys_cbp_test;
 id | parent_id 
----+-----------
  1 |          
  2 |         1
  3 |         2
  4 |         3
  5 |         1
  6 |         5
  7 |         2
  8 |         6
  5 |         8
 20 |          
 21 |        20
 22 |        21
(12 rows)
复制

• 查询节点层级、起始节点、节点路径、是否存在死循环、是否叶子节点等

test=> WITH RECURSIVE x(id, --节点ID
test(> parent_id,           --父节点ID
test(> level,               --节点层级
test(> path,                --节点路径
test(> root,                --起始节点
test(> cycle                --节点是否循环
test(> ) AS
test->  (--起始节点查询语句
test(>   SELECT id,
test(>          parent_id,
test(>          1,
test(>          ARRAY[id],
test(>          id    AS root,
test(>          FALSE
test(>     FROM sys_cbp_test
test(>    WHERE parent_id IS NULL  --查询的起始节点
test(>   UNION ALL
test(>   --递归循环语句
test(>   SELECT b.id,
test(>          b.parent_id,
test(>          level + 1,         --递归一层节点层级加1
test(>          x.path || b.id,    --把节点按照递归的次序依次存入数组
test(>          x.root,            --记录起始节点
test(>          b.id = ANY(path)   --判断当前节点是否已存在路径数组中，如果存在说明存在循环
test(>     FROM x,
test(>          sys_cbp_test b
test(>    WHERE x.id = b.parent_id --从起始节点往下递归
test(>      AND NOT cycle          --终止循环节点
test(>    )
test-> SELECT id,
test->        x.parent_id,
test->        level,
test->        array_to_string(path, '->') AS path,
test->        root,
test->        path,
test->        cycle,
test->        CASE 
test->            WHEN t.parent_id IS NULL THEN 
test->              TRUE 
test->            ELSE 
test->              FALSE 
test->        END AS isleaf  --是否叶子节点
test->   FROM x 
test->   LEFT JOIN (SELECT parent_id 
test(>                FROM sys_cbp_test 
test(>               GROUP BY parent_id) t 
test->     ON x.id = t.parent_id
test->--WHERE NOT cycle --去掉循环重复的节点，反过来也可以查找哪个节点存在死循环
test->  ORDER BY id;
 id | parent_id | level |     path      | root |    path     | cycle | isleaf 
----+-----------+-------+---------------+------+-------------+-------+--------
  1 |           |     1 | 1             |    1 | {1}         | f     | f
  2 |         1 |     2 | 1->2          |    1 | {1,2}       | f     | f
  3 |         2 |     3 | 1->2->3       |    1 | {1,2,3}     | f     | f
  4 |         3 |     4 | 1->2->3->4    |    1 | {1,2,3,4}   | f     | t
  5 |         8 |     5 | 1->5->6->8->5 |    1 | {1,5,6,8,5} | t     | f --此行一般需要过滤掉（NOT cycle）
  5 |         1 |     2 | 1->5          |    1 | {1,5}       | f     | f
  6 |         5 |     3 | 1->5->6       |    1 | {1,5,6}     | f     | f
  7 |         2 |     3 | 1->2->7       |    1 | {1,2,7}     | f     | t
  8 |         6 |     4 | 1->5->6->8    |    1 | {1,5,6,8}   | f     | f
 20 |           |     1 | 20            |   20 | {20}        | f     | f
 21 |        20 |     2 | 20->21        |   20 | {20,21}     | f     | f
 22 |        21 |     3 | 20->21->22    |   20 | {20,21,22}  | f     | t
(12 rows)


复制