该设计方案的优点是:只用一条查询语句即可得到某个根节点及其所有子孙节点的先序遍历。由于消除了递归,在数据记录量较大时,可以大大提高列表效率。但是,这种编码方案由于层信息位数的限制,限制了每层能所允许的最大子节点数量及最大层数。同时,在添加新节点的时候必须先计算新节点的位置是否超过最大限制。
上面的设计方案必须预先设定类别树的最大层数以及最大子节点数,不是无限分级,在某些场合并不能采用,那么还有更完美的解决方案吗?通过 google的搜索,我又探索到一种全新的无递归查询,无限分级的编码方案——左右值。原文的程序代码是用php写的,但是通过仔细阅读其数据库表设计说明及相关的sql语句,我彻底弄懂了这种巧妙的设计思路,并在这种设计中新增了删除节点,同层平移的需求(原文只提供了列表及插入子节点的sql语句)。
下面我力图用比较简短的文字,少量图表,及相关核心sql语句来描述这种设计方案:
首先,我们弄一棵树作为例子:
商品
|---食品
| |---肉类
| | |--猪肉
| |---蔬菜类
| |--白菜
|---电器
|--电视机
|--电冰箱
采用左右值编码的保存该树的数据记录如下(设表名为tree):
第一次看见上面的数据记录,相信大部分人都不清楚左值(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
查询结果如下:
那么某个节点到底有多少子孙节点呢?很简单,子孙总数 =(右值-左值-1)/2
以节点“食品”举例,其子孙总数=(11-2-1)/ 2 = 4
同时,我们在列表显示整个类别树的时候,为了方便用户直观的看到树的层次,一般会根据节点所处的层数来进行相应的缩进,那么,如何计算节点在树中的层数呢?还是只需通过左右值的查询即可,以节点“食品”举例,sql语句如下:
select count(*) from tree where lft <= 2 and rgt >= 11
为了方便列表,我们可以为tree表建立一个视图,添加一个层数列,该类别的层数可以写一个自定义函数来计算。该函数如下:
然后,我们建立如下视图:
给出对于给定某个节点,对该节点及其子孙节点进行先序遍历的存储过程:
现在,我们使用上面的存储过程来列表节点“食品”及其所有子孙节点,查询结果如下:
采用左右值编码的设计方案,在进行类别树的遍历时,由于只需进行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脚本吧?下面我给出相对完整的插入子节点的存储过程:
然后,我们删除节点“电视机”,再来看看该树会变成什么情况:
1商品20-2
+-----------------------------------+
2食品13 14电器19-2
+-----------------+
3肉类8 9蔬菜类12 17-2电冰箱18-2
+----------+
4猪肉5 6牛肉7 10白菜11
相应的存储过程如下:
注意:因为删除某个节点会同时删除该节点的所有子孙节点,而这些被删除的节点的个数为:(被删节点的右值-被删节点的左值+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,正好和节点左右值需要调整的幅度相等。由此规律,我们可以编写出类似下面的存储过程来实现节点同层前移的功能:
同层下移的存储过程和同层上移类似,有兴趣的朋友可以自己动手编写体味一下其中的细节,我就不在这里列出来了。
最后,我对上面这种左右值编码实现无限分级类别树的方案做一个总结:
优点:在消除递归的前提下实现了无限分级,而且查询条件是基于整形数字比较的,效率很高。可以进行先序列表,添加,修改,删除,同层平移等常规操作,基本满足需求。
缺点:由于这种左右值编码的方式和常见的阿拉伯数字直观排序不同,再加上节点在树中的层次,顺序不是直观显示出来,而必须通过简单的公式计算后得到,需要花费一定的时间对其数学模型进行深入理解。而且,采用该方案编写相关存储过程,新增,删除,同层平移节点需要对整个树进行查询修改,由此导致的代码复杂度,耦合度较高,修改维护的风险较高。
上面的设计方案必须预先设定类别树的最大层数以及最大子节点数,不是无限分级,在某些场合并不能采用,那么还有更完美的解决方案吗?通过 google的搜索,我又探索到一种全新的无递归查询,无限分级的编码方案——左右值。原文的程序代码是用php写的,但是通过仔细阅读其数据库表设计说明及相关的sql语句,我彻底弄懂了这种巧妙的设计思路,并在这种设计中新增了删除节点,同层平移的需求(原文只提供了列表及插入子节点的sql语句)。
下面我力图用比较简短的文字,少量图表,及相关核心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,对整个类别表的破坏是惊人的,强烈推荐在做上述工作前对类别表进行完整备份。
同层下移的存储过程和同层上移类似,有兴趣的朋友可以自己动手编写体味一下其中的细节,我就不在这里列出来了。
最后,我对上面这种左右值编码实现无限分级类别树的方案做一个总结:
优点:在消除递归的前提下实现了无限分级,而且查询条件是基于整形数字比较的,效率很高。可以进行先序列表,添加,修改,删除,同层平移等常规操作,基本满足需求。
缺点:由于这种左右值编码的方式和常见的阿拉伯数字直观排序不同,再加上节点在树中的层次,顺序不是直观显示出来,而必须通过简单的公式计算后得到,需要花费一定的时间对其数学模型进行深入理解。而且,采用该方案编写相关存储过程,新增,删除,同层平移节点需要对整个树进行查询修改,由此导致的代码复杂度,耦合度较高,修改维护的风险较高。
发表评论
-
Apache POI简介
2011-10-19 22:56 1547Apache POI是操作基于微软的OLE 2 Compoun ... -
Oracle——distinct的用法
2013-02-21 08:12 839distinct这个关键字来过滤掉多余的重复记录只保留一条,但 ... -
使用Spring提供的MailSender异步发送文本邮件
2013-02-21 08:12 1662在工程中经常有发送邮件的任务,如果使用JavaMail来发送邮 ... -
Spring邮件发送
2013-02-21 08:12 887以下是我对spring发送邮件的总结: 分别使用了两种方法: ... -
BIRT Viewer 2.2 参数设置详解
2011-10-04 12:28 0BIRT Viewer 2.2 参数设置详 ... -
BIRT部署并利用API生成PDF
2011-10-04 12:27 0Birt报表设计步骤: 1、下载birt all in one ... -
TOMCAT集群配置
2011-10-04 12:20 0我的运行环境:Windows2003 Server SP4 + ... -
POI中文编码及多工作表输出
2011-10-04 12:06 1171import java.io.FileOutputStream ... -
Linux下Apache与Tomcat整合的简单方法
2011-10-04 12:07 8081、准备,下载需要的文件。这里假定你已经正确安装配置好了JDK ... -
JMX在Tomcat中的应用
2011-10-04 12:07 8676一、 JMX 简单介绍 Tomcat 从 5.0 版本开始 ... -
将多个Tomcat实例应用转为Windows服务
2011-10-04 12:07 1519有使用过Tomcat经验的朋 ... -
web.xml配置总结
2011-10-03 22:50 4353一、关于webAppRootKey的定 ... -
解决多重web应用中webapp. root重用的问题
2011-10-03 22:09 1254当在tomcate中发布多个同根的应用时,容易出现这样异常: ... -
Tomcat 组件配置简介
2011-10-03 22:07 816Tomcat 组件配置简介 ------ 本文部分内容摘自 电 ... -
Tomcat启动分析
2011-10-03 22:01 7241 - Tomcat Server的组成部 ... -
如何同时启动多个Tomcat服务器
2011-10-03 21:56 881我所用Tomcat服务器都为zip版,非安装版。以两个为例: ...
相关推荐
标题提及的“左右值编码”是一种在数据库中存储无限分级树形结构的方法,常用于组织层级数据,如商品分类、组织架构等。这种方法的核心在于为每个节点分配两个数值:左值(Lft)和右值(Rgt),它们能够唯一地确定...
【左右值编码】是一种在数据库中存储无限分级树形结构的有效方法,主要应用于有层级关系的数据,如组织架构、商品分类等。这种方法的核心思想是为每个节点分配两个数值:左值(Lft)和右值(Rgt),通过这两个值可以...
5. **无限分级类**:在处理具有层级关系的数据(如分类、菜单)时,无限分级类能将数据结构化为树形结构,便于遍历和展示。这类类可能使用递归或自连接查询来实现,同时提供添加、删除、修改节点的方法。 6. **验证...
总结来说,这个数据库树形数据处理方案提供了一套完整的工具集,用于管理和操作树形结构的数据。它包括了数据的排序、统计、增删改查,并且考虑了数据完整性和层级关系的维护,对于处理具有层级关系的数据场景非常...
- **树形结构的理解**: 首先需要理解表1中的数据实际上构成了一个树形结构。每个记录代表树中的一个结点,每个结点包含自身的编码(id)、父结点的编码(pid)以及名称(name)。 - **编码规则分析**: 为了将表1转换为表2...
4. **数据库设计**:在数据库层面,省市区数据可能存储在一个表中,包含省份、城市和区县三个字段,或者采用分级的树形结构,每个区域有自己的父级ID,便于构建多级联动效果。 5. **JSON格式**:后端返回的数据通常...
在ASP.NET中,XML经常被用来构建TreeView控件,这是一个用户界面元素,可以以树形结构显示数据,非常适合展示层次化的信息。 TreeView控件是ASP.NET Web Forms中一个强大的组件,它允许用户以多级缩进的形式查看和...
【文件目录结构】Windows文件的目录结构呈树形,允许多级子目录。 【科学计算器】在Windows中,科学型计算器可以进行复杂的数学运算,如计算指数。 【文件更名】文件更名不会改变其内容。 【网络内容控制】IE的...
- **定义**: 每个节点的值都大于其左子树中的任意节点的值,小于其右子树中的任意节点的值。 - **应用**: 支持高效的插入、删除和查找操作。 - **平衡问题**: 需要注意保持树的平衡以确保O(log n)的操作时间。 **6....
对象浏览器——可配置的树形浏览能够显示同PL/SQL开发相关的全部信息,使用该浏览器可以获取对象描述、浏览对象定义、创建测试脚本以便调试、使能或禁止触发器或约束条件、重新编译不合法对象、查询或编辑表格、...
可配置的树形浏览能够显示同PL/SQL开发相关的全部信息,使用该浏览器可以获取对象描述、浏览对象定义、创建测试脚本以便调试、使能或禁止触发器或约束条件、重新编译不合法对象、查询或编辑表格、浏览数据、在对象...
通过“矿图信息管理系统”的建设,彻底整合煤矿矿业集团的矿图资源信息,并将其统一存储在数据库中,以实现矿图的“集中存储,统一管理,分级调用”,进而通过数据共享,提高煤矿矿业集团科研、生产、经营、管理的...
通过“GIS信息管理系统”的建设,彻底整合煤矿矿业集团的矿图资源信息,并将其统一存储在数据库中,以实现矿图的“集中存储,统一管理,分级调用”,进而通过数据共享,提高煤矿矿业集团科研、生产、经营、管理的...