PostgreSQL 15.1中如何跳过双向链表的可跳过节点并重写指针？

针对你的需求，我们可以用**递归CTE（Common Table Expression）**实现查询时动态跳过is_skippable = TRUE的节点，并重构剩余节点的双向关联关系。这种方式完全在查询层面完成链路重构，不会修改原表数据。

方案1：分别推导每个节点的有效前继与后继 #

通过两个递归CTE分别追溯每个非可跳过节点的最终前继（跳过所有中间可跳过节点）和最终后继，再合并结果：

WITH RECURSIVE valid_prev AS (
    -- 初始：非可跳过节点的原始前继
    SELECT id, prev AS current_prev
    FROM node
    WHERE NOT is_skippable
    UNION ALL
    -- 递归：如果当前前继是可跳过节点，继续追溯其前继
    SELECT vp.id, n.prev
    FROM valid_prev vp
    JOIN node n ON vp.current_prev = n.id
    WHERE n.is_skippable
),
final_prev AS (
    -- 筛选每个节点的最终有效前继（非可跳过或NULL）
    SELECT id, current_prev AS effective_prev
    FROM valid_prev
    WHERE current_prev IS NULL OR NOT (SELECT is_skippable FROM node WHERE id = current_prev)
),
valid_next AS (
    -- 初始：非可跳过节点的原始后继
    SELECT id, "next" AS current_next
    FROM node
    WHERE NOT is_skippable
    UNION ALL
    -- 递归：如果当前后继是可跳过节点，继续追溯其后继
    SELECT vn.id, n."next"
    FROM valid_next vn
    JOIN node n ON vn.current_next = n.id
    WHERE n.is_skippable
),
final_next AS (
    -- 筛选每个节点的最终有效后继（非可跳过或NULL）
    SELECT id, current_next AS effective_next
    FROM valid_next
    WHERE current_next IS NULL OR NOT (SELECT is_skippable FROM node WHERE id = current_next)
)
-- 合并结果，仅保留非可跳过节点及重构后的关联
SELECT 
    n.id,
    n.is_skippable,
    fp.effective_prev,
    fn.effective_next
FROM node n
JOIN final_prev fp ON n.id = fp.id
JOIN final_next fn ON n.id = fn.id
WHERE NOT n.is_skippable
ORDER BY n.id;

方案2：从链表头部遍历构建完整链路 #

如果链表有明确的头部节点（prev IS NULL或追溯后前继为NULL），可以从头部开始遍历整个链表，跳过可跳过节点并直接关联有效节点：

WITH RECURSIVE full_chain AS (
    -- 定位所有链表的起始节点：非可跳过且无前继（或前继为可跳过节点）
    SELECT 
        id AS node_id,
        NULL::TEXT AS prev_node,
        "next" AS next_candidate
    FROM node
    WHERE NOT is_skippable
        AND (prev IS NULL OR (SELECT is_skippable FROM node WHERE id = prev))
    UNION ALL
    -- 遍历链表，跳过可跳过节点
    SELECT 
        CASE WHEN nc.is_skippable THEN fc.node_id ELSE nc.id END,
        CASE WHEN nc.is_skippable THEN fc.prev_node ELSE fc.node_id END,
        CASE WHEN nc.is_skippable THEN nc."next" ELSE nc."next" END
    FROM full_chain fc
    JOIN node nc ON fc.next_candidate = nc.id
    WHERE fc.next_candidate IS NOT NULL
),
chain_relations AS (
    -- 整理每个有效节点的双向关联
    SELECT 
        node_id AS id,
        prev_node AS effective_prev,
        LEAD(node_id) OVER (PARTITION BY prev_node IS NULL ORDER BY node_id) AS effective_next
    FROM full_chain
    WHERE NOT (SELECT is_skippable FROM node WHERE id = node_id)
)
-- 输出最终结果
SELECT 
    n.id,
    n.is_skippable,
    cr.effective_prev,
    cr.effective_next
FROM node n
JOIN chain_relations cr ON n.id = cr.id
WHERE NOT n.is_skippable
ORDER BY n.id;

方案说明 #

• 两种方案均为只读查询，不会修改原表的prev和next字段，仅在查询结果中重构关联关系。
• 递归CTE会自动处理多组链表的情况，每组链表都会独立完成重构。
• 针对你给出的示例场景（A1<->A2<->A3，A2可跳过；B1<->B2），两种方案都会输出：
  • A1的next为A3，A3的prev为A1
  • B1和B2保持原关联

内容的提问来源于stack exchange，提问作者bhub