第14课:无限极分类处理

Mysql身为关系型数据库,对树形结构的数据处理就有点力不从心,而无限极分类是一个非典经典的树形结构
这个时候,就需要一定的算法来解决问题

此类结构通常有两个主要特点:
1、一个孩子有且只有一个父亲
2、树的深度不确定

树型结构的四种建模方法 :

为了解决这种结构,我们一般会建一张下面的表:
方案一(Adjacency List)
CREATE TABLE Employees(
	employee_id int,
	employee_name varchar2(100),
	parent_id int
);
每个员工在Employees表中会有一条记录,并通过parent_id来记录其直属领导的employee_id,这样做很简单明了,但是却存在一些弊端。
考虑如下问题:
1、如何得到某个员工的直属领导?
2、如何得到某个领导的直属下属?
3、如何得到某个领导全部下属(下属的下属)?
问题1、2都很简单,一次自连接就解决了,但问题3呢?
两种人会有两种做法,一种觉得可以在程序里做,把问题2的SQL循环执行最终把结果拼起来就OK了;
一种是觉得我可以使用多次自连接,比如我知道这下领导最多有两级下属,我就可以这样做:
select child.employee_id,child.employee_name,child1.employee_id,child1.employee_name
from employees self  inner join employees child on child.parent_id=self.employee_id
left join employees child1 on child1.parent_id=child.employee_id and
where self.employee_id=1010
上面两种方法看似都可以解决问题,但是别忘了此类树结构的一个很重要的特点,那就是深度的不确定性(就算确定,如果层次很深,20级),
性能及可扩展性将是一个很大的问题

于是,就有了方案二(Path Enumeration)

此种方案借助了unix文件目录的思想,表结构如下所示:
employee_id  employee_name  parent_id   path
1            根目录         0           /1/
2            一级子目录     1           /1/2/
3	     二级子目录     2           /1/2/3/

关键在于用一个path字段来维护层级关系
不过这个算法有个缺点当树的层级太深有可能会超过PATH字段的长度,所以其能支持的最大深度并非无限的

方案三(Nested Sets)
CREATE TABLE EMPLOYEES_NESTEDSETS(
EMPLOYEE_ID INT,
EMPLOYEE_NAME VARCHAR2(100),
NSLEFT INT,
NSRIGHT INT
);
该方案采用深度优先遍历给树中的每个节点分配两个值,分别存在NSLEFT和NSRIGHT中
每个节点左边的的值存放在NSLEFT中,右边的值存放在NSRIGHT中;节点左边的值比该节点的所有子孙节点值都要小,节点右边的值比该节点的所有子孙节点值都要大。
例如Hell Mayes左边的值为2,其比Hell Mayes的所有子孙节点的值都要小(3,4,5,10,6,7,8,9)
Hell Mayes右边的值为11,其比Hell Mayes的所有子孙节点的值都要大(3,4,5,10,6,7,8,9)
有了这个规则之后,如果想要查找某个节点的子孙或都祖先就非常容易了
回到我们前面的题目中来,假设我要查找Helen Mayes的所有下属员工,我们可以这样
select *  
  from EMPLOYEES_NESTEDSETS par,   
  EMPLOYEES_NESTEDSETS child  
 where child.nsleft > par.nsleft  
   and child.nsleft < par.nsright  
   and par.EMPLOYEE_NAME = 'Helen Mayes'
Nested Sets这种方案还有一个优点就是,当你删除了一个非叶子节点的时候,该节点的所有子孙节点会自动成为该节点父节点的子孙,并同样满足前面所说的条件。
缺点:
在Adjacency List方案中很好回答的问题,在Nested Sets中却变得困难起来
比如我想要查找任意领导(比如Helen Mayes)的直属下属,在Nested Sets中你需要这样做
select *  
  from EMPLOYEES_NESTEDSETS par  
 inner join EMPLOYEES_NESTEDSETS child  
    on child.nsleft > par.nsleft  
   and child.nsleft < par.nsright  
  left join EMPLOYEES_NESTEDSETS tmp  
    on child.nsleft > tmp.nsleft  
   and child.nsleft < tmp.nsright  
   and tmp.nsleft > par.nsleft  
   and tmp.nsleft < par.nsright  
 where par.EMPLOYEE_NAME = 'Helen Mayes'  
   and tmp.employee_id is null

方案四(Closure Table)
在方案1的基础上,再多建一个表,用来存储个个级别之间的关联关系
CREATE TABLE Employees(
employee_id int,
employee_name varchar2(100)
);

CREATE TABLE TreePaths (
ancestor_key int,
member_key  int,
Distance int,
is_leaf int
);

Closure Table将树中每个节点与其子孙节点的关系都存储了下来到TreePaths表
Distance是祖先节点到其本身之间的深度
IS_LEAF用于标识该节点是否为叶子节点

查找某个领导(www.godeye.org)的所有下属员工信息
select * from Employees a, TreePaths b where a.employee_id = b.ancestor_key and a.employee_name = 'www.godeye.org' and b.distance<>0

查找某个领导(www.godeye.org)的所有直属员工信息
select * from Employees a, TreePaths b where a.employee_id = b.ancestor_key and a.employee_name = 'www.godeye.org' and b.distance=1

查找某个员工的所有领导
select * from Employees a, TreePaths b where a.employee_id = b.member_key and a.employee_name = 'www.godeye.org' and b.distance<>0

但是这个方案也有一个缺点,因为要新建一个表来存储各个层级之间的关系,如果目录比较深,数据量比较大,这个表会膨胀的很快

在实际应用中,我还是倾向与用方案二,简单实用,同时也解决了问题,方案4虽然完美的解决了问题,但是数据量大的时候就不那么实用