主页 / coding / 问题 / 78443845
Accepted
Ben H
Asked: 2024-05-08 00:12:42 +0800 CST

跳过 DLL 中某些类型的节点

  • 772

我使用的是 Postgres 15.1，有一个node表格如下：

CREATE TABLE node (
    id TEXT PRIMARY KEY,
    is_skippable BOOL,
    prev TEXT REFERENCES node(id),
    "next" TEXT REFERENCES node(id)
);

该表表示一系列双向链表，但在某些情况下，对于某些查询，我想从is_skippable列表中删除节点并链接它们周围。

例如，如果我在数据库中植入了以下数据，其中有一个链接列表A1 <-> A2 <-> A3（可A2跳过）和其中之一B1 <-> B2：

INSERT INTO node VALUES 
  ('A1', FALSE, NULL, 'A2'), 
  ('A2', TRUE, 'A1', 'A3'), 
  ('A3', FALSE, 'A2', NULL),
  ('B1', FALSE, NULL, 'B2'), 
  ('B2', FALSE, 'B1', NULL);

对于某些查询，我想链接is_skippable节点。因此，如果我查询这个完整的表，我要查找的结果集是：

ID 上一页 下一个
A1 无效的 A3
A3 A1 无效的
B1 无效的 B2
B2 B1 无效的

请注意，A2不在结果集中，并且A2的指针已被重写到其之前和之后的节点。

在 Postgres 中是否有一种得到良好支持的方法来做到这一点？我在 StackOverflow 上的其他地方看到了简单链表的答案（例如postgresql 中的链表概念），但它们不需要重写指针。谢谢！

示例小提琴：https: //dbfiddle.uk/4lB4TAtF。

postgresql

2 个回答

  1. Best Answer

    您可能可以将其折叠以同时在两个方向上运行横向查询，但事实上，这只尝试跳到最近的不可跳过元素实际上可能是一个优势，使递归部分更加轻量级。db<>fiddle 上的演示：

    select id,(with recursive cte as( 
            select n2.id,n2.prev,n2.is_skippable
            from node n2
            where n2.id=n1.prev
            union
            select n2.id,n2.prev,n2.is_skippable
            from node n2 join cte 
              on n2.id=cte.prev
              and cte.is_skippable) CYCLE prev SET is_cycle USING path
          select id from cte where not is_skippable limit 1) as prev
        ,(with recursive cte as( 
            select n2.id,n2.next,n2.is_skippable
            from node n2
            where n2.id=n1.next
            union
            select n2.id,n2.next,n2.is_skippable
            from node n2 join cte 
              on n2.id=cte.next
              and cte.is_skippable) CYCLE next SET is_cycle USING path
          select id from cte where not is_skippable limit 1) as next
from node n1
where not is_skippable;
    ID 上一页 下一个
    A1 无效的 A3
    A3 A1 无效的
    B1 无效的 B2
    B2 B1 无效的

    1. 它并不介意列表是否有分支。您可以收紧递归 cte 连接条件来检查链接的双向性，使其严格遵循双向路径：

      from node n2 join cte 
       on n2.id = cte.next
      and n2.prev=cte.id --add this for strict

      分支以单向链接开始，因此这会将它们过滤掉。

    2. 由于内置的​​循环检测，它不介意循环/环/循环（如果您碰巧有的话）。

    3. 覆盖索引可以加快速度：

      create index on node (id)
   include(is_skippable,prev,"next")
   with(fillfactor=100);

    4. 您可能对pgrouting和Apache AGE感兴趣。

    • 1

  2. 这是使用递归 cte 的解决方案：

    WITH RECURSIVE cte (id, prev, next, count) AS
(
SELECT n.id, n.prev, n.next, 0
  FROM node AS n
 WHERE NOT is_skippable
UNION ALL
SELECT c.id, COALESCE (n_prev.prev, c.prev), COALESCE(n_next.next, c.next), c.count + 1 
  FROM cte AS c
  LEFT JOIN node AS n_prev
    ON n_prev.id = c.prev
  LEFT JOIN node AS n_next
    ON n_next.id = c.next
 WHERE (c.prev IS NOT NULL AND n_prev.is_skippable)
    OR (c.next IS NOT NULL AND n_next.is_skippable)
)
SELECT DISTINCT ON (id) id, prev, next
  FROM cte
 ORDER BY id, count DESC ;

    dbfiddle中的演示

    • 0

相关问题