皇上,还记得我吗?我就是1999年那个Linux伊甸园啊-----24小时滚动更新开源资讯,全年无休!

树形结构数据存储方案(五):区间嵌套

前面的一篇文章介绍了左右值编码,不知道大家注意到了没有,如果数据庞大,每次更新都需要更新差不多全表,效率较低没有更好的方式?今天我们就来研究下区间嵌套法。

区间嵌套法原理

如果节点区间[clft, crgt]与[plft, prgt]存在如下关系:plft <= clft and crgt >= prgt,则[clft, crgt]区间里的点是[plft, prgt]的子节点。基于此假设我们就可以通过对区间的不断的向下划来获取新的区间。举例:如果在区间[plft, prgt]中存在一个空白区间[lft1, rgt1],如果要加入一个[plft,lft1]、[rgt1,prgt]同级的区间,只需插入节点:[(2*lft1+rgt1)/3,  (rgt1+2*lft)/3]。在添加完节点后我们还留下[lft1,(2*lft1+rgt1)/3]和 [(rgt1+2*lft)/3,rgt1]两个空余的空间用来添加更多的子节点。

树形结构数据存储方案(五):区间嵌套如果我们把区间放在二位平面上,把rgt当成是x轴,lft当做是y轴,纳闷嵌套的区间数差不多是这样的:

树形结构数据存储方案(五):区间嵌套

每个节点[lft, rgt]拥有的子节点都被包含在y >= lft & x <= rgt中。同时y >= clft & x <= crgt所在的空间也是y >= plft  & x <= prgt的子集。另外由于新增的右区间都小于已有的左区间,所以新增的节点均在y=x这条直线以下。

区间嵌套法实现

了解了区间嵌套法的原理后,接下来我们就要考虑如何实现他,原则上初始的区间使用任何区间都是可以的,这里我们使用的是[0,1]作为根区间。

树形结构数据存储方案(五):区间嵌套

首先,我们在XY平面上定义2个点。深度优先集合点和广度有限集合点,针对点<x=1,y=1/2>的深度优先集合点为<x=1,y=1>,广度优先集合点为<x=1/2,y=1/2>。接下来我们定义第一个子节点的位置为父节点和深度优先集合点的中间点。兄弟节点则为前一个子节点到广度优先集合点的中间点,如上图所示,节点1.2的位置为<x=3/4, y=5/8>。

另外仔细看我们可以看到点与点之间的关系。另外如果我们知道x和y的和,我们就能反推出x,y的值(具体的逻辑是什么,我现在也还没有搞懂,有知道的朋友可以帮忙解释下)。

我们以节点<x=3/4, y=5/8>为例,我们可以得到他的和为11/8。

我们定义11为分子(numerator),8为分母(denominator),则x点的分子为:

x点的分母为:

Y点的分子:

Y 的分母:

接下来我们来测试下,X与Y是否能解码出来:

树形结构数据存储方案(五):区间嵌套

结果与节点1.2的位置为<x=3/4, y=5/8>完全一致。现在我们知道只需要一个分数即可表示平面上的一个点。

如有已经有分数11/8如何获取该节点的父节点?(如果分子为3,则代表其为根节点)

计算当前节点在同级所在的位置:

有了查询父节点的方法及当前节点所在同级中的位置的方法,即可通过这两个的组合,将节点的路径给计算出来。

按照以上方法添加后进行测试,返回[Err] 1424 – Recursive stored functions and triggers are not allowed. 即MySQL的自定义函数不支持递归查询。

SELECT path (11, 8) 的结果为 1.2

计算节点层级的方法:

我们知道了如何将编码过的节点转成目录形式,如何逆转呢?以下是方法:

先添加2个辅助函数:

再来编写逆转函数:

select CONCAT(path_numer(‘2.1.3′),’/’,path_denom(‘2.1.3’)) 结果为51/64

参考资料:

  • http://www.rampant-books.com/art_vadim_nested_sets_sql_trees.htm
  • 转自 http://blog.jobbole.com/112339/