R树索引

如索引基础概念页面中介绍的，R 树索引通常用于加快空间搜索的速度。

R 树索引可以存储和搜索各种形状。

例如：

一个点表示为宽度和高度均为 1 的矩形，而起始坐标为 15, 844、结束坐标为 0, 3647 的线段则存储为左上角位于 15， 844、右下角位于 0， 3647 的矩形。要确定两条线是否相交，或者一个点是否在给定区域内（由圆、矩形等描述），会执行R 树搜索以找出所有重叠的矩形。对于每个匹配项，在应用程序代码中会进一步进行测试，以确定条件是否实际满足。
假设我们有如下线条：

查找与（75，15）（20，70）相交的所有线段，会返回包含（35，25）（20，30）的矩形，因为这两个矩形有重叠。应用程序会提取该对象的其他信息，例如它是条线段以及其起始和结束坐标，并得出结论这条线段不与关键线段相交；然后继续处理索引搜索返回的下一个重叠矩形。

请注意，任何具有坐标{(X1, Y1), (X2, Y2), ... (Xn, Yn)}的形状都可以以这种方式存储和搜索。

例如，考虑一个多边形：

这里的 X 坐标为 35、55、65、70、85，Y 坐标为 30、33、35、45、50、63。边界矩形是左上角顶点为（Xmax，Ymin），右下角顶点为（Xmin，Ymax）的矩形，其中 Xmin = min(Xi)，Ymin = min(Yi)，Xmax = max(Xi)，Ymax = max(Yi)。在这种情况下，Xmax = 85，Ymin = 30，Xmin = 35，Ymax = 63，我们的矩形左上角和右下角分别为（85，30）和（35，63）。

R 树搜索可以返回满足以下条件的矩形：

与给定的坐标完全匹配；
重叠给定的坐标；
完全包含给定的坐标；
按照与指定参考矩形或点的距离顺序排列。

尽管矩形坐标可以通过多种方式指定，例如指定对应于左上角和右下角的两个点，但对于 r 树索引，矩形必须以最大和最小坐标的数组形式指定。例如，二维矩形表示为一个数组：

    xMin,yMin,xMax,yMax

换句话说，如上图所示，使用 X 和 Y 坐标，<xMin, yMin> 坐标对应于左下角的点，而 <xMax, yMax> 则是右上角的点。三维“矩形”的表示方式如下：

    xMin,yMin,zMin,xMax,yMax,zMax

R 树搜索示例

为了演示R 树索引的用法，请看下面图表中的矩形和点：

两个实线矩形由坐标 <25,25> - <50,35> 和 <5,45> - <60,65> 定义，虚线矩形由坐标 <20,30> - <85,50> 和 <45,60> - <10,55> 定义。

为了将这些矩形存储在数据库中，我们可能会创建一个名为Boxes 的类，并为其添加一个类似以下的R 树索引：

    class Boxes
    {
        int2 square[4];
         
        rtree <square> ridx;
    };

我们将使用所选的 API 插入这四个矩形。

R 树索引支持四种类型的搜索操作：等于（equals）、包含（contains）、重叠（overlaps ）或邻近（neighborhood）。

要执行R 树搜索，与执行其他索引类型的搜索一样，首先必须创建一个游标。然后，若要在数据库中搜索特定的矩形，我们需要执行游标搜索操作，操作类型等于指定矩形（四个坐标）。

要查找与指定矩形重叠的矩形，需使用重叠操作类型。例如，在图中查找虚线矩形 3（<20,30> - <85,50>），会“找到”两个实线矩形 1 和 2。

同样地，要查找包含指定矩形的矩形，需使用包含操作类型。例如，查找虚线矩形 4（<45,60> - <10，55>）会“找到”仅有的更大的实线矩形 2（<5，45> - <60，65>）。

使用邻域操作类型将返回索引中所有矩形，这些矩形按照与指定矩形或点的距离排序。（请注意，点可以指定为二维坐标数组，也可以指定为“退化矩形”，即左下角和右上角的坐标值相同。尽管内部搜索算法（特别是重叠和包含操作类型）处理的是“框”，会将点提升为矩形，但在某些情况下，存储点所需的内存明显少于存储矩形。）

在当前示例中，指定点 <10,10> 将会返回所有四个插入的矩形，从左到右排序，因为指定的点位于每个矩形的左侧。此搜索会计算目标矩形（本例中为 <10,10>）的左下角（minX, minY）点到索引中每个矩形的最近点的欧几里得距离，并按距离从小到大返回结果。

R 树索引游标与常规树（B 树）类型的游标具有不同的语义。与常规树索引的搜索操作将游标定位在第一个匹配项，或者在部分键搜索的情况下定位在最近匹配项之前不同，R 树索引游标是在搜索结果集上操作。

对于 R 树游标，游标操作 first、last、next 和 prev 是在对象集合内进行的。