树型结构的四种建模方法

yshengyong 贡献于2017-11-30

作者 Yang  创建于2015-02-28 03:13:00   修改者Yang  修改于2015-02-28 03:16:00字数4296

文档摘要:
关键词:

树型结构的四种建模方法 对于组织架构中的员工层次关系我们应该怎么建模呢?   如下图所示:   此类结构通常有两个主要特点: 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都很简单,一次自连接就解决了: 1、 [sql] view plaincopyprint? 1. select par.employee_id,par.employee_name    2. from employees par,employees self   3. where self.parent_id=par.employee_id   4. and self.employee_id=3201     2、  [sql] view plaincopyprint? 1. select child.employee_id,child.employee_name    2. from employees child,employees self    3. where child.parent_id=self.employee_id    4. and self.employee_id=1010     但问题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级), 性能及可扩展性将是一个很大的问题。   那怎么办呢?一时间好像看起来别无他法啊。 好消息是使用Oracle 10g及以上或者SQL Server 2005及以上的朋友可以直接使用数据库特有的SQL特性来解决这个问题了。 例如在Oracle中可以使用层次查询 [sql] view plaincopyprint? 1. select EMPLOYEE_ID, employee_name   2.   from employees    3.  start with employee_id = 1   4.  connect by  prior employee_id = parent_id     那使用MySQL或者其不支持层次查询的数据库怎么办呢?难道只能用前面两种笨方法? 答案是否定的,你需要重新设计你的表模型。     How to design?   方案二(Path Enumeration) CREATE TABLE Employees_Path( employee_id int, employee_name varchar2(100), path varchar2(1000) ); 此种方案借助了unix文件目录的思想,如下图所示:   我们需要做的就是正确的维护这个PATH值,现在如果我们要查询任意领导(比如Michele)的所有下属就只需要这样即可: [sql] view plaincopyprint? 1. select * from Employees_Path where path like '/1/_%'   同样的,如果我们需要查询任意员工(比如Chris)的所有领导也只需要这样即可: [sql] view plaincopyprint? 1. select * from Employees_Path where '/1/2/5/' like path||'%' and path<>'/1/2/5/'     缺点: 1、PATH值由程序来维护,无法在数据库一级确保数据的有效性 2、当树的层级太深有可能会超过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的所有下属员工,我们可以这样: [sql] view plaincopyprint? 1. select *   2.   from EMPLOYEES_NESTEDSETS par,    3.   EMPLOYEES_NESTEDSETS child   4.  where child.nsleft > par.nsleft   5.    and child.nsleft < par.nsright   6.    and par.EMPLOYEE_NAME = 'Helen Mayes'   那如果我们要查找Helen Mayes的所有领导呢? [sql] view plaincopyprint? 1. select *   2.   from EMPLOYEES_NESTEDSETS par,    3.   EMPLOYEES_NESTEDSETS child   4.  where child.nsleft > par.nsleft   5.    and child.nsleft < par.nsright   6.    and child.EMPLOYEE_NAME = 'Angela Richards'     Nested Sets这种方案还有一个优点就是,当你删除了一个非叶子节点的时候,该节点的所有子孙节点会自动成为该节点父节点的子孙,并同样满足前面所说的条件。 缺点: 在Adjacency List方案中很好回答的问题,在Nested Sets中却变得困难起来 比如我想要查找任意领导(比如Helen Mayes)的直属下属,在Nested Sets中你需要这样做 [sql] view plaincopyprint? 1. select *   2.   from EMPLOYEES_NESTEDSETS par   3.  inner join EMPLOYEES_NESTEDSETS child   4.     on child.nsleft > par.nsleft   5.    and child.nsleft < par.nsright   6.   left join EMPLOYEES_NESTEDSETS tmp   7.     on child.nsleft > tmp.nsleft   8.    and child.nsleft < tmp.nsright   9.    and tmp.nsleft > par.nsleft   10.    and tmp.nsleft < par.nsright   11.  where par.EMPLOYEE_NAME = 'Helen Mayes'   12.    and tmp.employee_id is null   怎么样,够复杂吧? 其逻辑就是 首先找到Helen Mayes的所有下属,然后在去查找这些下属没有属于Helen Mayes下属的上级.........WTF...........   另外,移动和新增加节点也比较复杂 比如我们要在Helen Mayes和Chris Jones之间插入一名员工Scott,如下图所示     从上图基本上就可以看出来我们要更改的地方了......需要重新生成比新插入节点的nsleft值大的所有节点的nsleft和nsright值 非常复杂......     方案四(Closure Table)   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将树中每个节点与其子孙节点的关系都存储了下来,如下图所示: 注意:每个节点都有一条到其本身的记录,如上表的第一条、第四条、第六条记录 Distance是祖先节点到其本身之间的深度 IS_LEAF用于标识该节点是否为叶子节点     有了这张关系表之后,下面让我们用具体例子来感受其带来的好处   查找某个领导(Helen Mayes)的所有下属员工信息 select * from Employees a, TreePaths b where a.employee_id = b.ancestor_key and a.employee_name = 'Helen Mayes' and b.distance<>0   查找某个领导(Helen Mayes)的所有直属员工信息 select * from Employees a, TreePaths b where a.employee_id = b.ancestor_key and a.employee_name = 'Helen Mayes' and b.distance=1    查找某个员工的所有领导 select * from Employees a, TreePaths b where a.employee_id = b.member_key and a.employee_name = 'Helen Mayes' and b.distance<>0   由于时间的关系(现在已经凌晨1点),其它的关于增删改查的方法请大家自行验证。     结语 四种方案中,通常会结合方案一和方案四来使用(BIEE 11g的父子维就使用的该方案);方案三只适合插入和更新极少,查询占主要的应用;方案二不怎么推荐。

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档