通过 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