PHP左右值无限分类

《PHP左右值无限分类》由会员分享，可在线阅读，更多相关《PHP左右值无限分类（10页珍藏版）》请在装配图网上搜索。

1、采用左右值编码来存储无限分级树形结构的数据库表设计之前我介绍过一种按位数编码保存树形结构数据的表设计方法，详情见：浅谈数据库设计技巧（上）该设计方案的优点是：只用一条查询语句即可得到某个根节点及其所有子孙节点的先序遍历。由于消除了递归，在数据记录量较 大时，可以大大提高列表效率。但是，这种编码方案由于层信息位数的限制，限制了每层能所允许的最大子节点数量及最大层数。同时， 在添加新节点的时候必须先计算新节点的位置是否超过最大限制。上面的设计方案必须预先设定类别树的最大层数以及最大子节点数，不是无限分级，在某些场合并不能采用，那么还有更完美的 解决方案吗？通过google的搜索，我又探索到一种全新

2、的无递归查询，无限分级的编码方案一一左右值。原文的程序代码是用php写 的，但是通过仔细阅读其数据库表设计说明及相关的sql语句，我彻底弄懂了这种巧妙的设计思路，并在这种设计中新增了删除节点， 同层平移的需求（原文只提供了列表及插入子节点的sql语句）。下面我力图用比较简短的文字，少量图表，及相关核心sql语句来描述这种设计方案：首先，我们弄一棵树作为例子：商品I-食品I |-肉类I I I-猪肉I I蔬菜类II-白菜I-电器I-电视机I-电冰箱采用左右值编码的保存该树的数据记录如下（设表名为tree）：Type_idNameLftRgt1商品1182食品2113肉类364猪肉455蔬菜类71

3、06白菜897电器12178电视机13149电冰箱1516第一次看见上面的数据记录，相信大部分人都不清楚左值（Lft）和右值（Rgt）是根据什么规则计算 出来的，而且，这种表设计似乎没有保存父节点的信息。下面把左右值和树结合起来，请看：1商品18+2食品1112电器17+3肉类67蔬菜类1013电视机1415电冰箱164猪肉58白菜9请用手指指着上图中的数字，从1数到18,学习过数据结构的朋友肯定会发现什么吧？对，你手指 移动的顺序就是对这棵树的进行先序遍历的顺序。接下来，让我讲述一下如何利用节点的左右值，得到该 节点的父节点，子孙节点数量，及自己在树中的层数。假定我们要对节点食品”及其子孙节

4、点进行先序遍历的列表，只需使用如下一条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同时，我们在列表显示整个类别树的时候，为了方便用户直观的看到树的层次，一般会根据节点所处的层数来进行相应的缩进，那么，如何计算节点在树中的层数呢？还是只需通过左右值的查询即可，以节点食品

5、”举例，sql语句如下：select count(*) from tree where 1ft = 11为了方便列表，我们可以为tree表建立一个视图，添加一个层数列，该类别的层数可以写一个自定 义函数来计算。该函数如下：CREATE FUNCTION dbo.CountLayer(type_id int)RETURNS intASbegindeclare result intset result=0declare lft intdeclare rgt intif exists (select 1 from tree where type_id =type_id)beginselect lft

6、= lft,rgt= rgt from tree where type_id =type_idselect result = count(*) from tree where lft = rgtendreturn resultendGO然后，我们建立如下视图：CREATE VIEW dbo.TreeViewASSELECT type_id, name, lft, rgt, dbo.CountLayer(type_id) AS layer FROM dbo.tree ORDER BY lftGO给出对于给定某个节点，对该节点及其子孙节点进行先序遍历的存储过程：CREATE PROCEDURE d

7、bo.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 asc endgo现在，我们使用上面的存储过程来列表节点食品”及其所有子孙节点，查询结果如下：T

8、ype_idNameLftRgtLaye r2食品21123肉类3634猪肉4545蔬菜类71036白菜894采用左右值编码的设计方案，在进行类别树的遍历时，由于只需进行2次查询，消除了递归，再加上 查询条件都为数字比较，效率极高，类别树的记录条目越多，执行效率越高。看到这里，相信不少人对这 种设计方案有所心动了，下面让我们接着看看如何在这种表结构中实现插入、删除、同层平移节点（变更同层节点排序）的功能。假定我们要在节点肉类”下添加一个子节点牛肉”，该树将变成：1商品18+2+2 食品 11+212+2 电器 17+2+ +3肉类6+27+2蔬菜类10+213+2电视机14+215+2电冰箱1

9、6+2+4猪肉5 6牛肉7 8+2白菜9+2看完上图相应节点左右值的变化后，相信大家都知道该如何写相应的sql脚本吧？下面我给出相对完整的插入子节点的存储过程：CREATE PROCEDURE dbo.AddSubNodeByNode(type_id int,name varchar(50)ASdeclare rgt intif exists (select 1 from tree where type_id = type_id)beginSET XACT_ABORT ONBEGIN TRANSACTIONselect rgt=rgt from tree where type_id = typ

10、e_idupdate tree set rgt=rgt+2 where rgt = rgtupdate tree set lft=lft+2 where lft = rgtinsert into tree (name,lft,rgt) values (name,rgt,rgt+1)COMMIT TRANSACTIONSET XACT_ABORT OFFendgo然后，我们删除节点电视机，再来看看该树会变成什么情况:1商品20-2+2食品1314电器19-2+3肉类89蔬菜类1217-2电冰箱18-2+ 4猪肉5 6牛肉7 10白菜11相应的存储过程如下：CREATE PROCEDURE dbo

11、.DelNodetype_id intASdeclare lft intdeclare rgt intif exists (select 1 from tree where type_id =type_id)beginSET XACT_ABORT ONBEGIN TRANSACTIONselect lft= lft,rgt=rgt from tree where type_id=type_iddelete from tree where lft = lft and rgtlftupdate tree set rgt=rgt-(rgt-lft+1) where rgtrgtCOMMIT TRAN

12、SACTIONSET XACT_ABORT OFFEnd注意：因为删除某个节点会同时删除该节点的所有子孙节点，而这些被删除的节点的个数为：（被删节 点的右值-被删节点的左值+1）/2,而任何一个节点同时具有唯一的左值和唯一的右值，故删除作废节点后, 其他相应节点的左、右值需要调整的幅度应为：减少（被删节点的右值-被删节点的左值+1）。最后，让我们看看平移节点电器”，将其和其所有子孙节点移动到节点食品”之前后，该树会变成什 么情况：1商品18+14-12 电器 17-122+4 食品 13+4+15-12电冰箱16-123+4肉类8+49+4蔬菜类12+4+4+4 猪肉 5+46+4 牛肉 7+

13、4 10+4 白菜 11+4大家仔细观察一下交换后同层2个节点和其所有子孙节点左右值的变化，可以发现一个明显的规律， 那就是，节点电器”及其所有子孙节点的左右值均减少12,而节点食品”及其所有子孙节点的左右值均增 加4。而节点电器”+其子孙节点的数量为2,节点食品”+其子孙节点的数量为6,这其中有什么联系吗？ 还记得我在删除节点的存储过程后面的注释吗？任何一个节点同时具有唯一的左值和唯一的右值。让我们 把节点数量*2,正好和节点左右值需要调整的幅度相等。由此规律，我们可以编写出类似下面的存储过程 来实现节点同层前移的功能：CREATE PROCEDURE dbo.MoveNodeUptype_

14、id intASdeclare lft intdeclare rgt intdeclare layer intif exists （select 1 from tree where type_id = type_id）beginSET XACT_ABORT ONBEGIN TRANSACTIONselect 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)begindeclare

15、 brother_lft intdeclare brother_rgt intselect brother_lft= lft,brother_rgt=rgt from TreeView where rgt =lft-1 an d laye r=laye rupdate tree set lft= lft (brother_rgt-brother_lft+1) where lft = lft and rgt = brother_lft and rgt : = br othe r_rgtupdate tree set rgt=rgt (brother_rgt-brother_lft+1) wher

16、e rgtbrother_ rgt and rgt = brother_lft+(rgt-lft+ 1) and rgt : = brother_rgtendCOMMIT TRANSACTIONSET XACT_ABORT OFFend注意：节点的同层平移可以采用临时表来做中介，降低代码的复杂度。不用临时表来处理也行，但是 update语句顺序一定要考虑周详。否则，一旦出现bug，对整个类别表的破坏是惊人的，强烈推荐在做 上述工作前对类别表进行完整备份。同层下移的存储过程和同层上移类似，有兴趣的朋友可以自己动手编写体味一下其中的细节，我就不 在这里列出来了。最后，我对上面这种左右值编码实现无限

17、分级类别树的方案做一个总结:优点：在消除递归的前提下实现了无限分级，而且查询条件是基于整形数字比较的，效率很高。可以 进行先序列表，添加，修改，删除，同层平移等常规操作，基本满足需求。缺点：由于这种左右值编码的方式和常见的阿拉伯数字直观排序不同，再加上节点在树中的层次，顺序不是直观显示出来, 而必须通过简单的公式计算后得到，需要花费一定的时间对其数学模型进行深入理解。而且，采用该方案编写相关存储过程， 新增，删除，同层平移节点需要对整个树进行查询修改，由此导致的代码复杂度，耦合度较高，修改维护的风险较高。#hometohome 发表于 2008-05-07 22:17:19 IP: 123.1

18、15.4.*请问该如何根据子节点的type_id找出父节点呢？比如：猪肉的父节点是肉类、食品、商品#hometohome 发表于 2008-05-07 22:38:54 IP: 123.115.4.*declare rgt intselect rgt=rgt from tree where type_id = 13select * from tree where rgt = rgt and lft = rgt order by lft我是楼上的。这么做可否？#greki 发表于 2008-10-11 17:49:40 IP: 125.122.194.*非常感谢，试过很好用，另外我不懂存储过程，

19、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 asc end go这个改为返回结果集。select *

20、 from TreeView where 1ft between lft and rgt order by 1ft asc。怎么改#Binlorima 发表于 2008-11-17 16:08:20 IP: 220.231.42.*看到你的这篇文章后，我有以下想法：数据库结构：id name index layer1食品122肉类2 33猪肉3 44蔬菜类4 35白菜5 46电器6 27电视机7 38电冰箱8 3laye r 12 3 4 index1卜-_食品2 |卜-肉类3 |卜-猪肉4 | | 蔬菜类5 | |-白菜6 | 电器7卜-电视机8 |-电冰箱我认为这样存储更直观而且不需要计算层级，更容易得出父节点及直接父节点