内容简介：前面的一篇文章介绍了左右值编码，不知道大家注意到了没有，如果数据庞大，每次更新都需要更新差不多全表，效率较低没有更好的方式？今天我们就来研究下区间嵌套法。
前面的一篇文章介绍了左右值编码，不知道大家注意到了没有，如果数据庞大，每次更新都需要更新差不多全表，效率较低没有更好的方式？今天我们就来研究下区间嵌套法。
区间嵌套法原理
如果节点区间[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点的分子为：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
CREATE DEFINER = `root`@`localhost` FUNCTION `x_numer`(`numer` int,`denom` int) RETURNS int(11) BEGIN DECLARE ret_num INT; DECLARE ret_den INT; SET ret_num := numer+1; SET ret_den := denom*2; WHILE floor(ret_num/2) = ret_num/2 DO SET ret_num := ret_num/2; SET ret_den := ret_den/2; END WHILE; RETURN ret_num; END; |
x点的分母为：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
CREATE DEFINER = `root`@`localhost` FUNCTION `x_ denom`(`numer` int,`denom` int) RETURNS int(11) BEGIN DECLARE ret_num INT; DECLARE ret_den INT; SET ret_num := numer+1; SET ret_den := denom*2; WHILE floor(ret_num/2) = ret_num/2 DO SET ret_num := ret_num/2; SET ret_den := ret_den/2; END WHILE; RETURN ret_den; END; |
Y点的分子:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
CREATE DEFINER = `root`@`localhost` FUNCTION `y_numer`(`numer` int,`denom` int) RETURNS int(11) BEGIN DECLARE num INT; DECLARE den INT; SET num := x_numer(numer, denom); SET den := x_denom(numer, denom); WHILE den < denom DO SET num := num*2; SET den := den*2; END WHILE; SET num := (numer - num); WHILE floor(num/2) = num/2 DO SET num := num/2; SET den := den/2; END WHILE; RETURN num; END; |
Y 的分母：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
CREATE DEFINER = `root`@`localhost` FUNCTION `y_denom`(`numer` int,`denom` int) RETURNS int(11) BEGIN DECLARE num INT; DECLARE den INT; SET num := x_numer(numer, denom); SET den := x_denom(numer, denom); WHILE den < denom DO SET num := num*2; SET den := den*2; END WHILE; SET num := (numer - num); WHILE floor(num/2) = num/2 DO SET num := num/2; SET den := den/2; END WHILE; RETURN den; END; |
接下来我们来测试下，X与Y是否能解码出来：
|
1 2 3 |
SELECT CONCAT(x_numer (11, 8),'/',x_denom (11, 8)) AS X, CONCAT(y_numer (11, 8),'/',y_denom (11, 8)) AS Y |
结果与节点1.2的位置为<x=3/4, y=5/8>完全一致。现在我们知道只需要一个分数即可表示平面上的一个点。
如有已经有分数11/8如何获取该节点的父节点？(如果分子为3，则代表其为根节点)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
CREATE DEFINER = `root`@`localhost` FUNCTION `parent_numer`(`numer` int,`denom` int) RETURNS int(11) BEGIN DECLARE ret_num INT; DECLARE ret_den INT; IF numer=3 THEN RETURN denom/2; END IF; SET ret_num := (numer-1)/2; SET ret_den := denom/2; WHILE floor((ret_num-1)/4) = (ret_num-1)/4 DO SET ret_num := (ret_num+1)/2; SET ret_den := ret_den/2; END WHILE; RETURN ret_num; END; |
|
1 |
SELECT CONCAT(parent_numer(11,8),'/',parent_denom(11,8)) AS parent |
计算当前节点在同级所在的位置：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
CREATE DEFINER = `root`@`localhost` FUNCTION `parent_denom`(`numer` int,`denom` int) RETURNS int(11) BEGIN DECLARE ret_num INT; DECLARE ret_den INT; IF numer=3 THEN RETURN NULL; END IF; SET ret_num := (numer-1)/2; SET ret_den := denom/2; WHILE floor((ret_num-1)/4) = (ret_num-1)/4 DO SET ret_num := (ret_num+1)/2; SET ret_den := ret_den/2; END WHILE; RETURN ret_den; END; |
有了查询父节点的方法及当前节点所在同级中的位置的方法，即可通过这两个的组合，将节点的路径给计算出来。
|
1 2 3 4 5 6 7 8 |
CREATE DEFINER = `root`@`localhost` FUNCTION `path`(`numer` int,`denom` int) RETURNS varchar(255) BEGIN IF numer is NULL THEN RETURN ''; END IF; RETURN path(parent_numer(numer, denom),parent_denom(numer, denom))|| ‘.’ || sibling_number(numer, denom); END; |
按照以上方法添加后进行测试，返回[Err] 1424 – Recursive stored functions and triggers are not allowed. 即 MySQL 的自定义函数不支持递归查询。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
CREATE DEFINER = `root`@`localhost` FUNCTION `path`(`numer` int,`denom` int) RETURNS varchar(255) BEGIN DECLARE numer_temp INT; DECLARE denom_temp INT; DECLARE path_result VARCHAR(255); DECLARE path_temp VARCHAR(255); DECLARE sn VARCHAR(255); SET path_temp := ''; WHILE numer IS NOT NULL DO IF path_temp = '' THEN SET path_result := sibling_number(numer, denom); ELSE SET path_result := CONCAT(sibling_number(numer, denom),'.',path_temp); END IF; SET path_temp := path_result; SET numer_temp := parent_numer(numer, denom); SET denom_temp := parent_denom(numer, denom); SET numer := numer_temp; SET denom := denom_temp; END WHILE; RETURN path_result; END; |
SELECT path (11, 8) 的结果为 1.2
计算节点层级的方法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
CREATE DEFINER = `root`@`localhost` FUNCTION `node_level`(`numer` int,`denom` int) RETURNS int(11) BEGIN DECLARE ret_num INT; DECLARE ret_den INT; DECLARE ret INT; SET ret =1; IF numer=3 THEN return 1; END IF; WHILE numer!=3 DO SET ret_num := parent_numer(numer, denom); SET ret_den := parent_denom(numer, denom); SET numer := ret_num; SET denom := ret_den; SET ret := ret + 1; END WHILE; RETURN ret; END; |
我们知道了如何将编码过的节点转成目录形式，如何逆转呢？以下是方法：
先添加2个辅助函数：
|
1 2 3 4 5 |
CREATE DEFINER = `root`@`localhost` FUNCTION `child_numer`(`num` int,`den` int,`child` int) RETURNS int(11) BEGIN RETURN num * power(2, child) + 3 - power(2, child); END; |
|
1 2 3 4 5 |
CREATE DEFINER = `root`@`localhost` FUNCTION `child_denom`(`num` int,`den` int,`child` int) RETURNS int(11) BEGIN RETURN den*power(2, child); END; |
再来编写逆转函数：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
CREATE DEFINER = `root`@`localhost` FUNCTION `path_numer`(`path` varchar(255)) RETURNS int(11) BEGIN DECLARE num INT; DECLARE den INT; DECLARE postfix VARCHAR(255); DECLARE sibling VARCHAR(255); SET num := 1; SET den := 1; SET postfix := CONCAT(path,'.'); WHILE length(postfix) > 1 DO SET sibling := SUBSTR(postfix, 1, instr(postfix,'.')-1); SET postfix := SUBSTR(postfix, instr(postfix,'.')+1); SET num := child_numer(num,den,sibling+0); SET den := child_denom(num,den,sibling+0); END WHILE; RETURN num; END; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
CREATE DEFINER = `root`@`localhost` FUNCTION `path_denom`(`path` varchar(255)) RETURNS int(11) BEGIN DECLARE num INT; DECLARE den INT; DECLARE postfix VARCHAR(255); DECLARE sibling VARCHAR(255); SET num := 1; SET den := 1; SET postfix := CONCAT(path,'.'); WHILE length(postfix) > 1 DO SET sibling := SUBSTR(postfix, 1, instr(postfix,'.')-1); SET postfix := SUBSTR(postfix, instr(postfix,'.')+1); SET num := child_numer(num,den,sibling+0); SET den := child_denom(num,den,sibling+0); END WHILE; RETURN den; END; |
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
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- MyBatis collection 集合嵌套查询树形节点
- MySQL 实现树形的遍历
- 巧用 MyBatis 构建树形结构
- js 将线性数据转为树形
- 树形结构数据存储方案（三）：闭包表
- 树形结构数据存储方案（二）： 物化路径
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
HTTPS权威指南
[英] Ivan Risti? / 杨洋、李振宇、蒋锷、周辉、陈传文 / 人民邮电出版社 / 2016-9 / 99.00元
本书是集理论、协议细节、漏洞分析、部署建议于一体的详尽Web应用安全指南。书中具体内容包括：密码学基础，TLS协议，PKI体系及其安全性，HTTP和浏览器问题，协议漏洞；最新的攻击形式，如BEAST、CRIME、BREACH、Lucky 13等；详尽的部署建议；如何使用OpenSSL生成密钥和确认信息；如何使用Apache httpd、IIS、Nginx等进行安全配置。一起来看看 《HTTPS权威指南》 这本书的介绍吧!
