STR-R树

R树

R-tree是一种具有层次结构的数据结构派生自B-tree，是为了相交查询而设计的。R-tree存储了一个矩形的集合，这个集合可以通过插入和删除操作在任意时间更改。对于任意的图形对象，通过其最小外接矩形来表示。对于二维及以上的情形，R-tree非常容易建立。

R-tree中的每个节点最多存储$b$个条目。每个条目包含一个矩形$R$和一个指针$P$，对于叶等级的节点，R是一个范围，通过指针P来定向。在内部节点中，$R$是子树中存储的所有矩形的公共外接矩形，通过$P$指向。值得注意的是，穿过树的任意路径都应该是一系列嵌套的矩形，最后一个包含实际的数据对象。同时还要注意，任意层级的矩形都可能会压盖，此外，通过任一对象集创建的R树绝不是是唯一的。

对于执行的一次查询$Q$，与查询区域相交的所有矩形都要被检索并检验。这个检索过程是通过一个简单的递归过程来完成的，该递归过程始于根节点，并且沿着树的几个不同路径执行。对于某个节点，首先检索存储在这个节点的所有与$Q$区域相交的矩形。如果节点是个内部节点，则通过递归搜索检索到与检索到的矩形相对应的子树。否则，这个节点是叶节点，检索到的矩形就可以很方便的得到。

Packing Alogrithms

一般过程

1. 预处理数据文件，处理后有：$r$个矩形，排序后，分别保存在$\frac r b$个连续的的分组（每个含有$b$个矩形），每个组中的矩形被计划放入叶级节点中。注意，最后一组中可能少于$b$个矩形。

2. 将这$\frac r b$个矩形组加载进页面并且输出每个叶级页面的MBR和页码进入一个临时文件。页码被用做更高级别的节点中的子指针。

3. 递归打包这些MBR进下一级的节点，向上执行，直到根节点被创建。

对于不同的打包算法，这三个步骤只在每个层级矩形如何排序中有所不同。

Nearest-X

矩形使用x坐标排序。

Hilbert Sort

矩形使用Hilbert（分型）空间填充曲线。排序时使用的矩形中心点沿曲线到原点的距离。这决定了矩形放入R-tree中节点的顺序。

Sort-Tile-Recursive

考虑一个$k$维数据集包含$r$个超矩形。一个超矩形被$k$个由$[a,b]$组成的intervals，点的位置为第$i$个坐标落在地i个interval内。

预设item个数为$r$，每个叶级节点的容量为$b$

STR最适合处理$2$维的情形。相应的，我们想象平面上有一组矩形。首先，假设一维空间，若每个节点容量为$b$，则可以划分$\frac r b$个叶级节点，类比后我们用$\sqrt{\frac r b}$个垂直切片切分数据空间，这样，每个切片可以包含足够的矩形来满足大约$\sqrt{\frac r b}$个节点容量。接下来，我们设想矩形的中心点作为坐标，确定了叶级页面的数量$P =\ulcorner \frac r b \urcorner$，令$S=\sqrt P$。用$x$坐标排序，并将他们分配到$S$个垂直分组中。每个切片中包含排序列表中的一连串的$S \cdot b$个连续的矩形。注意最后一个切片可能矩形的数量会比$S \cdot b$少。之后，再将切片中的矩形按照$y$坐标排序并将它们$b$个一组打包插入叶级节点。