我们在编程开发的过程中可能会遇到这样的需求，多级分类，多级留言评价，多级分销系统，这些系统需求很简单，但是存在无限多的父子关系，是一个典型的迭代关系设计。
对于这个问题，以下给出几个解决方案供大家参考。
一、邻接表设计
我们以留言评价这样的需求为例来设计一个数据结构，在mysql中执行以下sql语句：
CREATE TABLE `Comment` ( `id` int NOT NULL , `pid` int NULL , `words` varchar(255) NULL , PRIMARY KEY (`id`), CONSTRAINT `pidkey` FOREIGN KEY (`pid`) REFERENCES `Comment` (`id`) );1通过上面的sql我们可以发现，pid这个字段指向了本表的id字段，类似于链表的结构，
insert into Comment(id,pid,words) values(1,null,"hello world") ; insert into Comment(id,pid,words) values(2,1,"hello ") ; insert into Comment(id,pid,words) values(3,1,"are you ok ") ; insert into Comment(id,pid,words) values(4,null,"this is good") ; insert into Comment(id,pid,words) values(5,2,"what is your name?") ;好了，现在的数据结构是这样的
pid为null的表示顶级评论
那么怎么一次性迭代查询出多级的数据呢，比如查询父级pid=1的所有子树数据，代码如下：
WITH recursive comment_cte as( select a.id,a.pid,a.words, 1 as tlevel FROM comment as a WHERE a.pid = 1 UNION ALL SELECT c.id,c.pid,c.words, ce.tlevel+1 as tlevel FROM comment AS c INNER JOIN comment_cte AS ce ON c.pid = ce.id ) SELECT * FROM comment_cte查询结果如下：
tlevel为第几层的数据
修改删除也很方便。
二、路径枚举
路径枚举是一个由连续的直接层级关系组成的完整路径。如"/home/account/login",其中home是account的直接父亲，这也就意味着home是login的祖先。
还是有刚才评论的例子，我们用路径枚举的方式来代替邻接表的设计：
CREATE TABLE `Comment2` ( `id` int NOT NULL , `path` varchar(255) NULL , `words` varchar(255) NULL , PRIMARY KEY (`id`) );
先插入一些数据
insert into Comment2(id,path,words) values(1,"1","hello world") ; insert into Comment2(id,path,words) values(2,"1/2","hello ") ; insert into Comment2(id,path,words) values(3,"1/3","hello ") ; insert into Comment2(id,path,words) values(4,"1/2/4","hi ") ;
现在表中数据是这样的
SELECT * FROM Comment2 AS c WHERE c.path LIKE '1/%';
查询结果如下：
一旦我们可以很简单地获取一个子树或者从子孙节点到祖先节点的路径，就可以很简单地实现更多查询，比如计算一个字数所有节点的数量(COUNT聚合函数)。
插入一个节点也可以像和使用邻接表一样地简单。
可以插入一个叶子节点而不用修改任何其他的行。你所需要做的只是复制一份要插入节点的逻辑上的父亲节点路径，并将这个新节点的Id追加到路径末尾就可以了。如果这个Id是插入时由数据库生成的，你可能需要先插入这条记录，然后获取这条记录的Id，并更新它的路径。
路径枚举的缺点:
1、数据库不能确保路径的格式总是正确或者路径中的节点确实存在(中间节点被删除的情况，没外键约束)。2、要依赖高级程序来维护路径中的字符串，并且验证字符串的正确性的开销很大。
3、VARCHAR的长度很难确定。无论VARCHAR的长度设为多大，都存在不能够无限扩展的情况。
路径枚举的设计方式能够很方便地根据节点的层级排序，因为路径中分隔两边的节点间的距离永远是1，因此通过比较字符串长度就能知道层级的深浅。三、嵌套集
嵌套集解决方案是存储子孙节点的信息，而不是节点的直接祖先。我们使用两个数字来编码每个节点，表示这个信息。可以将这两个数字称为nsleft和nsright。
还是以上面的评论作为例子，对于嵌套集的方式表可以设计为：
CREATE TABLE `Comment3` ( `id` int AUTO_INCREMENT , `mleft` int NOT NULL , `mright` int NOT NULL , `words` varchar(255) NULL , PRIMARY KEY (`id`) );
mleft值的确定：mleft的数值小于该节点所有后代的Id。
mright值的确定：mright的值大于该节点所有后代的Id。
我们来新增一些值
insert into Comment3(id,mleft,mright,words) values(1,0,1,"hello world") ;上面的sql就是新增一个父级，id=1，这是一个叶子节点，我们在叶子节点新增一个子，sql为：
LOCK TABLE comment3 WRITE;
SELECT @myLeft := mleft FROM comment3
WHERE id = 1;
UPDATE comment3 SET mright = mright + 2 WHERE mright>@myLeft;
UPDATE comment3 SET mleft = mleft + 2 WHERE mleft>@myLeft;
INSERT INTO comment3(words, mleft, mright) VALUES('hello', @myLeft + 1, @myLeft + 2);
UNLOCK TABLES;那么删除节点的sql为：
LOCK TABLE comment3 WRITE; SELECT @myLeft := mleft, @myRight := mright, @myWidth := mright - mleft + 1 FROM comment3 WHERE id =2; DELETE FROM comment3 WHERE mleft BETWEEN @myLeft AND @myRight; UPDATE comment3 SET mright = mright - @myWidth WHERE mright > @myRight; UPDATE comment3 SET mleft = mleft - @myWidth WHERE mleft > @myRight; UNLOCK TABLES;
删除的节点如果有子节点，会一并删除
嵌套集的优点：
我觉得是唯一的优点了，查询祖先树和子树方便。
例如，通过搜索那些节点的ConmentId在评论4的nsleft与nsright之间就可以获得其及其所有后代：
这种嵌套集的设计还有一个优点，就是当你想要删除一个非叶子节点时，它的后代会自动地代替被删除的节点，称为其直接祖先节点的直接后代。
嵌套集设计并不必须保存分层关系。因此当删除一个节点造成数值不连续时，并不会对树的结构产生任何影响。
嵌套集缺点：
1、查询直接父亲。
在嵌套集的设计中，这个需求的实现的思路是，给定节点c1的直接父亲是这个节点的一个祖先，且这两个节点之间不应该有任何其他的节点，因此，你可以用一个递归的外联结来查询一个节点，它就是c1的祖先，也同时是另一个节点Y的后代，随后我们使y=x就查询，直到查询返回空，即不存在这样的节点，此时y便是c1的直接父亲节点。
比如，要找到评论6的直接父节点：老实说，SQL语句又长又臭，行肯定是行，但我真的写不动了。
2、对树进行操作，比如插入和移动节点。
当插入一个节点时，你需要重新计算新插入节点的相邻兄弟节点、祖先节点和它祖先节点的兄弟，来确保它们的左右值都比这个新节点的左值大。同时，如果这个新节点是一个非叶子节点，你还要检查它的子孙节点。
四、闭包表
CREATE TABLE `Comment4` ( `id` int AUTO_INCREMENT , `words` varchar(255) NULL , PRIMARY KEY (`id`) );父子关系表：
CREATE TABLE `RelaComment` ( `id` int AUTO_INCREMENT , `parentid` int not null , `childid` int not null , PRIMARY KEY (`id`) );
在这种设计中，Comments表将不再存储树结构，而是将书中的祖先-后代关系存储为RelaComment的一行，即使这两个节点之间不是直接的父子关系；同时还增加一行指向节点自己。
insert into Comment4(words) values("hello world") ;
insert into Comment4(words) values("hello ") ;
insert into Comment4(words) values("ok ") ;
insert into Comment4(words) values("all right ") ;
insert into relacomment(parentid,childid) values(1,1) ;
insert into relacomment(parentid,childid) values(2,2)
insert into relacomment(parentid,childid) values(1,2) ;
insert into relacomment(parentid,childid) values(3,3)
insert into relacomment(parentid,childid) values(1,3) ;
insert into relacomment(parentid,childid) values(2,4) ;
insert into relacomment(parentid,childid) values(4,2)
insert into relacomment(parentid,childid) values(1,4) ;
优点：1、查询所有后代节点(查子树)：
SELECT c.* FROM comment4 AS c INNER JOIN relacomment t on c.id = t.childid WHERE t.parentid = 2
SELECT c.* FROM comment4 AS c INNER JOIN relacomment t on c.id = t.parentid WHERE t.childid = 4
3、插入新节点：
要插入一个新的叶子节点，应首先插入一条自己到自己的关系，然后搜索relacomment 表中后代是评论5的节点，增加该节点与要插入的新节点的"祖先-后代"关系。
insert into Comment4(words) values("iam 5")
INSERT INTO relacomment(parentid,childid)
SELECT t.parentid,5
FROM relacomment AS t
WHERE t.childid = 4
UNION ALL
SELECT 5,54、删除叶子节点：
DELETE FROM relacomment WHERE childid= 5
5、删除子树：
DELETE FROM relacomment WHERE descendant IN(SELECT childid FROM relacomment WHERE parentid = 2)
要删除一颗完整的子树，比如评论4和它的所有后代，可删除所有在relacomment表中的后代为4的行，以及那些以评论4的后代为后代的行：
另外，闭包表还可以优化，如增加一个path_length字段，自我引用为0，直接子节点为1，再一下层为2，一次类推，查询直接自子节点就变得很简单。
总结
其实，在以往的工作中，曾见过不同类型的设计，邻接表，路径枚举，邻接表路径枚举一起来的都见过。
每种设计都各有优劣，如果选择设计依赖于应用程序中哪种操作最需要性能上的优化。
1、邻接表是最方便的设计，并且很多软件开发者都了解它。并且在递归查询的帮助下，使得邻接表的查询更加高效。
2、枚举路径能够很直观地展示出祖先到后代之间的路径，但由于不能确保引用完整性，使得这个设计比较脆弱。枚举路径也使得数据的存储变得冗余。
3、嵌套集是一个聪明的解决方案，但不能确保引用完整性，并且只能使用于查询性能要求较高，而其他要求一般的场合使用它。
4、闭包表是最通用的设计，并且最灵活，易扩展，并且一个节点能属于多棵树，能减少冗余的计算时间。但它要求一张额外的表来存储关系，是一个空间换取时间的方案。
{{collectdata}}
网友评论0