如何在PostgreSQL中高效遍历单链表结构表并返回ID序列？

你有一张自引用表，包含唯一主键id和外键next_id，next_id指向同表中的另一条记录（最后一条记录的next_id为null）。示例数据如下：

需要编写最有效的SQL查询，返回链表的ID序列（如示例中的[1, 3, 2]）。

最优方案：递归CTE查询 #

PostgreSQL中处理这种链式结构最高效的方式是使用递归公共表表达式（CTE），它专门设计用来遍历层级或链式结构的数据，性能表现优异（尤其在next_id字段创建索引时）。

具体SQL示例（以起始节点id=1为例）：

WITH RECURSIVE linked_list AS (
    -- 非递归部分：指定链表的起始节点
    SELECT id, next_id
    FROM your_table
    WHERE id = 1
    UNION ALL
    -- 递归部分：根据上一轮的next_id获取下一个节点，直到next_id为null终止
    SELECT t.id, t.next_id
    FROM your_table t
    JOIN linked_list ll ON t.id = ll.next_id
)
-- 将遍历到的id按顺序聚合为数组
SELECT ARRAY_AGG(id ORDER BY traversal_order) AS id_sequence
FROM (
    SELECT id,
           -- 生成遍历顺序，确保数组顺序与链表遍历逻辑一致
           ROW_NUMBER() OVER () AS traversal_order
    FROM linked_list
) sub;

关键说明 #

1. 递归逻辑：
   • 非递归段定义遍历的起点，可根据需求修改WHERE条件指定不同起始节点。
   • 递归段通过关联上一轮结果的next_id，自动向下遍历，直到没有匹配的节点（即next_id为null）时停止。
2. 性能优化：给next_id字段创建索引（CREATE INDEX idx_your_table_next_id ON your_table(next_id);），能让数据库快速定位下一个节点，避免全表扫描，大幅提升遍历效率。
3. 顺序保证：使用ROW_NUMBER()生成遍历顺序，确保最终数组的元素顺序完全匹配链表的遍历路径。

示例执行结果 #

运行上述查询后，会返回符合要求的ID序列：

id_sequence
-------------
 {1,3,2}

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