树形表结构设计总结

技术数据库

Word count: 3.1kReading time: 12 min

 2021/01/01 

树形表结构设计总结

在业务建模中树形表是很常见的结构，在多种场景的中都会用到，比如：

用户权限管理
企业组织架构
论坛网站评论功能
……

以用户评论功能为例，其业务场景是：

用户可以发表多条评论。
用户可以对其他用户的评论进行回复。
用户可以对其他用户的回复进行回复。
用户删除评论或回复后，所有对其回复（及其子级）的回复都会被级联删除。
…

这类功能常见的设计方法如下：

设计	查询父子节点	查询树结构（后代/祖先）	插入	删除	引用完整
邻接表	简单	困难（除非支持递归查询）	简单	简单	是
枚举路径	简单	简单	简单	简单	否
嵌套集	困难	简单	困难	困难	否
闭包表	简单	简单	简单	简单	是

邻接表（Adjacency List）

邻接表是最广泛使用的设计方法，其使用 parent_id 字段引用同一张表的其他记录，并建立外键约束维护关系。

CREATE TABLE Comments (
  comment_id SERIAL PRIMARY KEY,
  parent_id BIGINT UNSIGNED,
  comment TEXT NOT NULL,
  FOREIGN KEY (parent_id) REFERENCES Comments(comment_id)
);

查询一条评论和它的直接后代：

SELECT c1.*, c2.*
FROM Comments c1 
LEFT JOIN Comments c2 ON c2.parent_id = c1.comment_id;
--- LEFT JOIN Comments c3 ON c3.parent_id = c2.comment_id;
--- ...
--- LEFT JOIN Comments cn ON cn.parent_id = cm.comment_id;

这种做法存在以下问题：

扩展性差：每增加一层查询都要额外扩展一个关联（通过 ORM 框架或在业务代码中生成动态 SQL 则这种情况能有所缓解）。
难以使用聚合函数（比如 COUNT、SUM、MAX、MIN 等）。

可以先查询出所有行，在业务代码中重新构造出这棵树。但处理数据之前就进行从数据库到应用程序之间的 大量数据复制，非常低效（可能只需要部分子树，或者只需要统计值而非全量数据，但不得不查出完整的树）。

另一方面是如果要从树中 删除节点很困难，需要执行多次查询找到所有后代节点，自底向上逐个删除这些节点以满足外键完整性。

解决方法：

不使用外键约束，但需要配合其他方法处理迷失节点，尽可能少产生零散数据。
可以使用 触发器 或指定外键模式为 ON DELETE CASCADE 实现 级联删除，清理整棵子树。
如果删除非叶子节点（并提升其子节点），或者移动子节点到另一个子节点，则需要先修改其 parent_id 再删除：

SELECT parent_id
FROM Comments 
WHERE comment_id = 6;

UPDATE Comments 
SET parent_id = 4 
WHERE parent_id = 6;

DELETE FROM Comments
WHERE comment_id = 6;

这种做法也有好处，即增加或修改节点比较方便，只需要指定 parent_id：

1 2	INSERT Comments (parent_id, comment) VALUES (7, 'OK!');

1
2
3

UPDATE Comments 
SET parent_id = 3
WHERE comment_id = 6;

递归查询（Recursive Query）

邻接表存在难以实现扩展查询，但一些关系型数据库（比如 Microsoft SQL Server 2005、Oracle 11gR2、IBM DB2 和 PostgreSQL 8.4 ）提供了递归查询（符合 SQL-99 标准）的支持，能有效解决这种问题：

WITH CommentTree (comment_id, parent_id, comment, depth)
AS (
  SELECT *, 0 AS depth
  FROM Comments
  WHERE parent_id IS NULL
  UNION ALL
  SELECT c.*, ct.depth + 1 AS depth
  FROM CommentTree ct
  JOIN Comments c ON (ct.comment = c.parent_id)
)
SELECT * FROM CommentTree WHERE comment_id = 10

MySQL、SQLite、Infomix、Oracle 10g 则不支持递归查询。

Oracle 9i 和 10g 支持 WITH 子句，但不是在递归查询时使用。它们有着自己特殊的语法定义：START WITH 和 CONNECT BY PRIOR。
1
2
3
4
SELECT *
FROM Comments
START WITH comment_id = 9876
CONNECT BY PRIOR parent_id = comment_id;

枚举路径（Path Enumeration）

路径枚举的将所有祖先的信息组合成类似 Linux 绝对路径 的字符串，分隔符相邻两个节点间距离是 1，并保存为每个节点的属性，能很巧妙地解决了邻接表 从树中获取一个给定节点的所有祖先的开销很大 的问题。

CREATE TABLE Comments (
  comment_id SERIAL PRIMARY KEY,
  parent_id BIGINT UNSIGNED,
  comment TEXT NOT NULL,
  path VARCHAR(1000)
);

比如 comment_id 为 2 的评论是 comment_id 为 1（path 的值为“1/”）的回复，则其 path 可记为“1/2/”；comment_id 为 3 的评论是 comment_id 为 2 的回复，则可以记为“1/2/3”。

通过比较每个节点的路径，可以查询一个节点的祖先（比如评论 7 的祖先，可匹配“1/4/6/%”、“1/4/5”、“1/%”）或后代（比如评论 4 的后代，可匹配“1/4/5”、“1/4/6”、“1/4/6/7”）：

1
2
3

SELECT * 
FROM Comments AS c
WHERE '1/4/6/7/' LIKE c.path || '%';

1
2
3

SELECT *
FROM Comments AS c
WHERE c.path LIKE '1/4/' || '%';

计算一棵子树所有节点的值的总和、统计数量等操作同样也只需要使用 LIKE：

SELECT COUNT(*)
FROM Comments AS c
WHERE c.path LIKE '1/4/' || '%'
GROUP BY comment;

在树中插入节点时无需修改任何其他的行：

复制一份要插入节点的逻辑上的父亲节点的路径，将这个新节点的 ID 追加到路径末尾。
如果 ID 是在插入时自动生成的，可能需要先插入这条记录，再获取这条记录的 ID，并更新它的路径。

INSERT INTO Comments (comment) VALUES ('OK!');

UPDATE Comments 
SET path = (
  SELECT path
  FROM Comments
  WHERE comment_id = 7
) || LAST_INSERT_ID() || '/'
WHERE comment_id = LAST_INSERT_ID();

这种设计也存在问题：

没有外键约束不能确保路径格式总是正确、路径中的节点确实存在，依赖于应用程序的逻辑代码维护路径字符串。
验证字符串正确性开销很大（LIKE 操作非最左前缀查询难以利用索引）。
无论是 VARCHAR 还是 TEXT 类型，字符串类型长度都存在限制，树结构无法无限扩展。

嵌套集（Nested Sets）

使用两个数字编码 nsleft 和 nsright 表示每个节点：

nsleft 的值小于该节点所有后代的 ID，nsright 的值大于该节点所有后代的 ID（数值与 comment_id 无关）。
建表时需要对树进行一次深度优先遍历，在逐层深入时依次递增地分配 nsleft 的值，在返回时依次递增地分配 nsright 的值。

CREATE TABLE Comments (
  comment_id SERIAL PRIMARY KEY,
  nsleft INTEGER NOT NULL,
  nsright INTEGER NOT NULL,
  comment TEXT NOT NULL
);

nsleft 和 nsright 可用于查找给定节点的后代或祖先：

SELECT c2.*
FROM Comments AS c1
JOIN Comments AS c2 ON c2.nsleft BETWEEN c1.nsleft AND c1.nsright
WHERE c1.comment_id = 4;

SELECT c2.*
FROM Comments AS c1
JOIN Comments AS c2 ON c1.nsleft BETWEEN c2.nsleft AND c2.nsright
WHERE c1.comment_id = 6;

其优点体现在 删除一个非叶子节点时其后代会自动代替被删除的节点，成为其直接祖先节点的直接后代。

尽管每个节点的左右两个值是有序分配，而每个节点也总是和它相邻的父兄节点进行比较，但这种设计不需要保存分层关系。

在删除节点时造成 数值不连续也不会对树结构产生影响，比如计算给定节点的深度然后删除其父节点，再次计算深度时即会少一层：

SELECT c1.comment_id, COUNT(c2.comment_id) AS depth
FROM Comments AS c1
JOIN Comment AS c2 ON c1.nsleft BETWEEN c2.nsleft AND c2.nsright
WHERE c1.comment_id = 7
GROUP BY c1.comment_id;

DELETE FROM Comment WHERE comment_id = 6;

--- 此时再次执行相同的查询会少一层

代价是某些查询操作会变得复杂，比如获取一个节点的直接父亲或者直接后代。

在嵌套集中要访问父亲节点需要：

给定节点 c1 的直接父亲是该节点的一个祖先，且这两个节点之间没有任何其他节点。
使用递归的外连接查询一个节点 x，它既是 c1 的祖先，同时也是另一个 Y 节点的后代。
随后使 Y=x，并继续查询，直到查询返回空（即不存在节点），此时的 Y 便是 c1 的直接父亲节点：

SELECT parent.*
FROM Comment AS c
JOIN Comment AS parent ON c.nsleft BETWEEN parent.nsleft AND parent.nsright
LEFT JOIN Comment AS in_between ON c.nsleft BETWEEN in_between.nsleft AND in_between.nsright AND in_between.nsleft BETWEEN parent.nsleft AND parent.nsright
WHERE c.comment_id = 6 AND in_between.comment_id IS NULL;

对树的插入和移动操作也很复杂：

插入节点时，需要重新计算其相邻兄弟节点、祖先节点和它祖先节点的兄弟，来确保它们的左右值都比这个新节点的左值大。
如果这个新节点是一个非叶子节点，还要检查它的子孙节点。

假设新插入的节点是一个叶子节点，以下语句可以更新每个需要更新的地方：

UPDATE Comments
SET nsleft = CASE WHEN nsleft >= 8 THEN nsleft + 2 ELSE nsleft END,
nsright = nsright+2;
WHERE nsright >= 7

INSERT INTO Comments (nsleft, nsright, comment) VALUES (8, 9, 'OK!')

嵌套集设计能实现简单快速的查询（给定节点的祖先和后代），比操作单独的节点简单，但由于增删改太复杂，总的来说还是不太推荐。

闭包表（Closure Table）

闭包表是我最喜欢的一种设计：

创建另一个表 记录树中所有节点间的关系：将树中任何具有（直接或间接的）“祖先-后代”关系节点对存储在 TreePaths 表中，同时增加一行指向节点自己。
除了能快速查询给定节点的祖先和后代，闭包表能更加简单地维护分层信息。
为了使它更方便地查询直接父亲节点或孩子节点，在 TreePaths 表中增加一个 path_length 字段，对于节点的自身引用 path_length 为 0，到直接子节点 path_length 为 1，以此类推。

CREATE TABLE Comments (
  comment_id SERIAL PRIMARY KEY,
  comment TEXT NOT NULL
);

CREATE TABLE TreePaths (
  ancestor BIGINT UNSIGNED NOT NULL,
  descendant BIGINT UNSIGNED NOT NULL,
  path_length BIGINT UNSIGNED NOT NULL,
  PRIMARY KEY (ancestor, descendant),
  FOREIGN KEY (ancestor) REFERENCES Comments(comment_id),
  FOREIGN KEY (descendant) REFERENCES Comments(comment_id),
);

查询直接子节点很简单：

1
2
3

SELECT *
FROM TreePaths
WHERE ancestor = 4 AND path_length = 1;

搜索所有后代或祖先也只需要关联路径表：

SELECT c.*
FROM Comments AS c
JOIN TreePaths AS t ON c.comment_id = t.descendant
WHERE t.ancestor = 4;

SELECT c.*
FROM Comments AS c
JOIN TreePaths AS t ON c.comment_id = t.descendant
WHERE t.descendant = 4;

插入新的叶子节点时，比如 5 的子节点（ID 为 8），应首先插入一条自己到自己的关系，然后搜索 TreePath 表中后代为 5 的节点，增加该节点和新插入节点的“祖先-后代”关系，包括 5 的自我引用。

INSERT INTO TreePaths (ancestor, descendant)
SELECT t.ancestor, 8
FROM TreePaths AS t
WHERE t.descendant = 5
UNION ALL 
SELECT 8, 8

INSERT INTO Comments (8, 'OK');

该模式下删除数据为逻辑删除（只是删除关系，节点还存在），要删除一个叶子节点，比如 ID 为 7，应删除 TreePaths 表中后代为 7 的行。

1	DELETE FROM TreePaths WHERE descendant = 7;

要删除一棵完整的子树，比如 ID 为 4 的记录及其后代，可删除所有在 TreePath 表中后代为 4 的行：

DELETE FROM TreePaths
WHERE descendant IN (
  SELECT descendant
  FROM TreePaths
  WHERE ancestor = 4
)

要从一个地方移动一棵子树到另一地方相对复杂，但也有固定的算法：

断开这棵子树和它的祖先们的关系。需要找到这棵子树的顶点，删除它的所有子节点和它的所有祖先节点间的关系。
将这棵孤立的树和新节点及它的祖先建立关系。可以使用 CROSS JOIN 创建一个新节点及其祖先 和 这棵孤立的树中所有节点 间的笛卡儿积来建立所有需要的关系。

DELETE FROM TreePaths
WHERE descendant IN (
  SELECT descendant
  FROM TreePaths
  WHERE ancestor = 6
) AND ancestor IN (
  SELECT ancestor
  FROM TreePaths
  WHERE descendant = 6 AND ancestor != descendant
);

INSERT INTO TreePaths (ancestor, descendant)
SELECT supertree.ancestor, subtree.descendant
FROM TreePaths AS supertree
CROSS JOIN TreePaths AS subtree
WHERE supertree.descendant = 3 AND subtree.ancestor = 6;

未完待续（结构图解和性能测试）。

总结

邻接表最易于实现，如果数据库支持 WITH 或者 CONNECT BY PRIOR 递归查询，则会更高效（对递归查询性能存疑，有待测试）。
枚举路径可直观展示祖先到后代的路径，但由于不能确保引用完整性，设计上非常脆弱。枚举路径也使数据存储冗余。
嵌套集相对巧妙，但也不能确保引用完整性。在查询性能要求很高而对其他要求一般的场合使用。
闭包表最通用，且允许一个节点属于多棵树。其要求额外的表存储关系，使用空间换时间的方案，减少操作过程中由冗余计算造成的消耗。

参考

Bill Karwin. SQL Antipatterns [M]. Pragmatic Bookshelf, 2010.

Next Post

《DDIA》阅读笔记（五）：数据复制（单主节点）
Previous Post

《DDIA》阅读笔记（三）：数据存储与检索

CATALOG

1. 树形表结构设计总结