X-Spirit
Always Beyond the Time
BlogJava
|
首页
|
发新随笔
|
发新文章
|
联系
|
聚合
|
管理
随笔:91 文章:1 评论:65 引用:0
[导入][转]采用左右值编码来存储无限分级树形结构的数据库表设计2
采用左右值编码的设计方案,在进行类别树的遍历时,由于只需进行
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,对整个类别表的破坏是惊人的,强烈推荐在做上述工作前对类别表进行完整备份。
同层下移的存储过程和同层上移类似,有兴趣的朋友可以自己动手编写体味一下其中的细节,我就不在这里列出来了。
最后,我对上面这种左右值编码实现无限分级类别树的方案做一个总结:
优点:在消除递归的前提下实现了无限分级,而且查询条件是基于整形数字比较的,效率很高。可以进行先序列表,添加,修改,删除,同层平移等常规操作,基本满足需求。
缺点:由于这种左右值编码的方式和常见的阿拉伯数字直观排序不同,再加上节点在树中的层次,顺序不是直观显示出来,而必须通过简单的公式计算后得到,需要花费一定的时间对其数学模型进行深入理解。而且,采用该方案编写相关存储过程,新增,删除,同层平移节点需要对整个树进行查询修改,由此导致的代码复杂度,耦合度较高,修改维护的风险较高。
文章来源:
http://x-spirit.spaces.live.com/Blog/cns!CC0B04AE126337C0!368.entry
发表于 2007-12-18 20:02
X-Spirit
阅读(255)
评论(0)
编辑
收藏
新用户注册
刷新评论列表
只有注册用户
登录
后才能发表评论。
网站导航:
博客园
IT新闻
知识库
C++博客
博问
管理
<
2007年12月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
常用链接
我的随笔
我的文章
我的评论
我的参与
最新评论
留言簿
(6)
给我留言
查看公开留言
查看私人留言
随笔分类
(28)
Big Data
(rss)
Cloud
(rss)
Java EE
(rss)
Java FX
(rss)
Java SE(9)
(rss)
Java 轻量级企业开发(5)
(rss)
Linux(3)
(rss)
MySQL
(rss)
NetBeans(1)
(rss)
Node.js
(rss)
NoSQL
(rss)
Oracle(3)
(rss)
前端技术
(rss)
开源协议(1)
(rss)
思维模式
(rss)
悟(1)
(rss)
技术之外(5)
(rss)
敏捷开发
(rss)
时间管理
(rss)
随笔档案
(90)
2014年9月 (1)
2014年3月 (1)
2014年2月 (1)
2014年1月 (1)
2013年2月 (1)
2012年11月 (1)
2012年10月 (1)
2012年3月 (1)
2012年2月 (1)
2011年2月 (1)
2010年4月 (6)
2010年3月 (4)
2010年1月 (2)
2009年11月 (1)
2009年8月 (1)
2009年7月 (1)
2009年6月 (2)
2009年5月 (1)
2009年4月 (13)
2009年3月 (1)
2009年2月 (1)
2009年1月 (2)
2008年12月 (3)
2008年11月 (1)
2008年10月 (1)
2008年9月 (3)
2008年5月 (1)
2008年4月 (9)
2008年3月 (3)
2008年1月 (1)
2007年12月 (4)
2007年10月 (2)
2007年9月 (6)
2007年8月 (9)
2007年7月 (1)
2007年4月 (1)
文章分类
(1)
My Voice(1)
(rss)
文章档案
(1)
2009年12月 (1)
收藏夹
(4)
别人的学习笔记(4)
(rss)
牛人牛博
DaoRu的Blog
(rss)
爱折腾的道儒
Doug Lea's Home Page
Doug Lea's Home Page
jolestar
老王的博客
Tim Yang
(rss)
后端技术
Yang_net
(rss)
靠谱IT帅哥
摇摆巴赫@blog.sina
源码控
摇摆巴赫@javaeye
源码控
文初的一亩三分地
淘宝放翁
淘宝核心团队
淘宝核心团队
福林雨
(rss)
福林的博客
那谁的BLOG
那谁的BLOG
酷站
ImportNew
学习新知、发现新朋友
InfoQ中文站
InfoQ中文站
InfoQ英文站
InfoQ英文站
Java Code Geeks
A website for Java Geeks
并发编程网
并发编程网
开源中国
OSCHINA
百度技术沙龙
百度技术沙龙
酷壳
(rss)
酷壳
最新随笔
1. 【Math's History】什么是罗素悖论
2. 【Effective】IntelliJ IDEA MAC IDE config files
3. 5 Ways To Burn Out Programming
4. 【Efficiency】快速配置ubuntu桌面环境之Java环境配置[全软件源安装]
5. 【Efficiency】MAC下使用设定可以从mission control中启动的eclipse.app。
6. 【Effective】如何迁移git仓库
7. 【转】阅读我们的学科——计算机专业学习浅谈
8. 【Tech Details】【转】有关Java SPI机制
9. 【Efficiency】 监控 Linux 性能的 18 个命令行工具
10. 【Effective】Logging最佳实践
搜索
最新评论
1. re: Java 多线程同步问题的探究(三、Lock来了,大家都让开【1. 认识重入锁】)
上班
--地点
2. re: 【转】阅读我们的学科——计算机专业学习浅谈
好文!
--何杨
3. re: [导入][转]重复提交、重复刷新、防止后退的问题以及处理方式
是多少
--乒乓、
4. ......
....
--..
5. re: Java多线程同步问题的探究(一、线程的先来后到)
多线程这块一直是软肋,学习一下,呵呵
--FlyingFish
阅读排行榜
1. Java 多线程同步问题的探究(三、Lock来了,大家都让开【1. 认识重入锁】)(9035)
2. Java 多线程同步问题的探究(五、你有我有全都有—— ThreadLocal如何解决并发安全性?)【更新重要补疑】(8404)
3. Java 多线程同步问题的探究(二、给我一把锁,我能创造一个规矩)(7422)
4. Java 多线程同步问题的探究(四、协作,互斥下的协作——Java多线程协作(wait、notify、notifyAll))(7242)
5. Java多线程同步问题的探究(一、线程的先来后到)(7088)
评论排行榜
1. Java 多线程同步问题的探究(五、你有我有全都有—— ThreadLocal如何解决并发安全性?)【更新重要补疑】(15)
2. Java 多线程同步问题的探究(三、Lock来了,大家都让开【1. 认识重入锁】)(10)
3. Java 多线程同步问题的探究(二、给我一把锁,我能创造一个规矩)(9)
4. Java 多线程同步问题的探究(四、协作,互斥下的协作——Java多线程协作(wait、notify、notifyAll))(9)
5. Java多线程同步问题的探究(一、线程的先来后到)(8)