数据存储方案-区间嵌套

区间嵌套法原理

如果节点区间[clft, crgt]与[plft, prgt]存在如下关系:clft >= plft and crgt <= prgt,则[plft, prgt]区间里的点包含[clft, crgt]的子节点。基于此假设我们就可以通过对区间的不断的向下划来获取新的区间。

举例:如果在区间[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轴:

原文地址:https://www.cnblogs.com/wade-luffy/p/7730179.html