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

　　下面我力图用比较简短的文字，少量图表，及相关核心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