PAYATHON 2026

SQLite 能否在一个递归 CTE 中遍历父子链表并计算层级？

数据小许

结论

如果 idx 需要根据现有的 prev/next 链表动态计算，通常不适合直接把两段递归合并成一个简单的递归 CTE：一段沿兄弟链计算位置，另一段沿父子关系遍历树。也可以用携带遍历栈的状态机尝试一次遍历，但 SQL 会复杂得多。

如果能在每条父子关系上保存子节点的整数位置，例如 position，一个递归 CTE 就可以同时计算层级和位置，并按树的先序顺序输出。

推荐做法：保存子节点位置

表结构可以改为：

CREATE TABLE map (
  parent,
  child,
  position
);

每个父节点的子节点按 position 从小到大排列。递归时，level 由父节点层级加一得到，idx 则直接取当前边上的 position：

WITH RECURSIVE tree(child, level, idx, path) AS (
  VALUES (0, 0, 0, '')

  UNION ALL

  SELECT
    m.child,
    t.level + 1,
    m.position,
    t.path || printf('%010d.', m.position)
  FROM map AS m
  JOIN tree AS t ON m.parent = t.child
)
SELECT
  substr('..........', 1, level * 3) || child AS node,
  level,
  idx
FROM tree
ORDER BY path;

path 会累积每个节点祖先路径上的位置，用来保证先序输出：先输出一个节点，再输出它的子树，最后输出同层的下一个节点。printf('%010d.', ...) 会把位置补齐到固定宽度，方便按文本排序。如果位置可能超过 10 位，需要相应增加宽度。示例以根节点 0 作为递归起点，因此不需要把它放进 map 表。

保留 prev/next 时

在现有结构中，位置不是节点的直接属性。需要从 prev is null 的首节点出发，沿 next 链逐个计数，再按 parent 使用这些位置遍历树。因此，把原查询拆成两个递归步骤会更清晰。如果运行时必须只执行一次递归，可以设计一个显式的深度优先遍历状态，把当前节点和回溯所需的信息放进递归状态。这种写法要处理进入子树、访问兄弟节点和回溯等分支，维护起来比存储 position 更复杂。

使用前检查

确认每个父节点的子节点链表只有一个 prev IS NULL 的首节点，链表没有断链或环，并且每个子节点只属于一个父节点。否则，链表遍历可能漏行或重复，层级结果也可能不符合预期。

备注：内容仅供参考。