注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

和申的个人主页

专注于java开发,1985wanggang

 
 
 

日志

 
 

采用左右值编码来存储无限分级树形结构的数据库表设计  

2012-09-10 21:44:23|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
采用左右值编码来存储无限分级树形结构的数据库表设计,下面是详细介绍。

  下面我力图用比较简短的文字,少量图表,及相关核心sql语句来描述这种设计方案:

  首先,我们弄一棵树作为例子:

商品
|---食品
|    |---肉类
|    |    |--猪肉 
|    |---蔬菜类 
|          |--白菜 
|---电器 
     |--电视机 
     |--电冰箱

 
采用左右值编码的保存该树的数据记录如下(设表名为tree):
Type_id Name Lft Rgt 
1 商品 1 18 
2 食品 2 11 
3 肉类 3 6 
4 猪肉 4 5 
5 蔬菜类 7 10 
6 白菜 8 9 
7 电器 12 17 
8 电视机 13 14 
9 电冰箱 15 16

 
第一次看见上面的数据记录,相信大部分人都不清楚左值(Lft)和右值(Rgt)是根据什么规则计算出来的,而且,这种表设计似乎没有保存父节点的信息。下面把左右值和树结合起来,请看:
          1商品18
     +---------------------------------------+
                2食品11                                    12电器17
          +-----------------+                     +---------------------+
    3肉类6          7蔬菜类10          13电视机14       15电冰箱16
    4猪肉5           8白菜9
请用手指指着上图中的数字,从1数到18,学习过数据结构的朋友肯定会发现什么吧?对,你手指移动的顺序就是对这棵树的进行先序遍历的顺序。接下来,让我讲述一下如何利用节点的左右值,得到该节点的父节点,子孙节点数量,及自己在树中的层数。
 
假定我们要对节点“食品”及其子孙节点进行先序遍历的列表,只需使用如下一条sql语句:
select * from tree where Lft between 2 and 11 order by Lft asc
查询结果如下:
Type_id Name Lft Rgt 
2 食品 2 11 
3 肉类 3 6 
4 猪肉 4 5 
5 蔬菜类 7 10 
6 白菜 8 9

 
那么某个节点到底有多少子孙节点呢?很简单,子孙总数 =(右值-左值-1)/2 
以节点“食品”举例,其子孙总数=(11-2-1)/ 2 = 4
 
同时,我们在列表显示整个类别树的时候,为了方便用户直观的看到树的层次,一般会根据节点所处的层数来进行相应的缩进,那么,如何计算节点在树中的层数呢?还是只需通过左右值的查询即可,以节点“食品”举例,sql语句如下:
select count(*) from tree where lft <= 2 and rgt >= 11
为了方便列表,我们可以为tree表建立一个视图,添加一个层数列,该类别的层数可以写一个自定义函数来计算。该函数如下: CREATE FUNCTION dbo.CountLayer
(    
    @type_id int
)
RETURNS int
AS
begin
    declare @result int
    set @result=0
    declare @lft int
    declare @rgt int
    if exists (select 1 from tree where type_id=@type_id)
    begin
        select @lft=lft,@rgt=rgt from tree where type_id=@type_id
        select @result = count(*) from tree where lft <= @lft and rgt >= @rgt
    end    
    return @result
end
GO

然后,我们建立如下视图:
CREATE VIEW dbo.TreeView
AS
SELECT type_id, name, lft, rgt, dbo.CountLayer(type_id) AS layer FROM dbo.tree ORDER BY lft
GO
 
给出对于给定某个节点,对该节点及其子孙节点进行先序遍历的存储过程:
CREATE PROCEDURE [dbo].[GetTreeListByNode]
(
    @type_id int --给定节点标识
)
AS
declare @lft int
declare @rgt int
if exists (select 1 from tree where type_id=@type_id)
    begin
        select @lft=lft,@rgt=rgt from tree where type_id=@type_id
        select * from TreeView where lft between @lft and @rgt order by lft asc
    end
go

 
现在,我们使用上面的存储过程来列表节点“食品”及其所有子孙节点,查询结果如下:
Type_id Name Lft Rgt Layer 
2 食品 2 11 2 
3 肉类 3 6 3 
4 猪肉 4 5 4 
5 蔬菜类 7 10 3 
6 白菜 8 9 4

 
 
采用左右值编码的设计方案,在进行类别树的遍历时,由于只需进行2次查询,消除了递归,再加上查询条件都为数字比较,效率极 高,类别树的记录条目越多,执行效率越高。看到这里,相信不少人对这种设计方案有所心动了,下面让我们接着看看如何在这种表结构中实现插入、删除、同层平 移节点(变更同层节点排序)的功能。
 
假定我们要在节点“肉类”下添加一个子节点“牛肉”,该树将变成:
                                     1商品18+2
                      +--------------------------------------------+
                2食品11+2                                  12+2电器17+2
          +-----------------+                                    +-------------------------+
    3肉类6+2   7+2蔬菜类10+2         13+2电视机14+2    15+2电冰箱16+2
    +-------------+ 
4猪肉5  6牛肉7  8+2白菜9+2
 
看完上图相应节点左右值的变化后,相信大家都知道该如何写相应的sql脚本吧?下面我给出相对完整的插入子节点的存储过程:
CREATE PROCEDURE [dbo].[AddSubNodeByNode]
(
    @type_id int,
    @name varchar(50)
)
AS
declare @rgt int
if exists (select 1 from tree where type_id=@type_id)
    begin
       SET XACT_ABORT ON
       BEGIN TRANSACTION
        select @rgt=rgt from tree where type_id=@type_id
        update tree set rgt=rgt+2 where rgt>=@rgt
        update tree set lft=lft+2 where lft>=@rgt
        insert into tree (name,lft,rgt) values (@name,@rgt,@rgt+1)    
        COMMIT TRANSACTION
       SET XACT_ABORT OFF    
    end
go

 
然后,我们删除节点“电视机”,再来看看该树会变成什么情况:
                                            1商品20-2
                       +-----------------------------------+
                2食品13                                14电器19-2
          +-----------------+                
       3肉类8          9蔬菜类12              17-2电冰箱18-2
    +----------+ 
4猪肉5  6牛肉7  10白菜11
 
  相应的存储过程如下:
CREATE PROCEDURE [dbo].[DelNode] 
    @type_id int
AS
declare @lft int
declare @rgt int
if exists (select 1 from tree where type_id=@type_id)
    begin
       SET XACT_ABORT ON
       BEGIN TRANSACTION
        select @lft=lft,@rgt=rgt from tree where type_id=@type_id
        delete from tree where lft>=@lft and rgt<=@rgt
        update tree set lft=lft-(@rgt-@lft+1) where lft>@lft
        update tree set rgt=rgt-(@rgt-@lft+1) where rgt>@rgt
        COMMIT TRANSACTION
       SET XACT_ABORT OFF    
End
 
   注意:因为删除某个节点会同时删除该节点的所有子孙节点,而这些被删除的节点的个数为:(被删节点的右值-被删节点的左值+1)/2,而任何一个节点同 时具有唯一的左值和唯一的右值,故删除作废节点后,其他相应节点的左、右值需要调整的幅度应为:减少(被删节点的右值-被删节点的左值+1)。
 
   最后,让我们看看平移节点“电器”,将其和其所有子孙节点移动到节点“食品”之前后,该树会变成什么情况:
 
             1商品18
                        +-----------------------------------+
                14-12电器17-12                      2+4食品13+4
                                                       +----------------------+                
             15-12电冰箱16-12      3+4肉类8+4      9+4蔬菜类12+4        
                                            +-------------------+ 
                                      4+4猪肉5+4     6+4牛肉7+4 10+4白菜11+4
 
大 家仔细观察一下交换后同层2个节点和其所有子孙节点左右值的变化,可以发现一个明显的规律,那就是,节点“电器”及其所有子孙节点的左右值均减少12,而 节点“食品”及其所有子孙节点的左右值均增加4。而节点“电器”+其子孙节点的数量为2,节点“食品”+其子孙节点的数量为6,这其中有什么联系吗?还记 得我在删除节点的存储过程后面的注释吗?任何一个节点同时具有唯一的左值和唯一的右值。让我们把节点数量*2,正好和节点左右值需要调整的幅度相等。由此 规律,我们可以编写出类似下面的存储过程来实现节点同层前移的功能:
CREATE PROCEDURE [dbo].[MoveNodeUp] 
    @type_id int
AS
declare @lft int
declare @rgt int
declare @layer int
if exists (select 1 from tree where type_id=@type_id)
    begin
       SET XACT_ABORT ON
       BEGIN TRANSACTION
        select @lft=lft,@rgt=rgt,@layer=layer from TreeView where type_id=@type_id
        if exists (select * from TreeView where rgt=@lft-1 and layer=@layer)
           begin
               declare @brother_lft int
               declare @brother_rgt int
               select @brother_lft=lft,@brother_rgt=rgt from TreeView where rgt=@lft-1 and layer=@layer
               update tree set lft=lft-(@brother_rgt-@brother_lft+1) where lft>=@lft and rgt<=@rgt
               update tree set lft=lft+(@rgt-@lft+1) where lft>=@brother_lft and rgt<=@brother_rgt
               update tree set rgt=rgt-(@brother_rgt-@brother_lft+1) where rgt>@brother_rgt and rgt<=@rgt
               update tree set rgt=rgt+(@rgt-@lft+1) where lft>=@brother_lft+(@rgt-@lft+1) and rgt<=@brother_rgt
           end
        COMMIT TRANSACTION
       SET XACT_ABORT OFF    
    end
 
  注意:节点的同层平移可以采用临时表来做中介,降低代码的复杂度。不用临时表来处理也行,但是update语句顺序一定要考虑周详。否则,一旦出现bug,对整个类别表的破坏是惊人的,强烈推荐在做上述工作前对类别表进行完整备份。
 
  同层下移的存储过程和同层上移类似,有兴趣的朋友可以自己动手编写体味一下其中的细节,我就不在这里列出来了。
 
  最后,我对上面这种左右值编码实现无限分级类别树的方案做一个总结:
  优点:在消除递归的前提下实现了无限分级,而且查询条件是基于整形数字比较的,效率很高。可以进行先序列表,添加,修改,删除,同层平移等常规操作,基本满足需求。
   缺点:由于这种左右值编码的方式和常见的阿拉伯数字直观排序不同,再加上节点在树中的层次,顺序不是直观显示出来,而必须通过简单的公式计算后得到,需 要花费一定的时间对其数学模型进行深入理解。而且,采用该方案编写相关存储过程,新增,删除,同层平移节点需要对整个树进行查询修改,由此导致的代码复杂 度,耦合度较高,修改维护的风险较高。

  评论这张
 
阅读(1263)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016