树形结构数据存储方案（五）：区间嵌套

（点击上方公众号，可快速关注）

来源：标点符

www.biaodianfu.com/nested-intervals.html

如有好文章投稿，请点击 → 这里了解详情

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

区间嵌套法原理

如果节点区间[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点的分子为：

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点的分母为：

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点的分子:

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 的分母：

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是否能解码出来：

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，则代表其为根节点)

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;

SELECT CONCAT(parent_numer(11,8),'/',parent_denom(11,8)) AS parent

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

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;

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

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的自定义函数不支持递归查询。

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

计算节点层级的方法：

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个辅助函数：

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;

CREATE DEFINER = `root`@`localhost` FUNCTION `child_denom`(`num` int,`den` int,`child` int)

RETURNS int(11)

BEGIN

RETURN den*power(2, child);

END;

再来编写逆转函数：

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;

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

系列回顾

• 树形结构数据存储方案（一）：邻接列表模式

• 树形结构数据存储方案（二）： 物化路径

• 树形结构数据存储方案（三）：闭包表

• 树形结构数据存储方案（四）：左右值编码
  

看完本文有收获？请转发分享给更多人

关注「数据库开发」，提升 DB 技能