首页 > 算法 > 数据库中树形结构存储与优化 左右值树的处理

数据库中树形结构存储与优化 左右值树的处理

       无论是成本核算中的产品结构BOM,还是价格概算中的WBS工作任务分解,你都会遇到要在数据库中存储树型结构数据的情况。同时,除非你使用一种像XML的数据库,否则关系数据库中的表都不是层次结构的,他们只是一个平坦的列表。所以你必须找到一种把树型结构进行数据库转化的方法。

       在本文中,我们将探讨改进前序遍历树算法。我将举一个在线食品店树形图的例子。这个食品店通过类别、颜色和品种来组织食品。树形图如下:

改进前序遍历树

现在,让我们看另一种存储树的方法。递归可能会很慢,所以我们就尽量不使用递归函数。我们也想尽量减少数据库查询的次数。最好是每次只需要查询一次。

我们先把树按照水平方式摆开。从根节点开始(“Food”),然后他的左边写上1。然后按照树的顺序(从上到下)给“Fruit”的左边写上2。这样,你沿着树的边界走啊走(这就是“遍历”),然后同时在每个节点的左边和右边写上数字。最后,我们回到了根节点“Food”在右边写上18。下面是标上了数字的树,同时把遍历的顺序用箭头标出来了。

我们称这些数字为左值和右值(如,“Food”的左值是1,右值是18)。正如你所见,这些数字按时了每个节点之间的关系。因为“Red”有3和6两个值,所以,它是有拥有1-18值的“Food”节点的后续。同样的,我们可以推断所有左值大于2并且右值小于11的节点,都是有2-11的“Food”节点的后续。这样,树的结构就通过左值和右值储存下来了。这种数遍整棵树算节点的方法叫做“改进前序遍历树”算法。
在继续前,我们先看看我们的表格里的这些值:

获取树

如果你要通过左值和右值来显示这个树的话,你要首先标识出你要获取的那些节点。例如,如果你想获得“Fruit”子树,你要选择那些左值在2到11的节点。用SQL语句表达:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

这个会返回:

好吧,现在整个树都在一个查询中了。现在就要像前面的递归函数那样显示这个树,我们要加入一个ORDER BY子句在这个查询中。如果你从表中添加和删除行,你的表可能就顺序不对了,我们因此需要按照他们的左值来进行排序。

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;

就只剩下缩进的问题了。
要显示树状结构,子节点应该比他们的父节点稍微缩进一些。我们可以通过保存一个右值的一个栈。每次你从一个节点的子节点开始时,你把这个节点的右值添加到栈中。你也知道子节点的右值都比父节点的右值小,这样通过比较当前节点和栈中的前一个节点的右值,你可以判断你是不是在显示这个父节点的子节点。当你显示完这个节点,你就要把他的右值从栈中删除。要获得当前节点的层数,只要数一下栈中的元素。

节点的路径

有了新的算法,我们还要另找一种新的方法来获得指定节点的路径。这样,我们就需要这个节点的祖先的一个列表。
由于新的表结构,这不需要花太多功夫。你可以看一下,例如,4-5的“Cherry”节点,你会发现祖先的左值都小于4,同时右值都大于5。这样,我们就可以使用下面这个查询:

SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;

注意,就像前面的查询一样,我们必须使用一个ORDER BY子句来对节点排序。这个查询将返回:

我们现在只要把各行连起来,就可以得到“Cherry”的路径了。
有多少个后续节点?How Many Descendants
如果你给我一个节点的左值和右值,我就可以告诉你他有多少个后续节点,只要利用一点点数学知识。
因为每个后续节点依次会对这个节点的右值增加2,所以后续节点的数量可以这样计算:
descendants = (right – left – 1) / 2
利用这个简单的公式,我可以立刻告诉你2-11的“Fruit”节点有4个后续节点,8-9的“Banana”节点只是1个子节点,而不是父节点。

添加一个节点

添加和删除节点的方法是更新新节点右边的所有节点。让我们看一下例子。我们要添加一种新的水果——“Strawberry”,作为“Red”的最后一个子节点。首先,我们要腾出一个空间。“Red”的右值要从6变成8,7-10的“Yellow”节点要变成9-12,如此类推。更新“Red”节点意味着我们要把所有左值和右值大于5的节点加上2。
我们用一下查询:

UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;
现在我们可以添加一个新的节点“Strawberry”来填补这个新的空间。
这个节点左值为6右值为7。
INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';

缺点
首先,改进前序遍历树算法看上去很难理解。它当然没有邻接列表方法简单。然而,一旦习惯了左值和右值这两个属性,就会变得清晰起来,你可以用这个技术来完成邻接列表能完成的所有事情,同时改进前序遍历树算法更快。当然,更新树需要很多查询,要慢一点,但是取得节点却可以只用一个查询。

对树节点的操作
–获取某个节点的父级节点

select p.* from t_mytreenode c,t_mytreenode p
where p.leftvaluec.rightvalue
and p.isolatedflag = c.isolatedflag
and c.id=5
and c.id=12

–汇总查询

select sum(child.value),parent.id, parent.name
from T_MYTREENODE child,T_MYTREENODE parent
where
child.LEFTVALUE>=parent.LEFTVALUE
and
child.rightvalue--获取某个节点的下一级节点
1 select c.* from t_mytreenode c,t_mytreenode p
where c.leftValue>p.leftValue
and c.leftValue--插入对象(插在同级下最后一个位置:
父亲右值之后的所有值加2,包括父亲的右值)
1 update t_mytreenode t set t.rightvalue = t.rightvalue+2
where t.rightvalue>=16 and t.isolatedflag=2
update t_mytreenode t set t.leftvalue = t.leftvalue+2
	where t.leftvalue>=16 and t.isolatedflag=2
insert into
t_mytreenode t(t.id,t.name,t.leftvalue,t.rightvalue,
t.mlevel,t.value,t.isolatedflag)
values(13,'2.1.1.3',16,17,4,6,2)  --新节点的左右值应该是父节点的右值及右值+1

–插入对象(插在同级下第一个位置:父亲左值之后的所有值加2,不包括父亲的左值)

update t_mytreenode t set t.rightvalue = t.rightvalue+2
	where t.rightvalue>3 and t.isolatedflag=2;
update t_mytreenode t set t.leftvalue = t.leftvalue+2
	where t.leftvalue>3 and t.isolatedflag=2;
insert into
t_mytreenode t(t.id,t.name,t.leftvalue,t.rightvalue,
t.mlevel,t.value,t.isolatedflag)
values(14,'2.1.1.4',4,5,4,7,2);  --新节点的左右值应该是父节点的左值+1及左值+2

除非注明,文章为IT热血青年原创,欢迎转载!转载请注明本文地址,谢谢。
本文地址:http://blog.itblood.com/tree-structure-storage-and-optimization.html

  1. 2016年2月26日13:07 | #1

    你网站首页非常漂亮,非常喜欢,现在可以交换链接吗?

  1. 本文目前尚无任何 trackbacks 和 pingbacks.