前言
最近项目在换数据库，从sqlserver转到mysql，目前正在准备阶段，可以预见一些问题。比如mysql中没有一些复杂的函数；这使得需要重写一些数据库语句，甚至要改表结构。
递归树查询是一个其中问题，mysql中没有with..来查询其中子孙节点，所以需要对其进行改造。
继承关系设计(原来设计)
表结构：
| 名称 | 类型 | 备注 |
|---|---|---|
| id | int | PK |
| parent_id | int | 父节点id |
| name | varchar(255) | 名称 |
以下是一些实例数据：
tree-data.png
我们首先会想到如上的设计" 这样的设计符合第三范式" 能正确的表达菜单的树状结构且没有冗余数据"，但在实际开发中这种设计及其不方便，先来看查询一个节点的所有后代，下面是两层的数据的SQL语句：
SELECT t1.*
FROM tree AS t1 LEFT JOIN tree AS t2
ON t1.id = t2.parent_id
where t2.parent_id=1
显然，每需要查多一层，就需要联结多一次表。SQL查询的联结次数是有限的，因此不能无限深的获取所有的后代。
为了实现这样的层次关系的树，就需要多次检索，通过父节点检索出子节点后，再根据检索出的子节点进行检索，以此类推直至到叶子节点，这样的效率对于少量的数据影响还能忍受，但是当树节点扩充到数十条甚至上百条记录后，单单一次菜单显示就要检索数十次该表，整个程序的运行效率就会非常差。
所以sqlserver2005后就提供了函数with进行递归查询，但是MySQL并没有类似的函数，所以只能自定义函数来实现，或者用一个临时数组或临时表，然后在内存中遍历结果，这样就可以不用检索那么多次数据库了，但这仅仅是把沉重的运算负担从一个地方转移到另一个地方，没有从根本上解决问题。
下面是用MySQL写的自定义查询所有子节点函数：
CREATE FUNCTION queryChildrenTree(treeId INT)
RETURNS VARCHAR(4000)
BEGIN
DECLARE sTemp VARCHAR(4000);
DECLARE sTempChd VARCHAR(4000);
SET sTemp='$';
SET sTempChd = CAST(treeId AS CHAR);
WHILE sTempChd IS NOT NULL DO
SET sTemp= CONCAT(sTemp,',',sTempChd);
SELECT GROUP_CONCAT(id) INTO sTempChd FROM tree WHERE FIND_IN_SET(parent_id,sTempChd)>0;
END WHILE;
RETURN sTemp;
END;
select * from tree where FIND_IN_SET(parent_id, queryChildrenTree(1))
路径枚举
路径枚举的设计是指通过将所有祖先的信息联合成一个字符串，并保存为每个节点的一个属性。
路径枚举是一个由连续的直接层级关系组成的完整路径。如"/home/article/details",其中home是article的直接父亲，这也就意味着home是details的祖先。
接下来对上面表进行改造：
表结构（tree1）：
| 名称 | 类型 | 备注 |
|---|---|---|
| id | int | PK |
| parent_id | int | 父节点id |
| name | varchar(255) | 名称 |
| path | varchar(255) | 路径 |
以下是一些实例数据：
tree1-data.png
路径枚举的优点：可以很方便的查询所有的祖先和后代。
--查询所有的子节点（包括孙子）
select * from tree1 where path like '0/1%'
后代
select * from tree1 where '0/1/4/6' like CONCAT(path,'%')
祖先
路径枚举的缺点也很明显：
- 数据库不能确保路径的格式总是正确或者路径中的节点确实存在(中间节点被删除的情况，没外键约束)。
- 要依赖高级程序来维护路径中的字符串，并且验证字符串的正确性的开销很大。
- VARCHAR的长度很难确定。无论VARCHAR的长度设为多大，都存在不能够无限扩展的情况。
闭包表
闭包表需要额外创建了一张TreePaths的表(目的：空间换取时间)，它记录了表中所有的节点关系，并不仅仅是直接的父子关系。它包含两列，每一列都是一个指向tree3中的treeId的外键。
这种设计主表已经不再维护节点之间的关系，都是通过外表来维护节点的关系，下面是两个表的结构：
主表结构：
| 名称 | 类型 | 备注 |
|---|---|---|
| id | int | PK |
| name | varchar(255) | 名称 |
关系记录表：
| 名称 | 类型 | 备注 |
|---|---|---|
| id | int | pk |
| ancestor | int | 祖先id |
| descendant | int | 后代id |
| dept | int | 深度 |
主表数据：
tree2-data
关联表数据：
treePath-data
查询所有后代节点：
SELECT t.*,tp.dept FROM tree2 AS t
INNER JOIN TreePath tp on t.id = tp.descendant
WHERE tp.ancestor = 2
结果如图：
后代
查询所有祖先节点：
SELECT c.* FROM Comment AS c
INNER JOIN TreePaths t on c.CommentId = t.ancestor
WHERE t.descendant = 6
结果如图：
祖先
插入数据：
先插入主表的数据，然后增加该节点与其关联的"祖先-后代"关系。
-- 插入主表数据
insert into tree2 values(8,'haha8')
-- 插入关联数据
insert INTO TreePath(ancestor,descendant,dept)
select t.ancestor,8,(t.dept+1)
from TreePath AS t
where descendant = 5
union all
SELECT 8,8,0
删除叶子节点：
删除指定节点关联的treePath，然后删除tree数据
DELETE FROM TreePath WHERE descendant = 8
删除子树
DELETE FROM treePath
where descendant
in(SELECT descendant FROM treePath WHERE ancestor = 6)
网友评论