03.单纯的树

单纯的树

目的

分层存储与查询

存在递归关系的数据很常见，数据常会像树或者以层级方式组织。在层级数据中，你可能需要查询与整个集合或其子集相关的特定对象
例如下述树形数据结构

组织架构图
在组织架构中每个职员有一个经理，在树形结构中表现为职员父节点。同时，经理也是一个职员

话题型讨论
树形结构也能用来表示回复评论的评论链。在这种树中，评论的子节点是它的回复

反模式

总是依赖父节点

常见的设计方式，在表中增加parent_id字段。这样的设计叫做邻接表

邻接表查询树

Comments表ddl语句

CREATE TABLE Comments(
comment_id SERIAL PRIMARY  KEY ,
parent_id BIGINT UNSINGED,
bug_id BIGINT UNSINGED NOT NULL,
author BIGINT UNSINGED NOT NULL,
comment_date DATETIME NOT NULL,
comment TEXT NOT NULL,
FOREIGN KEY (parent_id) REFERENCES Comments(comment_id),
FOREIGN KEY (bug_id) REFERENCES Bugs(bug_id),
FOREIGN KEY (author) REFERENCES Accounts(account_id)
)

虽然如此多的程序员会将邻接表作为默认的解决方案，但是它仍然有可能成为一个反模式。
原因在于它无法完成在树中查找一个节点的所有后代，但是你可以使用一个关联查询来获取一条评论和它的直接后代。
如下SQL

-- 这个查询只能查询两层的数据，查询三层或者四层依次类推，JOIN Comments 表
SELECT c1.*,c2.* FROM Comments c1 LEFT JOIN Comments c2 ON c2.parent_id = c1.comment_id

这种方式的查询很笨拙，也不优雅，因为伴随着逐渐增减的后代，必须同等的增加联结查询的列，这使得执行一个聚合函数很费劲。

程序员普遍采用邻接表的设计方案，但是不会采用上述的方式写SQL查询树。而是在程序中查询出来所有的数据，然后
通过程序来组装成树结构的数据来使用。这种方式效率不高，因为我们有可能只需要一棵子树，我们不得不把所有的数据
查询出来，然后组装我们需要的子树。

邻接表维护树

无可否认，使用邻接表也有它的优点，比如增加一个叶子节点很方便

INSERT INTO Comments (bug_id,parent_id,author,comment) VALUES (123,7,'aaa','bbb')

修改一个节点也很方便

UPDATE Comments SET parent_id = 3 WHERE comment_id = 6

但是删除一个节点很麻烦，如果需要删除一棵子树，你不得不执行多次查询来找到所有的后代节点，然后从最低级别开始
删除这些节点以满足外键完整性。

如何识别反模式

如果你听到以下声音，有可能就使用了反模式

1. 我们树结构要支持多少层
2. 我总是害怕接触哪些管理树结构代码
3. 我需要一个脚本来定时清理树中的孤立节点数据

合理使用反模式

某些情况下，在应用程序中使用邻接表设计可能正好适用，邻接表的优势在于很方便获取直接父子节点，也很容易插入新
的节点。如果邻接表的优势正好是你需求，那么你使用它没有问题。

解决方案

路径枚举

邻接表的缺点之一就是从树中获取一个给定节点的所有祖先的开销很大。路径枚举的设计通过将所有的祖先信息联合成
一个字符串，并保存为每个节点的一个属性。

Comments表ddl语句

CREATE TABLE Comments(
comment_id SERIAL PRIMARY  KEY ,
path VARCHAR (1000),
bug_id BIGINT UNSINGED NOT NULL,
author BIGINT UNSINGED NOT NULL,
comment_date DATETIME NOT NULL,
comment TEXT NOT NULL,
FOREIGN KEY (parent_id) REFERENCES Comments(comment_id),
FOREIGN KEY (bug_id) REFERENCES Bugs(bug_id),
FOREIGN KEY (author) REFERENCES Accounts(account_id)
)

在Comments表中，我们使用varchar的path代替parent_id字段，这个path字段所存储的内容为当前节点的最顶层的
祖先到它自己的序列，就像unix的路径一样，你甚至可以使用’/'作为路径中的分隔符。

示例数据：

你可以通过比较每个节点路径来查询一个节点的祖先。比如，要找到评论#7-路径是1/4/6/7/的祖先，sql可以这样写

-- 这个sql的查询语句会匹配的路径为1/4/6/%、1/4/%以及1/%的节点，而这些节点都是评论#7的祖先
SELECT * FROM Comments AS c WHERE '1/4/6/7/' LIKE c.path || '%'

同时还可以通过将like关键字两边的参数互换，来查询一个给定节点的的所有后代，如下sql

-- 这个sql的查询语句会匹配的路径为1/4/5/、1/4/6/以及1/4/6/7/的节点，而这些节点都是评论#4的后代
SELECT * FROM Comments AS c WHERE c.path LIKE '1/4/' || '%'

如果要计算从评论#4扩展出的所有评论中每个用户的评论数量，sql如下

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

插入一个节点也可以像使用邻接表一样地简单。可以插入一个叶子节点而不用修改任何其他
的行。你所需要做的只是复制一份要插入节点的逻辑上的父亲节点的路径，并将这个新节点的 ID
追加到路径末尾就行了。如果这个 ID 是在插入时自动生成的，你可能需要先插入这条记录，然
后获取这条记录的 ID，并更新它的路径。比如，你使用的是 MySQL，它的内置函数
LAST_INSERT_ID()会返回当前会话的最新一条插入记录的 ID，通过调用这个函数，便可以获得
你所需要的 ID，然后就可以通过新节点的父亲节点来获取完整的路径了。sql如下

INSERT INTO Comments(author,comment) VALUES ('ollie','good job!')

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

总结

路径枚举有一个很明显的缺点，就是path字段的长度无论设置为多长，都存在长度的限制，因此并不能支持树结构的无限扩展

嵌套集

嵌套集解决方案是存储子孙节点的相关信息，而不是节点的直接祖先，我们使用两个数字来编码每个节点，从而表示这
一信息，可以将这两个数字称为nsleft和nsright

Comments表ddl语句

CREATE TABLE Comments(
comment_id SERIAL PRIMARY  KEY ,
nsleft INTEGER NOT NULL,
nsright INTEGER NOT NULL,
bug_id BIGINT UNSINGED NOT NULL,
author BIGINT UNSINGED NOT NULL,
comment_date DATETIME NOT NULL,
comment TEXT NOT NULL,
FOREIGN KEY (parent_id) REFERENCES Comments(comment_id),
FOREIGN KEY (bug_id) REFERENCES Bugs(bug_id),
FOREIGN KEY (author) REFERENCES Accounts(account_id)
)

每个节点通过如下的方式确定 nsleft 和 nsright 的值：nsleft 的数值小于该节点所有后代的 ID，
同时 nsright 的值大于该节点所有后代的 ID。这些数字和 comment_id 的值并没有任何关联。
确定这三个值（nsleft，comment_id，nsrigh）的简单方法是对树进行一次深度优先遍历，
在逐层深入的过程中依次递增地分配 nsleft 的值，并在返回时依次递增地分配 nsright 的值。

一旦你为每个节点分配了这些数字，就可以使用它们来找到给定节点的祖先和后代。比如，
可以通过搜索哪些节点的 ID 在评论#4 的 nsleft 和 nsright 范围之间来获取评论#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

通过搜索评论#6 的 ID 在哪些节点的 nsleft 和 nsright 范围之内，可以获取评论#6 及其所
有祖先：

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

使用嵌套集设计的主要优势便是，当你想要删除一个非叶子节点时，它的后代会自动地代替
被删除的节点，成为其直接祖先节点的直接后代。尽管每个节点的左右两个值在示例图中是有序
分配，而每个节点也总是和它相邻的父兄节点进行比较，但嵌套集设计并不必须保存分层关系。
因而当删除一个节点造成数值不连续时，并不会对树的结构产生任何影响。

总结

如果简单快速查询是整个程序中最重要的部分，那么嵌套集是最佳的选择。然而，嵌套集的插入和移动节点是比较复杂
的，因为需要重新分配左右值，如果你的应用程序需要频繁的插入、删除节点，那么嵌套集可能不合适。

闭包表

闭包表是解决分级存储的一个简单而优雅的解决方案，它记录了树中所有节点的关系，而不仅仅只有那些直接的父子关系

Comments(评论)表ddl语句

CREATE TABLE Comments(
comment_id SERIAL PRIMARY  KEY ,
bug_id BIGINT UNSINGED NOT NULL,
author BIGINT UNSINGED NOT NULL,
comment_date DATETIME NOT NULL,
comment TEXT NOT NULL,
FOREIGN KEY (bug_id) REFERENCES Bugs(bug_id),
FOREIGN KEY (author) REFERENCES Accounts(account_id)
)

额外创建一张表TreePaths，它包含两列，每一列都是一个指向Comments中comment_id的外键

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

我们不在使用Comments表来存储树的结构，而是将树中任何具有祖先-后代关系的节点对都存储在TreePaths表的一行中，即使这
两个节点之间不是直接的父子关系，同时，我们还增加一行指向节点自己。

通过TreePaths表来获取祖先和后代比使用嵌套集更加直接。

查询

例如获取评论#4的后代，只需要在TreePaths表中搜索祖先是评论#4的行就可以了。sql如下：

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

例如要获取评论#6 的所有祖先，只需要在 TreePaths 表中搜索后代为评论#6 的行就可以了。sql如下：

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

新增

要插入一个新的叶子节点，比如评论#5的一个子节点，应首先插入一条自己到自己的关系，然后搜索TreePaths表中后代
是评论#5的节点，增加该节点和新插入节点的’祖先-后代’关系（包括评论#5的自我引用）

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

删除一个节点

要删除一个叶子节点，比如评论#7,应删除所有TreePaths表中后代为评论#7的行：

DELETE FROM TreePaths WHERE descendant = 7

删除一个子树

要删除一棵完整的子树，比如评论#4和它所有的后代，可删除所有在TreePaths表中后代为#4的行，以及哪些以评论#4
的后代为后代的行

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

请注意，如果你删除了 TreePahts 中的一条记录，并不是真正删除了这条评论。这对于评论
系统这个例子来说可能很奇怪，但它在其他类型的树形结构的设计中会变得比较有意义。比如在
产品目录的分类或者员工组织架构的图表中，当你改变了节点关系的时候，并不是真地想要删除
一个节点。我们把关系路径存储在一个分开独立的表中，使得设计更加灵活。

移动子树

要从一个地方移动一棵子树到另一地方，首先要断开这棵子树和它的祖先们的关系，
所需要做的就是找到这棵子树的顶点，删除它的所有子节点和它的所有祖先节点间的关系。比如将评论#6
从它现在的位置（评论#4 的孩子）移动到评论#3 下，首先做如下的删除（确保别把评论#6 的自我引用删掉）。
sql如下：

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)

查询评论#6 的祖先（不包含评论#6 自身），以及评论#6 的后代（包括评论#6 自身），然后删
除它们之间的关系，这将正确地移除所有从评论#6 的祖先到评论#6 和它的后代之间的路径。换
言之，这就删除了路径(1, 6)、(1,7)、(4, 6)和(4, 7)，并且它不会删除(6, 6) 或 (6, 7)。

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

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

这样就创建了评论#3 及它的所有祖先节点到评论#6 及其所有后代之间的路径。因此，新的路
径是：(1, 6)、(2, 6)、(3, 6)、(1, 7)、(2, 7)、(3, 7)。同时，评论#6 为顶点的这棵子树就成为了评论#3的
后代。笛卡儿积能创建所有需要的路径，即使这棵子树的层级在移动过程中发生了改变。

闭包表的设计比嵌套集更加地直接，两者都能快捷地查询给定节点的祖先和后代，但是闭包
表能更加简单地维护分层信息。这两个设计都比使用邻接表或者路径枚举更方便地查询给定节
点的直接后代和父代。

优化

然而，你可以优化闭包表来使它更方便地查询直接父亲节点或子节点：在 TreePaths 表中增
加一个 path_length 字段。一个节点的自我引用的 path_length 为 0，到它直接子节点的
path_length 为 1，再下一层为 2，以此类推。查询评论#4 的子节点就变得很直接：

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

总结

每种设计都各有优劣，如何选择设计依赖于应用程序中哪些操作最需要性能上的优化。文章来源地址https://www.toymoban.com/news/detail-833977.html

1. 邻接表是最方便的设计，并且很多软件开发者都了解它
2. 枚举路径能够很直观展示出祖先到后代之间的路径，但同时由于它不能确保引用完整性，使得这个设计非常脆弱。枚举路径也使得数据的存储变得冗余
3. 嵌套集是一个聪明的解决方案，最好在一个查询性能要求很高而对其他需求要求一般的场合来使用它。
4. 闭包表是最通用的设计，并且本章所描述的设计中只有它能允许一个节点属于多棵树。它要求一张额外表来存储关系，使用空间换时间的思路减少冗余的计算所造成的消耗

到了这里，关于03.单纯的树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！