数据库表设计-邻接表,左右值,物化路径,闭包表

邻接表模型

每个节点都有一个指向其父节点的指针。顶层节点没有父节点。

比如区域表（国、省、市、区）：

CREATE TABLE Area (
[id] [int]  NOT NULL,
[name] [nvarchar]  (50) NULL,
[parent_id] [int]  NULL,
[type] [int]  NULL );

parent_id 是父ID，省的父ID是国，市的父ID 为省，以此类推。

左右值模型(嵌套集)

嵌套集解决方案是存储子孙节点的相关信息，而不是节点的直接祖先。我们使用两个数字来编码每个节点，从而表示这一信息，可以将这两个数字称为nsleft 和 nsright。
每个节点通过如下的方式确定nsleft 和nsright 的值：nsleft的数值小于该节点所有后代ID，同时nsright 的值大于该节点的所有后代的ID。这些数字和comment_id 的值并没有任何关联。

确定这三个值（nsleft，comment_id，nsright）的简单方法是对树进行一次深度优先遍历，在逐层深入的过程中依次递增地分配nsleft的值，并在返回时依次递增地分配nsright的值。得到数据如下:

一旦你为每个节点分配了这些数字，就可以使用它们来找到指定节点的祖先和后代。比如搜索评论#4及其所有后代，可以通过搜索哪些节点的ID在评论 #4 的nsleft 和 nsright 范围之间，例：

1 2	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及其所有祖先，可以通过搜索#6的ID在哪些节点的nsleft 和 nsright 范围之间，例：

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

使用嵌套集设计的主要优势是，当你想要删除一个非叶子节点时，它的后代会自动替代被删除的节点，成为其直接祖先节点的直接后代。就是说已经自动减少了一层。

然而，某些在邻接表的设计中表现得很简单的查询，比如获取一个节点的直接父亲或者直接后代，在嵌套集设计中会变得比较复杂。在嵌套集中，如果需要查询一个节点的直接父亲，我们会这么做，比如要找到评论#6 的直接父亲：

SELECT parent.* FROM comments AS c JOIN comments AS parent ON c.nsleft BETWEEN parent.nsleft AND parent.nsright
LEFT OUTER JOIN comments 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;

对树进行操作，比如插入和移动节点，使用嵌套集会比其它设计复杂很多。当插入一个新节点时，你需要重新计算新插入节点的相邻兄弟节点、祖先节点和它祖先节点的兄弟，来确保他们的左右值都比这个新节点的左值大。同时，如果这个新节点时一个非叶子节点，你还要检查它的子孙节点。

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

物化路径模型(路径枚举)

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

你可以通过比较每个节点的路径来查询一个节点祖先。比如：要找到评论#7，路径是 1/4/5/7一的祖先，可以这么做：

1	SELECT * FROM comments AS c WHERE '1/4/5/7' LIKE CONCAT(c.path,'%');

这句话查询语句会匹配到路径为 1/4/5/%，1/4/% 以及 1/% 的节点，而这些节点就是评论#7的祖先。

同时还可以通过将LIKE 关键字两边的参数互换，来查询一个给定节点的所有后代。比如查询评论#4，路径path为 ‘1/4’ 的所有后代，可以使用如下语句：

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

这句查询语句所有能找到的后台路径分别是：1/4/5、1/4/5/6、1/4/5/7。

一旦你可以很简单地获取一棵子树或者从子孙节点到祖先节点的路径，你就可以很简单地实现更多的查询，如查询一颗子树所有节点上值的总和。
插入一个节点也可以像使用邻接表一样地简单。你所需要做的只是复制一份要插入节点的父亲节点路径，并将这个新节点的ID追加到路径末尾即可。

路径枚举也存在一些缺点，比如数据库不能确保路径的格式总是正确或者路径中的节点确实存在。依赖于应用程序的逻辑代码来维护路径的字符串，并且验证字符串的正确性开销很大。无论将varchar 的长度设定为多大，依旧存在长度的限制，因而并不能够支持树结构无限扩展。

闭包表模型

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

在设计评论系统时，我们额外创建了一个叫 tree_paths 表，它包含两列，每一列都指向 comments 中的外键。

CREATE TABLE `comments` (
  `comment_id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `bug_id` bigint(20) unsigned NOT NULL,
  `author` varchar(60) NOT NULL,
  `comment_date` datetime NOT NULL,
  `comment` text NOT NULL,
  PRIMARY KEY (`comment_id`),
  KEY `bug_id` (`bug_id`)
);

CREATE TABLE `treepaths` (
  `ancestor` bigint(20) unsigned NOT NULL,
  `descendant` bigint(20) unsigned NOT NULL,
  PRIMARY KEY (`ancestor`,`descendant`),
  KEY `descendant` (`descendant`)
);

INSERT INTO `comments` VALUES (1, 1, 'Fran', '2021-06-16 19:27:22', '这个Bug的成因是什么');
INSERT INTO `comments` VALUES (2, 1, 'Ollie', '2021-06-16 19:29:26', '我觉得是一个空指针');
INSERT INTO `comments` VALUES (3, 1, 'Fran', '2021-06-16 19:30:00', '不，我查过了');
INSERT INTO `comments` VALUES (4, 1, 'Kukla', '2021-06-16 19:30:34', '我们需要查无效输入');
INSERT INTO `comments` VALUES (5, 1, 'Ollie', '2021-06-16 19:31:01', '是的，那是个问题');
INSERT INTO `comments` VALUES (6, 1, 'Fran', '2021-06-16 19:31:19', '好，查一下吧');
INSERT INTO `comments` VALUES (7, 1, 'Kukla', '2021-06-16 19:31:41', '解决了');

INSERT INTO `treepaths` VALUES (1, 1);
INSERT INTO `treepaths` VALUES (1, 2);
INSERT INTO `treepaths` VALUES (1, 3);
INSERT INTO `treepaths` VALUES (1, 4);
INSERT INTO `treepaths` VALUES (1, 5);
INSERT INTO `treepaths` VALUES (1, 6);
INSERT INTO `treepaths` VALUES (1, 7);
INSERT INTO `treepaths` VALUES (2, 2);
INSERT INTO `treepaths` VALUES (2, 3);
INSERT INTO `treepaths` VALUES (3, 3);
INSERT INTO `treepaths` VALUES (4, 4);
INSERT INTO `treepaths` VALUES (4, 5);
INSERT INTO `treepaths` VALUES (4, 6);
INSERT INTO `treepaths` VALUES (4, 7);
INSERT INTO `treepaths` VALUES (5, 5);
INSERT INTO `treepaths` VALUES (6, 6);
INSERT INTO `treepaths` VALUES (6, 7);
INSERT INTO `treepaths` VALUES (7, 7);

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

这里以 comment_id 为1 作为例子，当 comment_id 为1 treepaths 需要存储的结构则是表格标红的内容

通过 treepaths 表来获取祖先和后代比使用嵌套集更加地直接。例如要获取评论#4的后代，只需要在 treepaths 表中搜索祖先是评论#4的行就可以了：

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

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

SELECT
	c.* 
FROM
	comments AS c
	JOIN treepaths AS t ON c.comment_id = t.ancestor 
WHERE
	t.descendant = 6;

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

{int} 为新增的 comment_id


INSERT INTO comments (author,comment_date,bug_id, comment) VALUES ('Ollie','2021-01-11', 1,'Good job!');

INSERT INTO treepaths ( ancestor, descendant ) SELECT
t.ancestor,
{int} 
FROM
	TreePaths AS t 
WHERE
	t.descendant = 5 UNION ALL
SELECT
	{int},
	{int};

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

1	DELETE FROM treepaths WHERE descendant = 7;

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

DELETE 
FROM
	treepaths 
WHERE
	descendant IN ( SELECT descendant FROM ( SELECT descendant FROM treepaths WHERE ancestor = 4 ) AS b );

闭包表的设计比嵌套集更加地直接，两者都能快捷地查询给定节点的祖先和后代，但是闭包表能更加简单地维护分层信息。这两个设计都比路径枚举更方便地查询给定节点的直接后代和父代。
然而，你可以优化闭包表来使它更方便地查询直接父亲节点或子节点：在 treepaths 表中增加一个 path_length 字段。一个节点的自我引用的 path_length 为0，到它直接子节点的 path_length 为1，再下一层为2，以此类推。查询评论#4的子节点就变得很直接：

1
2
3

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

总结：

路径枚举 能够很直观地展示出祖先到后代之间的路径，但同时由于它不能确保引用完整性，使得这个设计非常地脆弱。枚举路径也使得数据的存储变得比较冗余。
嵌套集是一个聪明的解决方案——但可能过于聪明了，它不能确保引用完整性。最好在一个查询性能要求很高而对其他需求要求一般的场合来使用它
闭包表是最通用的设计，它要求一张额外的表来存储关系，使用空间换时间的方案减少操作过程中由冗余的计算所造成的消耗。

参考：

数据库表设计（邻接表、路径枚举、嵌套集、闭包表）

层次数据结构的数据表设计

评论表设计 - 路径枚举、嵌套集、闭包表