看了 无限级分类的简单算法实现及代码重点讲解 感觉不错。
下面还有一种不错的分级方案页很不错,在实际运用中我对其进行了适当修改。
采用左右值编码来存储无限分级树形结构的数据库表设计
原文: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1586020
作者: bobcy的专栏
无限分级的编码方案——左右值。原文的程序代码是用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表建立一个视图,添加一个层数列,该类别的层数可以写一个自定义函数来计算。该函数如下:
01.CREATE FUNCTION dbo.CountLayer
02.(
03. @type_id int
04.)
05.RETURNS int
06.AS
07.begin
08. declare @result int
09. set @result=0
10. declare @lft int
11. declare @rgt int
12. if exists (select 1 from tree where type_id=@type_id)
13. begin
14. select @lft=lft,@rgt=rgt from tree where type_id=@type_id
15. select @result = count(*) from tree where lft <= @lft and rgt >= @rgt
16. end
17. return @result
18.end
19.GO
复制代码
然后,我们建立如下视图:
01.CREATE VIEW dbo.TreeView
02.AS
03.SELECT type_id, name, lft, rgt, dbo.CountLayer(type_id) AS layer FROM dbo.tree ORDER BY lft
04.GO
05.
复制代码给出对于给定某个节点,对该节点及其子孙节点进行先序遍历的存储过程:
01.CREATE PROCEDURE [dbo].[GetTreeListByNode]
02.(
03. @type_id int --给定节点标识
04.)
05.AS
06.declare @lft int
07.declare @rgt int
08.if exists (select 1 from tree where type_id=@type_id)
09. begin
10. select @lft=lft,@rgt=rgt from tree where type_id=@type_id
11. select * from TreeView where lft between @lft and @rgt order by lft asc
12. end
13.go
14.
复制代码
现在,我们使用上面的存储过程来列表节点“食品”及其所有子孙节点,查询结果如下:
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脚本吧?下面我给出相对完整的插入子节点的存储过程:
01.CREATE PROCEDURE [dbo].[AddSubNodeByNode]
02.(
03. @type_id int,
04. @name varchar(50)
05.)
06.AS
07.declare @rgt int
08.if exists (select 1 from tree where type_id=@type_id)
09. begin
10. SET XACT_ABORT ON
11. BEGIN TRANSACTION
12. select @rgt=rgt from tree where type_id=@type_id
13. update tree set rgt=rgt+2 where rgt>=@rgt
14. update tree set lft=lft+2 where lft>=@rgt
15. insert into tree (name,lft,rgt) values (@name,@rgt,@rgt+1)
16. COMMIT TRANSACTION
17. SET XACT_ABORT OFF
18. end
19.go
复制代码
然后,我们删除节点“电视机”,再来看看该树会变成什么情况:
1商品20-2
+-----------------------------------+
2食品13 14电器19-2
+-----------------+
3肉类8 9蔬菜类12 17-2电冰箱18-2
+----------+
4猪肉5 6牛肉7 10白菜11
相应的存储过程如下:
01.CREATE PROCEDURE [dbo].[DelNode]
02. @type_id int
03.AS
04.declare @lft int
05.declare @rgt int
06.if exists (select 1 from tree where type_id=@type_id)
07. begin
08. SET XACT_ABORT ON
09. BEGIN TRANSACTION
10. select @lft=lft,@rgt=rgt from tree where type_id=@type_id
11. delete from tree where lft>=@lft and rgt<=@rgt
12. update tree set lft=lft-(@rgt-@lft+1) where lft>@lft
13. update tree set rgt=rgt-(@rgt-@lft+1) where rgt>@rgt
14. COMMIT TRANSACTION
15. SET XACT_ABORT OFF
16.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,对整个类别表的破坏是惊人的,强烈推荐在做上述工作前对类别表进行完整备份。
同层下移的存储过程和同层上移类似,有兴趣的朋友可以自己动手编写体味一下其中的细节,我就不在这里列出来了。
最后,我对上面这种左右值编码实现无限分级类别树的方案做一个总结:
优点:在消除递归的前提下实现了无限分级,而且查询条件是基于整形数字比较的,效率很高。可以进行先序列表,添加,修改,删除,同层平移等常规操作,基本满足需求。
缺点:由于这种左右值编码的方式和常见的阿拉伯数字直观排序不同,再加上节点在树中的层次,顺序不是直观显示出来,而必须通过简单的公式计算后得到,需要花费一定的时间对其数学模型进行深入理解。而且,采用该方案编写相关存储过程,新增,删除,同层平移节点需要对整个树进行查询修改,由此导致的代码复杂度,耦合度较高,修改维护的风险较高。
对上面树表的修改:
在对上面的方案修改前大家请先看看两幅图(此图好眼熟)
原文方案图
修改后方案图(说明:1/2样式为:左边代表唯一Type_ID 右边代表:Layer)
上面的树表在实际的使用中你会发现一个问题,就是每次要查询出第一层的所有子孙节点的时候,速度特别慢,尤其是当分类越来越深的时候,显示子孙节点将花费1-2秒,原因在那里?我们从上面的设计思想里看出,在查询节点下面的所有子孙节点的时候使用了一个视图和一个当前节点的层数的统计函数。速度慢的原因就是因为使用了一个统计。那么我们有什么办法能削除这个统计吗?答案是肯定的。下面我们来看修改后的表
Type_id Name Lft Rgt Layer
1 商品 1 18 1
2 食品 2 11 2
3 肉类 3 6 3
4 猪肉 4 5 4
5 蔬菜类 7 10 3
6 白菜 8 9 4
7 电器 12 17 2
8 电视机 13 14 3
9 电冰箱 15 16 3
仅仅在tree上多加了一个layer字段.也许有人会问,那么添加节点的时候也要统计层啊,也要统计层啊。(删除节点的时候不需要),这里我们要告诉你,统计函数也可以去掉,因为在我们添加根节点的时候默认把layer设置成1,以后添加下级节点只要在此节点层上加1就可以了.
按照上面的思想,其实我们可以删掉一个视图和一个层统计。前台调用一般只要2个存储过程就可以了,一个显示父节点路径,一个显示当前节点子节点列表就可以了,而且在和其他表链接查询的时候值需要2次,完全消除递归.(具体修改后的查询就不写了,这里只写了一颗树,大家把商品在实际当中去掉,那么剩下的是什么了?很有意思,深度挖掘一下,也许会有收获)
由于方案操作树表有很大的破坏性,因此我们可以写一个通用的tree管理器来管理树表信息.
分享到:
相关推荐
[TREE]采用左右值编码来存储无限分级树形结构的数据库表设计
水平树 Treeview自定义高级控件 菜单分级树形 C#
jquery tree树形结构在网页设计中必不可少,尤其是在后台管理模板(不兼容IE6,7,8浏览器)
自定义树形结构组件—TreeView TreeView控件用来显示信息的分级视图,如同Windows里的资源管理器的目录。TreeView控件中的各项信息都有一个与之相关的Node对象。TreeView显示Node对象的分层目录结构,每个Node对象...
无限分级 面向对象的方式 从数据库中读取节点后,只要一句代码,如用JSP (rs.next()){ %> d.add(("id")%>,("pid")%>,'("title")%>'); <% }%>
实现无限分级的数据库设计,可以实现重用
练习用,花了100分问问题的成果。囧! 菜鸟上路,代码共享QQ:846461,希望高手加我加以指导。 db_path = "x.mdb" Set conn= Server.createObject("ADODB.Connection") connstr = "Provider=Microsoft.Jet.OLEDB....
otreetable.js 原生JS树形表格,调用非常简单(只需一句代码即可调用),获取HTML中输出的表格数据重构表格,以树形方式显示,可展开/收缩,不破坏表格原有数据格式及内容,支持无限级,兼容所有浏览器。当前版本...
这种算法的数据库结构设计最为简单。category表中一个字段id,一个字段fid(父id)。这样可以根据WHERE id = fid来判断上一级内容,运用递归至最顶层。 分析:通过这种数据库设计出的无限级,可以说读取的时候相当费劲...
PHP树结构,实现无限分级 代码亲测有效,放在php环境下就行
可动态添加分级目录,可勾选,全选,自动拓展!
主要介绍了vue-cli + element-ui 树形表格(多级表格折腾小计),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
将xml文档的各节点以及属性用树形控件显示,属性显示在文本框中
MPEG_4视频编码的可分级技术研究.pdf MPEG_4视频编码的可分级技术研究.pdf
搜集的两个jquery插件,用于生成树形导航分级菜单,其中一个还可以实现选择功能。
Bootstrap多级树形分类折叠菜单基于Bootstrap2.2.1制作,多级分类树形菜单。
基于后验概率的算术编码器进行拓扑符号编码,采用不同情景进行设计,提出渐进式的标签预测过程,实现已编码组信息的充分利用,并采用局部坐标系有效压缩几何残差。通过与对比编码器的实验验证,所提算法相对于AD、...
精细可分级编码技术及其应用精细可分级编码技术及其应用
VC++6.0平台下实现树结构列表,是将具有一定层次结构的数据进行分级显示的控件,代码包含相互关联方式,可用于对磁盘目录单位组织结构产品品类别等管理。
TreeView&XML实现无限分级,递归实现无限分级,无论在xml文件中添加几级都可以实现.