Kyle's Notebook

树形表结构设计总结

Word count: 3.1kReading time: 12 min
2021/01/01

树形表结构设计总结

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

  • 用户权限管理

  • 企业组织架构

  • 论坛网站评论功能

  • ……

以用户评论功能为例,其业务场景是:

  • 用户可以发表多条评论。

  • 用户可以对其他用户的评论进行回复。

  • 用户可以对其他用户的回复进行回复。

  • 用户删除评论或回复后,所有对其回复(及其子级)的回复都会被级联删除。

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

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

邻接表(Adjacency List)

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

1
2
3
4
5
6
CREATE TABLE Comments (
comment_id SERIAL PRIMARY KEY,
parent_id BIGINT UNSIGNED,
comment TEXT NOT NULL,
FOREIGN KEY (parent_id) REFERENCES Comments(comment_id)
);

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

1
2
3
4
5
6
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 则这种情况能有所缓解)。

  • 难以使用聚合函数(比如 COUNTSUMMAXMIN 等)。

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

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

解决方法:

  • 不使用外键约束,但需要配合其他方法处理迷失节点,尽可能少产生零散数据。

  • 可以使用 触发器 或指定外键模式为 ON DELETE CASCADE 实现 级联删除,清理整棵子树。

  • 如果删除非叶子节点(并提升其子节点),或者移动子节点到另一个子节点,则需要先修改其 parent_id 再删除:

1
2
3
4
5
6
7
8
9
10
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 标准)的支持,能有效解决这种问题:

1
2
3
4
5
6
7
8
9
10
11
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 WITHCONNECT 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,并保存为每个节点的属性,能很巧妙地解决了邻接表 从树中获取一个给定节点的所有祖先的开销很大 的问题。

1
2
3
4
5
6
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

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

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

  • 复制一份要插入节点的逻辑上的父亲节点的路径,将这个新节点的 ID 追加到路径末尾。

  • 如果 ID 是在插入时自动生成的,可能需要先插入这条记录,再获取这条记录的 ID,并更新它的路径。

1
2
3
4
5
6
7
8
9
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)

使用两个数字编码 nsleftnsright 表示每个节点:

  • nsleft 的值小于该节点所有后代的 ID,nsright 的值大于该节点所有后代的 ID(数值与 comment_id 无关)。

  • 建表时需要对树进行一次深度优先遍历,在逐层深入时依次递增地分配 nsleft 的值,在返回时依次递增地分配 nsright 的值。

1
2
3
4
5
6
CREATE TABLE Comments (
comment_id SERIAL PRIMARY KEY,
nsleft INTEGER NOT NULL,
nsright INTEGER NOT NULL,
comment TEXT NOT NULL
);

nsleftnsright 可用于查找给定节点的后代或祖先:

1
2
3
4
SELECT c2.*
FROM Comments AS c1
JOIN Comments AS c2 ON c2.nsleft BETWEEN c1.nsleft AND c1.nsright
WHERE c1.comment_id = 4;
1
2
3
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;

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

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

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

1
2
3
4
5
6
7
8
9
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 的直接父亲节点:

1
2
3
4
5
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;

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

  • 插入节点时,需要重新计算其相邻兄弟节点、祖先节点和它祖先节点的兄弟,来确保它们的左右值都比这个新节点的左值大。

  • 如果这个新节点是一个非叶子节点,还要检查它的子孙节点。

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

1
2
3
4
5
6
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,以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
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;

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

1
2
3
4
5
6
7
8
9
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 的自我引用。

1
2
3
4
5
6
7
8
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 的行:

1
2
3
4
5
6
DELETE FROM TreePaths
WHERE descendant IN (
SELECT descendant
FROM TreePaths
WHERE ancestor = 4
)

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

  • 断开这棵子树和它的祖先们的关系。需要找到这棵子树的顶点,删除它的所有子节点和它的所有祖先节点间的关系。

  • 将这棵孤立的树和新节点及它的祖先建立关系。可以使用 CROSS JOIN 创建一个新节点及其祖先这棵孤立的树中所有节点 间的笛卡儿积来建立所有需要的关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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.
CATALOG
  1. 1. 树形表结构设计总结
    1. 1.1. 邻接表(Adjacency List)
      1. 1.1.1. 递归查询(Recursive Query)
    2. 1.2. 枚举路径(Path Enumeration)
    3. 1.3. 嵌套集(Nested Sets)
    4. 1.4. 闭包表(Closure Table)
    5. 1.5. 总结
    6. 1.6. 参考