# 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$$个一组打包插入叶级节点。