[TREE]采用左右值编码来存储无限分级树形结构的数据库表设计.doc

采用左右值编码来存储无限分级树形结构的数据库表设计之前我介绍过一种按位数编码保存树形结构数据的表设计方法，详情见：浅谈数据库设计技巧(上) 该设计方案的优点是：只用一条查询语句即可得到某个根节点及其所有子孙节点的先序遍历。由于消除了递归，在数据记录量较大时，可以大大提高列表效率。但是，这种编码方案由于层信息位数的限制，限制了每层能所允许的最大子节点数量及最大层数。同时，在添加新节点的时候必须先计算新节点的位置是否超过最大限制。上面的设计方案必须预先设定类别树的最大层数以及最大子节点数，不是无限分级，在某些场合并不能采用，那么还有更完美的解决方案吗？通过 google的搜索，我又探索到一种全新的无递归查询，无限分级的编码方案左右值。原文的程序代码是用php写的，但是通过仔细阅读其数据库表设计说明及相关的sql语句，我彻底弄懂了这种巧妙的设计思路，并在这种设计中新增了删除节点，同层平移的需求（原文只提供了列表及插入子节点的sql语句）。下面我力图用比较简短的文字，少量图表，及相关核心sql语句来描述这种设计方案：首先，我们弄一棵树作为例子：商品|-食品|-肉类|-猪肉 |-蔬菜类 |-白菜 |-电器 |-电视机 |-电冰箱采用左右值编码的保存该树的数据记录如下（设表名为tree）：Type_idNameLftRgt1商品1182食品2113肉类364猪肉455蔬菜类7106白菜897电器12178电视机13149电冰箱1516第一次看见上面的数据记录，相信大部分人都不清楚左值（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_idNameLftRgt2食品2113肉类364猪肉455蔬菜类7106白菜89那么某个节点到底有多少子孙节点呢？很简单，子孙总数 （右值-左值-1）/2以节点“食品”举例，其子孙总数（11-2-1）/ 2 4同时，我们在列表显示整个类别树的时候，为了方便用户直观的看到树的层次，一般会根据节点所处的层数来进行相应的缩进，那么，如何计算节点在树中的层数呢？还是只需通过左右值的查询即可，以节点“食品”举例，sql语句如下：select count(*) from tree where lft = 11为了方便列表，我们可以为tree表建立一个视图，添加一个层数列，该类别的层数可以写一个自定义函数来计算。该函数如下： CREATEFUNCTIONdbo.CountLayer(type_idint)RETURNSintASbegindeclareresultintsetresult=0declarelftintdeclarergtintifexists(select1fromtreewheretype_id=type_id)beginselectlft=lft,rgt=rgtfromtreewheretype_id=type_idselectresult=count(*)fromtreewherelft=rgtendreturnresultendGO然后，我们建立如下视图：CREATEVIEWdbo.TreeViewASSELECTtype_id,name,lft,rgt,dbo.CountLayer(type_id)ASlayerFROMdbo.treeORDERBYlftGO给出对于给定某个节点，对该节点及其子孙节点进行先序遍历的存储过程：CREATEPROCEDUREdbo.GetTreeListByNode(type_idint-给定节点标识)ASdeclarelftintdeclarergtintifexists(select1fromtreewheretype_id=type_id)beginselectlft=lft,rgt=rgtfromtreewheretype_id=type_idselect*fromTreeViewwherelftbetweenlftandrgtorderbylftascendgo现在，我们使用上面的存储过程来列表节点“食品”及其所有子孙节点，查询结果如下：Type_idNameLftRgtLayer2食品21123肉类3634猪肉4545蔬菜类71036白菜894采用左右值编码的设计方案，在进行类别树的遍历时，由于只需进行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脚本吧？下面我给出相对完整的插入子节点的存储过程：CREATEPROCEDUREdbo.AddSubNodeByNode(type_idint,namevarchar(50)ASdeclarergtintifexists(select1fromtreewheretype_id=type_id)beginSETXACT_ABORTONBEGINTRANSACTIONselectrgt=rgtfromtreewheretype_id=type_idupdatetreesetrgt=rgt+2wherergt=rgtupdatetreesetlft=lft+2wherelft=rgtinsertintotree(name,lft,rgt)values(name,rgt,rgt+1)COMMITTRANSACTIONSETXACT_ABORTOFFendgo然后，我们删除节点“电视机”，再来看看该树会变成什么情况： 1商品20-2 +-+ 2食品13 14电器19-2 +-+ 3肉类8 9蔬菜类12 17-2电冰箱18-2 +-+ 4猪肉56牛肉7 10白菜11相应的存储过程如下：CREATEPROCEDUREdbo.DelNodetype_idintASdeclarelftintdeclarergtintifexists(select1fromtreewheretype_id=type_id)beginSETXACT_ABORTONBEGINTRANSACTIONselectlft=lft,rgt=rgtfromtreewheretype_id=type_iddeletefromtreewherelft=lftandrgtlftupdatetreesetrgt=rgt-(rgt-lft+1)wherergtrgtCOMMITTRANSACTIONSETXACT_ABORTOFFEnd注意：因为删除某个节点会同时删除该节点的所有子孙节点，而这些被删除的节点的个数为：(被删节点的右值-被删节点的左值+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+410+4白菜11+4大家仔细观察一下交换后同层2个节点和其所有子孙节点左右值的变化，可以发现一个明显的规律，那就是，节点“电器”及其所有子孙节点的左右值均减少12，而节点“食品”及其所有子孙节点的左右值均增加4。而节点“电器”+其子孙节点的数量为2，节点“食品”+其子孙节点的数量为6，这其中有什么联系吗？还记得我在删除节点的存储过程后面的注释吗？任何一个节点同时具有唯一的左值和唯一的右值。让我们把节点数量*2，正好和节点左右值需要调整的幅度相等。由此规律，我们可以编写出类似下面的存储过程来实现节点同层前移的功能：CREATEPROCEDUREdbo.MoveNodeUptype_idintASdeclarelftintdeclarergtintdeclarelayerintifexists(select1fromtreewheretype_id=type_id)beginSETXACT_ABORTONBEGINTRANSACTIONselectlft=lft,rgt=rgt,layer=layerfromTreeViewwheretype_id=type_idifexists(select*fromTreeViewwherergt=lft-1andlayer=layer)begindeclarebrother_lftintdeclarebrother_rgtintselectbrother_lft=lft,brother_rgt=rgtfromTreeViewwherergt=lft-1andlayer=layerupdatetreesetlft=lft-(brother_rgt-brother_lft+1)wherelft=lftandrgt=brother_lftandrgtbrother_rgtandrgt=brother_lft+(rgt-lft+1)andrgt=rgt and lft=rgt order by lft我是楼上的。这么做可否？#greki发表于2008-10-11 17:49:40IP: 125.122.194.* 非常感谢，试过很好用，另外我不懂存储过程，CREATE PROCEDURE dbo.GetTreeListByNode(type_id int -给定节点标识)ASdeclare lft intdeclare rgt intif exists (select 1 from tree where type_id=type_id)beginselect lft=lft,rgt=rgt from tree where type_id=type_idselect * from TreeView where lft between lft and rgt order by lft ascendgo这个 改为返回结果集。 select * from TreeView where lft between lft and rgt order by lft asc。怎么改#Binlorima发表于2008-11-17 16:08:20I