使用闭包表计算亲属关系

家族关系查询看似简单，实际却很难。“这两个人有亲属关系吗？”“我们之间相隔多少层关系？”“最近的共同祖先是谁？”这些问题对人来说很自然，但使用标准邻接表存储时，回答它们的成本很高，因为每行只记录一对直接的父母与子女关系。要回答这些问题，必须递归遍历整棵树，在 SQL 中就需要使用递归 CTE——结果正确，但在深层树上速度较慢，也难以组合成更复杂的查询。

闭包表通过预先计算并存储树中完整的可达关系来解决这个问题。每一对祖先与后代及其深度，都会在写入时明确记录。代价是写入更复杂，收益是读取显著加快。对于读取远比写入频繁的家谱应用，这种权衡几乎总是合适的。

邻接表的问题

在关系数据库中存储树的标准方式是邻接表：表中每行都有一个 id 和一个 parent_id。它容易理解，写入也简单。新增一个人只需插入一行，修改父母关系也只需更新一次。

但要回答“X 的所有祖先是谁？”，就必须沿树向上递归遍历。在 PostgreSQL 和大多数现代 SQL 数据库中，可以用递归 CTE 表达：

WITH RECURSIVE ancestors AS (
  SELECT id, parent_id, 0 AS depth
  FROM people
  WHERE id = :person_id

  UNION ALL

  SELECT p.id, p.parent_id, a.depth + 1
  FROM people p
  JOIN ancestors a ON p.id = a.parent_id
)
SELECT * FROM ancestors;

这种方式能得到正确结果。但在深层树上，递归 CTE 需要在每一层扫描记录，成本随树的深度增长。对于只有三四代的浅层树，它足够快；对于跨越十代或十五代、包含数百个节点的树，性能会明显下降。更麻烦的是，像“查找 X 和 Y 的共同祖先”这样的查询，需要组合两个递归 CTE，分别完成递归后再连接结果，成本会进一步叠加。

闭包表结构

闭包表是在主要的人员表之外增加的一张表。闭包表中的每行代表一条可达关系：一对 (ancestor_id, descendant_id)，以及深度，也就是两者之间的边数。每个人也都是自己的祖先，深度为零。本文示例假设数据构成严格的树结构：每个人最多只记录父母中的一人，因此每一对祖先与后代之间都恰好只有一条路径和一个深度值。实际家谱中，每个人可能记录父母双方，也可能通过多条世系到达同一位祖先，此时需要扩展数据模式（例如，每条路径存储一行，或为每对祖先与后代保留最小深度）。LCA 查询此时返回的是可能存在的多位最近共同祖先中的一位，例如一对祖先夫妇中的一人。

CREATE TABLE family_closure (
  ancestor_id   INTEGER NOT NULL REFERENCES people(id),
  descendant_id INTEGER NOT NULL REFERENCES people(id),
  depth         INTEGER NOT NULL,
  PRIMARY KEY (ancestor_id, descendant_id)
);

CREATE INDEX idx_closure_descendant ON family_closure (descendant_id);
CREATE INDEX idx_closure_ancestor   ON family_closure (ancestor_id);

当 X 没有父母节点时，只插入一行：(X, X, 0)。当把 X 添加为 P 的子女时，插入范围会扩展到 P 的所有祖先：

-- Self-reference
INSERT INTO family_closure (ancestor_id, descendant_id, depth)
VALUES (:x_id, :x_id, 0);

-- All ancestors of parent P become ancestors of X, at depth + 1
INSERT INTO family_closure (ancestor_id, descendant_id, depth)
SELECT ancestor_id, :x_id, depth + 1
FROM family_closure
WHERE descendant_id = :parent_id;

这意味着，在世代深度为 N 的位置新增一个人，需要向闭包表插入 N+1 行。对于深度很少超过 15 或 20 代的典型家谱，这完全可以接受。写入开销与深度成正比，而不是与整棵树的总规模成正比。

查询所有祖先

有了闭包表，查询一个人的所有祖先只需要一次连接，无需递归：

SELECT p.*, fc.depth
FROM family_closure fc
JOIN people p ON p.id = fc.ancestor_id
WHERE fc.descendant_id = :person_id
  AND fc.depth > 0
ORDER BY fc.depth;

该查询可以通过对 descendant_id 进行一次索引扫描来完成。成本与祖先数量成正比，而不是与树的深度成正比。对于常见家谱深度的树，这通常比等价的递归 CTE 快得多，而且随着树变深，差距会扩大。

反方向的查询——查找一个人的所有后代——采用相同模式，只是改用 ancestor_id 索引：

SELECT p.*, fc.depth
FROM family_closure fc
JOIN people p ON p.id = fc.descendant_id
WHERE fc.ancestor_id = :person_id
  AND fc.depth > 0
ORDER BY fc.depth;

关系距离

两个人之间的关系距离，是经由共同祖先从一人走到另一人所需经过的亲属关系边数。它不是两人的深度之差，而是两人各自到 LCA 的距离之和。

SELECT MIN(a.depth + b.depth) AS degrees_of_separation
FROM family_closure a
JOIN family_closure b ON a.ancestor_id = b.ancestor_id
WHERE a.descendant_id = :person_a
  AND b.descendant_id = :person_b;

这里使用的连接与 LCA 查询相同，只是用 MIN() 聚合取代了 ORDER BY ... LIMIT 1。同辈堂表兄弟姐妹的关系距离为 4，因为双方到共同祖父母都需要两步。相差一代的堂表亲关系距离为 5。该查询无需任何应用层遍历逻辑，就能正确返回这些值。

要生成“相差两代的堂表亲”“叔祖父或舅公”等关系描述，还需要把深度值映射到关系名称的额外逻辑。一个接收 A 到 LCA 的深度、B 到 LCA 的深度并返回关系名称的函数，就能覆盖大多数常见情况。这属于应用层逻辑，而非 SQL；查询能够直接提供明确的整数深度后，这部分逻辑也会简单得多。

更新时如何维护闭包表

如上所示，插入操作很直接。删除和父母关系变更则需要更谨慎地处理。

从树中删除一个人，意味着要移除闭包表中所有将其列为祖先或后代的记录。如果此人有后代，仅这样做还不够：还必须移除将此人的祖先与这些后代相连的记录，否则闭包表仍会显示他们存在亲属关系。移除这些记录后，后代才会与此人的祖先集合断开连接。这是否符合预期取决于应用；在家谱场景中，通常会在应用层禁止删除已有后代记录的人。

变更父母关系——将原先记录的父母改为另一人——需要移除以该子女为根节点的子树所对应的旧闭包记录，再按照新的父母关系重新插入。最简单的实现方式是在一个事务中删除整个受影响子树的所有闭包记录，再从新的父母节点开始遍历并重新插入。这种方式是正确的，但事务期间会锁定相关记录。对于写入较少的大多数家谱应用，这可以接受。

性能比较

闭包表与递归 CTE 的性能差异很明显，并且会随树的规模增长而扩大。在一棵包含 500 个节点、平均深度为 12 代的合成树上，使用递归 CTE 的 LCA 查询速度会让界面交互略显迟缓。同样的查询改用闭包表连接后，速度足够快，延迟主要来自网络往返，而不是查询执行。

维护闭包表会给每次插入增加可测量的成本，且与树的深度成正比。但在家谱场景中，插入相较于读取很少发生——每增加一个人，家谱可能就会被查询数千次，用于展示关系和可视化。因此，这种权衡明显有利于闭包表方案。

存储开销也值得考虑。一棵包含 500 人、平均深度为 12 的家谱，其闭包表大约存储 6,500 行（每人约 13 行，包括各自的自引用记录）。即使计入 PostgreSQL 的每行开销（23 字节的元组头加上一个行指针）以及三个索引，每行所需空间也在一百字节左右，总计不到一兆字节。即使家谱数据库包含数万名成员，生成的闭包表也能轻松放入现代数据库服务器的内存中，供缓存和快速索引查找使用。