R_tree
R树是B树 向多维空间发展的另一种形式，它将对象空间按范围划分，每个结点都对应一个区域和一个磁盘页，非叶结点的磁盘页中存储其所有子结点的区域范围，非叶结点的 所有子结点的区域都落在它的区域范围之内；叶结点的磁盘页中存储其区域范围之内的所有空间对象的外接矩形。R树是一种动态索引结构。
（1）R-Tree是n 叉树，n称为R-Tree的扇（fan）。
（2）每个结点对应一个矩形。
（3）叶子结点上包含了小于等于n 的对象，其对应的矩为所有对象的外包矩形。
（4）非叶结点的矩形为所有子结点矩形的外包矩形。
R-Tree的定义很宽泛，同一套数据构造R-Tree，不同方可以得到差别很大的结构。什么样的结构比较优呢？有两标准：
（1）位置上相邻的结点尽量在树中聚集为一个父结点。
（2）同一层中各兄弟结点相交部分比例尽量小。
R-树是一种用于处理多维数据的数据结构，用来访问二维或者更高维区域对象组成的空间数据.R树是一棵平衡树。树上有两类结点：叶子结点和非叶子结点。每一个结点由若干个索引项构成。对于叶子结点，索引项形如(Index，Obj_ID)。其中，Index表示包围空间数据对象的最小外接矩形MBR，Obj_ID标识一个空间数据对象。对于一个非叶子结点，它的索引项形如(Index，Child_Pointer)。 Child_Pointer 指向该结点的子结点。Index仍指一个矩形区域，该矩形区域包围了子结点上所有索引项MBR的最小矩形区域。
符号说明：M：结点中单元的最大数目，m(1<= m <= M/2)为非根结点中单元个数的下限。
一个R树满足如下性质:
(1) 每一个叶子结点中包含的单元的个数介于m和M之间，除非他同样是根结点
(2) 每一个叶子结点中的单元(I, tuple-identifier),I为包含所有子结点的最小包含矩形(MBR)，tuple-identifier是指向存储记录的指针。
(3) 每一个非叶子结点的子结点数介于m和M之间，除非他是根结点
(4) 每一个非叶子结点单元(I, child -pointer)I是包含子结点的最小矩形MBR，child-pointer是指向子结点的指针。通过该指针逐层递归，可以访问到叶子结点。
(5) 根结点至少有两个子结点，除非他同时是叶子结点
(6) 所有的叶子结点都处在树的同一层上。
算法描述编辑
算法描述如下：
对象数为n，扇区大小定为fan。
（1）估计叶结点数k=n/fan。
（2）将所有几何对象按照其矩形外框中心点的x值排序。
（3）将排序后的对象分组，每组大小为 fan，最后一组可能不满员。
（4）上述每一分组内按照几何对象矩形外框中心点的y值排序。
（5）排序后每一分组内再分组，每组大小为fan。
（6）每一小组成为叶结点，叶子结点数为nn。
（7）k=nn，返回1。
其他索引结构编辑
R+树
在Guttman的工作的基础上，许多R树的变种被开发出来， Sellis等提出了R+树 [4] ，R+树与R树类似，主要区别在于R+树中兄弟结点对应的空间区域无重叠，这样划分空间消除了R树因允许结点间的重叠而产生的“死区域”（一个结点内不含本结点数据的空白区域），减少了无效查询数，从而大大提高空间索引的效率，但对于插入、删除空间对象的操作，则由于操作要保证空间区域无重叠而效率降低。同时R+树对跨区域的空间物体的数据的存储是有冗余的，而且随着数据库中数据的增多，冗余信息会不断增长。Greene也提出了他的R树的变种。
R树
在1990年，Beckman和Kriegel提出了最佳动态R树的变种——R树 [4] 。R树和R树一样允许矩形的重叠，但在构造算法R树不仅考虑了索引空间的“面积”，而且还考虑了索引空间的重叠。该方法对结点的插入、分裂算法进行了改进，并采用“强制重新插入”的方法使树的结构得到优化。但R树算法仍然不能有效地降低空间的重叠程度，尤其是在数据量较大、空间维数增加时表现的更为明显。R树无法处理维数高于20的情况。
QR树
QR树 [5] 利用四叉树将空间划分成一些子空间，在各子空间内使用许多R树索引，从而改良索引空间的重叠。QR树结合了四叉树与R树的优势，是二者的综合应用。实验证明：与R树相比，QR树以略大（有时甚至略小）的空间开销代价，换取了更高的性能，且索引目标数越多，QR树的整体性能越好。
SS树
SS树对R树进行了改进，通过以下措施提高了最邻近查询的性能：用最小边界圆代替最小边界矩形表示区域的形状，增强了最邻近查询的性能，减少将近一半存储空间；SS树改进了R树的强制重插机制。当维数增加到5是，R树及其变种中的边界矩形的重叠将达到90%，因此在高维情况（≧5）下，其性能将变的很差，甚至不如顺序扫描。
X树
X树 [6] 是线性数组和层状的R树的杂合体，通过引入超级结点，大大地减少了最小边界矩形之间的重叠，提高了查询效率。X树用边界圆进行索引，边界矩形的直径（对角线）比边界圆大，SS树将点分到小直径区域。由于区域的直径对最邻近查询性能的影响较大，因此SS树的最邻近查询性能优于R树；边界矩形的平均容积比边界圆小，R树将点分到小容积区域；由于大的容积会产生较多的覆盖，因此边界矩形在容积方面要优于边界圆。SR树既采用了最小边界圆（MBS），也采用了最小边界矩形（MBR），相对于SS树，减小了区域的面积，提高了区域之间的分离性，相对于R树，提高了邻近查询的性能。
1984年，加州大学伯克利分校的Guttman发表了一篇题为“R-trees: a dynamic index structure for spatial searching”的论文，向世人介绍了R树这种处理高维空间存储问题的数据结构。
R树在数据库等领域做出的功绩是非常显著的。它很好的解决了在高维空间搜索等问题。举个R树在现实领域中能够解决的例子：查找20英里以内所有的餐厅。如果没有R树你会怎么解决？一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中，一个字段记录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满足要求。如果一个地区有100家餐厅的话，我们就要进行100次位置计算操作了，如果应用到谷歌地图这种超大数据库中，这种方法便必定不可行了。
R树就很好的解决了这种高维空间搜索问题。它把B树的思想很好的扩展到了多维空间，采用了B树分割空间的思想，并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，R树就是一棵用来存储高维数据的平衡树。
R树是B树在高维空间的扩展，是一棵平衡树。每个R树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。根据R树的这种数据结构，当我们需要进行一个高维空间查询时，我们只需要遍历少数几个叶子结点所包含的指针，查看这些指针指向的数据是否满足要求即可。这种方式使我们不必遍历所有数据即可获得答案，效率显著提高。
R树运用了空间分割的理念，这种理念是如何实现的呢？R树采用了一种称为MBR(Minimal Bounding Rectangle)的方法，在此我把它译作“最小边界矩形”。从叶子结点开始用矩形（rectangle）将空间框起来，结点越往上，框住的空间就越大，以此对空间进行分割。
先来看图（b），首先我们假设所有数据都是二维空间下的点，图中仅仅标志了R8区域中的数据，也就是那个shape of data object。别把那一块不规则图形看成一个数据，我们把它看作是多个数据围成的一个区域。为了实现R树结构，我们用一个最小边界矩形恰好框住这个不规则区域，这样，我们就构造出了一个区域：R8。R8的特点很明显，就是正正好好框住所有在此区域中的数据。其他实线包围住的区域，如R9，R10，R12等都是同样的道理。这样一来，我们一共得到了12个最最基本的最小矩形。这些矩形都将被存储在子结点中。下一步操作就是进行高一层次的处理。我们发现R8，R9，R10三个矩形距离最为靠近，因此就可以用一个更大的矩形R3恰好框住这3个矩形。同样道理，R15，R16被R6恰好框住，R11，R12被R4恰好框住，等等。所有最基本的最小边界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住这些矩形。我想大家都应该理解这个数据结构的特征了。用地图的例子来解释，就是所有的数据都是餐厅所对应的地点，先把相邻的餐厅划分到同一块区域，划分好所有餐厅之后，再把邻近的区域划分到更大的区域，划分完毕后再次进行更高层次的划分，直到划分到只剩下两个最大的区域为止。要查找的时候就方便了。
下面就可以把这些大大小小的矩形存入我们的R树中去了。根结点存放的是两个最大的矩形，这两个最大的矩形框住了所有的剩余的矩形，当然也就框住了所有的数据。下一层的结点存放了次大的矩形，这些矩形缩小了范围。每个叶子结点都是存放的最小的矩形，这些矩形中可能包含有n个数据。
在这里，读者先不要去纠结于如何划分数据到最小区域矩形，也不要纠结怎样用更大的矩形框住小矩形，这些都是下一节我们要讨论的。
讲完了基本的数据结构，我们来讲个实例，如何查询特定的数据。又以餐厅为例，假设我要查询广州市天河区天河城附近一公里的所有餐厅地址怎么办？打开地图（也就是整个R树），先选择国内还是国外（也就是根结点）。然后选择华南地区（对应第一层结点），选择广州市（对应第二层结点），再选择天河区（对应第三层结点），最后选择天河城所在的那个区域（对应叶子结点，存放有最小矩形），遍历所有在此区域内的结点，看是否满足我们的要求即可。怎么样，其实R树的查找规则跟查地图很像吧？
一棵R树满足如下的性质：
除非它是根结点之外，所有叶子结点包含有m至M个记录索引（条目）。作为根结点的叶子结点所具有的记录个数可以少于m。通常，m=M/2。
对于所有在叶子中存储的记录（条目），I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（注意：此处所说的“矩形”是可以扩展到高维空间的）。
每一个飞叶子结点拥有m至M个孩子结点，除非它是根结点。
对于在非叶子结点上的每一个条目，i是最小的可以在空间上完全覆盖这些条目所代表的店的矩形（同性质2）。
所有叶子结点都位于同一层，因此R树为平衡树。
叶子结点的结构
先来探究一下叶子结点的结构。叶子结点所保存的数据形式为：(I, tuple-identifier)。
其中，tuple-identifier表示的是一个存放于数据库中的tuple，也就是一条记录，它是n维的。I是一个n维空间的矩形，并可以恰好框住这个叶子结点中所有记录代表的n维空间中的点。I=(I0,I1,…,In-1)。
I所代表的就是图中的矩形，其范围是a<=I0<=b，c<=I1<=d。有两个tuple-identifier，在图中即表示为那两个点。这种形式完全可以推广到高维空间。大家简单想想三维空间中的样子就可以了。这样，叶子结点的结构就介绍完了。
非叶子结点
非叶子结点的结构其实与叶子结点非常类似。想象一下B树就知道了，B树的叶子结点存放的是真实存在的数据，而非叶子结点存放的是这些数据的“边界”，或者说也算是一种索引（有疑问的读者可以回顾一下上述第一节中讲解B树的部分）。
同样道理，R树的非叶子结点存放的数据结构为：(I, child-pointer)。
其中，child-pointer是指向孩子结点的指针，I是覆盖所有孩子结点对应矩形的矩形 D,E,F,G为孩子结点所对应的矩形。A为能够覆盖这些矩形的更大的矩形。这个A就是这个非叶子结点所对应的矩形。这时候你应该悟到了吧？无论是叶子结点还是非叶子结点，它们都对应着一个矩形。树形结构上层的结点所对应的矩形能够完全覆盖它的孩子结点所对应的矩形。根结点也唯一对应一个矩形，而这个矩形是可以覆盖所有我们拥有的数据信息在空间中代表的点的。
我个人感觉这张图画的不那么精确，应该是矩形A要恰好覆盖D,E,F,G，而不应该再留出这么多没用的空间了。
R树的操作
搜索
R树的搜索操作很简单，跟B树上的搜索十分相似。它返回的结果是所有符合查找信息的记录条目。而输入是什么？就我个人的理解，输入不仅仅是一个范围了，它更可以看成是一个空间中的矩形。也就是说，我们输入的是一个搜索矩形。
先给出伪代码：
Function：Search
描述：假设T为一棵R树的根结点，查找所有搜索矩形S覆盖的记录条目。
S1:[查找子树] 如果T是非叶子结点，如果T所对应的矩形与S有重合，那么检查所有T中存储的条目，对于所有这些条目，使用Search操作作用在每一个条目所指向的子树的根结点上（即T结点的孩子结点）。
S2:[查找叶子结点] 如果T是叶子结点，如果T所对应的矩形与S有重合，那么直接检查S所指向的所有记录条目。返回符合条件的记录。
我们通过下图来理解这个Search操作。
阴影部分所对应的矩形为搜索矩形。它与根结点对应的最大的矩形（未画出）有重叠。这样将Search操作作用在其两个子树上。两个子树对应的矩形分别为R1与R2。搜索R1，发现与R1中的R4矩形有重叠，继续搜索R4。最终在R4所包含的R11与R12两个矩形中查找是否有符合条件的记录。搜索R2的过程同样如此。很显然，该算法进行的是一个迭代操作。
插入
R树的插入操作也同B树的插入操作类似。当新的数据记录需要被添加入叶子结点时，若叶子结点溢出，那么我们需要对叶子结点进行分裂操作。显然，叶子结点的插入操作会比搜索操作要复杂。插入操作需要一些辅助方法才能够完成。
来看一下伪代码：
Function：Insert
描述：将新的记录条目E插入给定的R树中。
I1：[为新记录找到合适插入的叶子结点] 开始ChooseLeaf方法选择叶子结点L以放置记录E。
I2：[添加新记录至叶子结点] 如果L有足够的空间来放置新的记录条目，则向L中添加E。如果没有足够的空间，则进行SplitNode方法以获得两个结点L与LL，这两个结点包含了所有原来叶子结点L中的条目与新条目E。
I3：[将变换向上传递] 开始对结点L进行AdjustTree操作，如果进行了分裂操作，那么同时需要对LL进行AdjustTree操作。
I4：[对树进行增高操作] 如果结点分裂，且该分裂向上传播导致了根结点的分裂，那么需要创建一个新的根结点，并且让它的两个孩子结点分别为原来那个根结点分裂后的两个结点。
Function：ChooseLeaf
描述：选择叶子结点以放置新条目E。
CL1：[Initialize] 设置N为根结点。
CL2：[叶子结点的检查] 如果N为叶子结点，则直接返回N。
CL3：[选择子树] 如果N不是叶子结点，则遍历N中的结点，找出添加E.I时扩张最小的结点，并把该结点定义为F。如果有多个这样的结点，那么选择面积最小的结点。
CL4：[下降至叶子结点] 将N设为F，从CL2开始重复操作。
Function：AdjustTree
描述：叶子结点的改变向上传递至根结点以改变各个矩阵。在传递变换的过程中可能会产生结点的分裂。
AT1：[初始化] 将N设为L。
AT2：[检验是否完成] 如果N为根结点，则停止操作。
AT3：[调整父结点条目的最小边界矩形] 设P为N的父节点，EN为指向在父节点P中指向N的条目。调整EN.I以保证所有在N中的矩形都被恰好包围。
AT4：[向上传递结点分裂] 如果N有一个刚刚被分裂产生的结点NN，则创建一个指向NN的条目ENN。如果P有空间来存放ENN，则将ENN添加到P中。如果没有，则对P进行SplitNode操作以得到P和PP。
AT5：[升高至下一级] 如果N等于L且发生了分裂，则把NN置为PP。从AT2开始重复操作。
同样，我们用图来更加直观的理解这个插入操作。 
我们来通过图分析一下插入操作。现在我们需要插入R21这个矩形。开始时我们进行ChooseLeaf操作。在根结点中有两个条目，分别为R1，R2。其实R1已经完全覆盖了R21，而若向R2中添加R21，则会使R2.I增大很多。显然我们选择R1插入。然后进行下一级的操作。相比于R4，向R3中添加R21会更合适，因为R3覆盖R21所需增大的面积相对较小。这样就在B8，B9，B10所在的叶子结点中插入R21。由于叶子结点没有足够空间，则要进行分裂操作。
插入操作如下图所示：
这个插入操作其实类似于第一节中B树的插入操作，这里不再具体介绍，不过想必看过上面的伪代码大家应该也清楚了。
删除
R树的删除操作与B树的删除操作会有所不同，不过同B树一样，会涉及到压缩等操作。相信读者看完以下的伪代码之后会有所体会。R树的删除同样是比较复杂的，需要用到一些辅助函数来完成整个操作。
伪代码如下：
Function：Delete
描述：将一条记录E从指定的R树中删除。
D1：[找到含有记录的叶子结点] 使用FindLeaf方法找到包含有记录E的叶子结点L。如果搜索失败，则直接终止。
D2：[删除记录] 将E从L中删除。
D3：[传递记录] 对L使用CondenseTree操作
D4：[缩减树] 当经过以上调整后，如果根结点只包含有一个孩子结点，则将这个唯一的孩子结点设为根结点。
Function：FindLeaf
描述：根结点为T，期望找到包含有记录E的叶子结点。
FL1：[搜索子树] 如果T不是叶子结点，则检查每一条T中的条目F，找出与E所对应的矩形相重合的F（不必完全覆盖）。对于所有满足条件的F，对其指向的孩子结点进行FindLeaf操作，直到寻找到E或者所有条目均以被检查过。
FL2：[搜索叶子结点以找到记录] 如果T是叶子结点，那么检查每一个条目是否有E存在，如果有则返回T。
Function：CondenseTree
描述：L为包含有被删除条目的叶子结点。如果L的条目数过少（小于要求的最小值m），则必须将该叶子结点L从树中删除。经过这一删除操作，L中的剩余条目必须重新插入树中。此操作将一直重复直至到达根结点。同样，调整在此修改树的过程所经过的路径上的所有结点对应的矩形大小。
CT1：[初始化] 令N为L。初始化一个用于存储被删除结点包含的条目的链表Q。
CT2：[找到父条目] 如果N为根结点，那么直接跳转至CT6。否则令P为N 的父结点，令EN为P结点中存储的指向N的条目。
CT3：[删除下溢结点] 如果N含有条目数少于m，则从P中删除EN，并把结点N中的条目添加入链表Q中。
CT4：[调整覆盖矩形] 如果N没有被删除，则调整EN.I使得其对应矩形能够恰好覆盖N中的所有条目所对应的矩形。
CT5：[向上一层结点进行操作] 令N等于P，从CT2开始重复操作。
CT6：[重新插入孤立的条目] 所有在Q中的结点中的条目需要被重新插入。原来属于叶子结点的条目可以使用Insert操作进行重新插入，而那些属于非叶子结点的条目必须插入删除之前所在层的结点，以确保它们所指向的子树还处于相同的层。
R树删除记录过程中的CondenseTree操作是不同于B树的。我们知道，B树删除过程中，如果出现结点的记录数少于半满（即下溢）的情况，则直接把这些记录与其他叶子的记录“融合”，也就是说两个相邻结点合并。然而R树却是直接重新插入。
同样，我们用图直观的说明这个操作。
假设结点最大条目数为4，最小条目数为2。在这张图中，我们的目标是删除记录c。首先使用FindLeaf操作找到c所处在的叶子结点的位置——R11。当c从R11删除时，R11就只有一条记录了，少于最小条目数2，出现下溢，此时要调用CondenseTree操作。这样，c被删除，R11剩余的条目——指向记录d的指针——被插入链表Q。然后向更高一层的结点进行此操作。这样R12会被插入链表中。原理是一样的，在这里就不再赘述。
有一点需要解释的是，我们发现这个删除操作向上传递之后，根结点的条目R1也被插入了Q中，这样根结点只剩下了R2。别着急，重新插入操作会有效的解决这个问题。我们插入R3，R12，d至它原来所处的层。这样，我们发现根结点只有一个条目了，此时根据Inert中的操作，我们把这个根结点删除，它的孩子结点，即R5，R6，R7，R3所在的结点被置为根结点。至此，删除操作结束。
1.R-Tree简介
Btree以及它的变体B+tree对数据库的发展可谓是功不可没,但是，Btree良好的性能却仅仅只能在一维数据上产生效果，如果涉及到二维数据甚至多维数据，那么Btree也无能为力了。然而随着GIS（地理信息系统）和CAD（计算机辅助设计）的广泛应用，多维空间数据(spatial data)的处理变得相当普遍，因此必须在二维和多维数据上找到一种有效的索引方法，于是Rtree就出现了.
1984年，加州大学伯克利分校的Guttman发表了一篇题为“R-trees: a dynamic index structure for spatial searching”的论文，向世人介绍了R树这种处理高维空间存储问题的数据结构。
简单的说，就是将空间对象按某种空间关系进行划分，以后对空间对象的存取都基于划分块进行。
2.R-Tree原理
R树是一种多级平衡树,它是B树在多维空间上的扩展。在R树中存放的数据并不是原始数据，而是这些数据的最小边界矩形（Minimal-Bounding-Box, MBR），空间对象的MBR被包含于R树的叶结点中。从叶子结点开始用矩形（rectangle）将空间框起来，父节点的矩形需要包含字节点的矩形,结点越往上框住的空间就越大，以此对空间进行分割。
R-Tee满足以下属性:
每个叶子节点包含m到M个索引记录,除非它是根节点;
每个叶子节点的索引记录(I, tuple-identifier),I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形(高维空间矩形).
每个非叶子节点包含m到M个子节点,除非它是根节点;
对于在非叶子结点上的每一个条目(Entry),I是最小的可以在空间中完全包含所有子节点矩形的最小矩形;
根节点至少有两个孩子节点,除非它是叶子节点;
所有的叶子节点在同一层;
需要保证,m <= M/2;
叶子节点:
叶子结点所保存的数据形式为：(I, tuple-identifier),其中，tuple-identifier表示的是一个存放于数据库中的tuple，也就是一条记录，它是n维的。I是一个n维空间的矩形，它可以恰好框住这个叶子结点中所有记录代表的n维空间中的点。
非叶子节点
叶子结点所保存的数据形式为：(I, child-pointer),其中child-pointer是子节点指针,I是可以覆盖所有子节点的最小n维空间的矩形;
3.R-Tree应用
典型的PostGis,这使得Postgresql支持空间索引.
空间索引是对存储在介质上的数据位置信息的描述，用来提高系统对数据获取的效率。GIS涉及的各种海量复杂数据存储于外存，如果对磁盘上的数据的位置不加以记录和组织，每查询一个数据项都要扫描整个数据文件，则这种访问磁盘的代价将严重影响系统的效率。因此索引的建立与处理至关重要。此外GIS所表现的地理数据多维性使得传统的B树索引不再适合，因为B树所针对的字符、数字等传统数据类型是在一个良序集之中，即都是在一个维度上，集合中任给两个元素，都可以在这个维度上确定其关系只可能是大于、小于、等于三种，若对多个字段进行索引，必须指定各个字段的优先级形成一个组合字段，而地理数据的多维性，在任何方向上并不存在优先级问题，因此B树并不能对地理数据进行有效的索引，所以需要研究特殊的能适应多维特性的空间索引方式。
1984年Guttman发表了《R树:一种空间查询的动态索引结构》[1]一种高度平衡树，由中间节点和叶节点组成，实际数据对象的最小外接矩形存储在叶节点中，中间节点通过聚集其低层节点的外接矩形形成，包含所有这些外接矩形。其后，人们在此基础上针对不同空间运算提出了不同改进，才形成了一个繁荣的索引树族，是目前流行的空间索引。
R树是一种采用对象界定技术的高度平衡树,是B 树在 k 维空间上的自然扩展，它将空间对象按范围划分，每个结点都对应一个区域和一个磁盘页，非叶结点的磁盘页中存储其所有子结点的区域范围，非叶结点的所有子结点的区域都落在它的区域范围之内；叶结点的磁盘页中存储其区域范围之内的所有空间对象的外接矩形。每个结点所能拥有的子结点数目有上、下限，下限保证对磁盘空间的有效利用，上限保证每个结点对应一个磁盘页，当插入新的结点导致某结点要求的空间大于一个磁盘页时，该结点一分为二。R树是一种动态索引结构，即：它的查询可与插入或删除同时进行，而且不需要定期地对树结构进行重新组织。
R-Tree数据结构
（1）R-Tree是n叉树，n称为R-Tree的扇（fan）。
（2）每个结点对应一个矩形。
（3）叶子结点上包含了小于等于n的对象，其对应的矩为所有对象的外包矩形。
（4）非叶结点的矩形为所有子结点矩形的外包矩形。
R-tree具有以下性质：
（1）除根节点外，每个节点的项数介于最小项数m和最大项数M之间；
（2）根节点至少有两个孩子，除非它是叶子节点；
（3）所有叶子节点位于同一层；
（4）同一节点中项，其排列没有顺序要求
R-Tree的的评价标准为：
（1）位置上相邻的结点尽量在树中聚集为一个父结点。
（2）同一层中各兄弟结点相交部分比例尽量小。
R树是一种用于处理多维数据的数据结构，用来访问二维或者更高维区域对象组成的空间数据.R树是一棵平衡树。树上有两类结点：叶子结点和非叶子结点。每一个结点由若干个索引项构成。对于叶子结点，索引项形如(Index，Obj_ID)。其中，Index表示包围空间数据对象的最小外接矩形MBR，Obj_ID标识一个空间数据对象。对于一个非叶子结点，它的索引项形如(Index，Child_Pointer)。 Child_Pointer指向该结点的子结点。Index仍指一个矩形区域，该矩形区域包围了子结点上所有索引项MBR的最小矩形区域。一棵R树的如图1所示。
R-Tree算法描述
（I）插入算法
基本思想：找到合适的叶子节点，插入之，若需分裂，则由下至上调整MBR值。算法如下：
I1: 调用ChooseLeaf来选择一个合适的叶子节点L以容纳需插入项E
I2: 若L中还能容纳E，则加入之；否则调用SplitNode来获取两个节点L和LL，它们包含E和L中原有的所有项
I3: 调用AdjustTree,传递参数L,LL(若产生了分裂)
I4: 若节点分裂向上传播导致根节点的分裂，则生成新的根节点。
算法ChooseLeaf: 选择一个合适的叶子节点以放置新项E。合适的评价标准是插入E后的节点MBR面积增加度最少。
C1: 设N指向根结点root
C2: 若N是叶子节点，返回N
C3: 若N不是叶子节点，让F表示N中的一项，该项F容纳E后，则N在面积上只需作面积最小扩展
C4: 设N指向叶子节点，则返回C2.
算法AdjustTree: 从叶子节点向根节点进行调整
A1: 设N=L,若L进行了分裂，则设NN=LL
A2: 若N为根节点，则返回
A3: 设P为N的双亲节点，EN为节点P中指向N的项，调整项EN的MBR
A4: 若NN存在，创建一个新项ENN,使其指向NN，同时计算出ENN的MBR.将ENN加入P，若不能容纳则调用SplitNode产生节点P和PP,包含ENN和原来P中所有项
A5: 设N=P, NN=PP, 转至A2.
算法SplitNode: 将M+1项分成两组，将它们加入到两个新节点。
判断节点分裂好坏的一个标准为：分裂后，两个新节点对应的MBR的面积之和最小。下图展示了节点分裂的一个例子。
一个时间复杂度为二次（Quadratic）的分裂算法如下：
S1： 调用PickSeeds选出两项，将它们分别作为两组的第一个元素；
S2： 若所有项都已分配完，则返回；若一组中的项如此之少，以至于将剩下的所有项添至其中才能满足项数达到m的要求，则进行分配且返回；
S3： 调用PickNext选择下一项，将其分配到某组中，该组在容纳该项后，MBR只需作最小面积扩展，转至S2.
算法PickSeeds：
PS1： 对每一项E1和E2，计算d=area(E1和E2合并之后的MBR) – area(E1) – area(E2)；
PS2：选择d值最大的一对项。
算法PickNext：
PN1：对每一项E，计算d1=<将E加入组1后MBR增加的面积>，同理计算d2；
PN2：选出d1和d2值差距最大的项。
（2）R-tree删除算法
算法Delete（Entry E)：从R-tree中删除项E
D1：调用FindLeaf来寻找存放E的叶子结点L ;若没有找到则停止；
D2：从L中删去E；
D3：调用CondenseTree，传递参数L :
D4：:若根结点只有一个孩子，则让该孩子结点成为新根节点。
算法FindLeaf (NODE T, Entry E )
FL1：若T不是叶子结点，则对于T中每一个与E相重叠的项，将该项所指的结点作参数，递归调用FindLeaf
FL2：若T是叶子结点，则检查T中是否有与E相等的项，若有，则返回T
算法CondenseTree ：传递参数结点L ，该结点进行了删除项的操作
CT1：设N=L ，将存储被删结点的集合Q置为空；
CT2：若N是根，转至CT6；否则，设P为N的父节点，EN为P中指向N的项；
CT3：若N中的项数小于m，在P中删除EN，并把N加入到集合Q中；
CT4：若N没有被删除，调整EN的MBR；
CT5：设N=P,转向CT2；
CT6：重新插入集合Q中所有节点中的所有项，对于叶子节点中的项仍插入到叶子节点
中，但对于中间节点的项需要插入到其原来所在的那一层。
R树主要变体
R树最初由Guttman于1984年提出，其后，人们在此基础上针对不同的空间操作需求提出了各种改进方案。经过二十多年的发展，不断产生的R树变体逐渐形成了一个枝繁叶茂的空间索引R树家族。
1 R+树[2]
在Guttman的工作的基础上，许多R树的变种被开发出来， Sellis等提出了R+树[10]，R+树与R树类似，主要区别在于R+树中兄弟结点对应的空间区域无重叠，这样划分空间消除了R树因允许结点间的重叠而产生的“死区域”（一个结点内不含本结点数据的空白区域），减少了无效查询数，从而大大提高空间索引的效率，但对于插入、删除空间对象的操作，则由于操作要保证空间区域无重叠而效率降低。同时R+树对跨区域的空间物体的数据的存储是有冗余的，而且随着数据库中数据的增多，冗余信息会不断增长。
2 R*树[3]
在1990年，Beckman和Kriegel提出了最佳动态R树的变种——R树[11]。R树和R树一样允许矩形的重叠，但在构造算法R树不仅考虑了索引空间的“面积”，而且还考虑了索引空间的重叠。该方法对结点的插入、分裂算法进行了改进，并采用“强制重新插入”的方法使树的结构得到优化。但R树算法仍然不能有效地降低空间的重叠程度，尤其是在数据量较大、空间维数增加时表现的更为明显。R*树无法处理维数高于20的情况。
3 QR树
QR树利用四叉树将空间划分成一些子空间，在各子空间内使用许多R树索引，从而改良索引空间的重叠。QR树结合了四叉树与R树的优势，是二者的综合应用。实验证明：与R树相比，QR树以略大（有时甚至略小）的空间开销代价，换取了更高的性能，且索引目标数越多，QR树的整体性能越好。
4 SS树
SS树对R树进行了改进，通过以下措施提高了最邻近查询的性能：用最小边界圆代替最小边界矩形表示区域的形状，增强了最邻近查询的性能，减少将近一半存储空间；SS树改进了R树的强制重插机制。当维数增加到5是，R树及其变种中的边界矩形的重叠将达到90％，因此在高维情况（≧5）下，其性能将变的很差，甚至不如顺序扫描。
5 X树
X树是线性数组和层状的R树的杂合体，通过引入超级结点，大大地减少了最小边界矩形之间的重叠，提高了查询效率。X树用边界圆进行索引，边界矩形的直径（对角线）比边界圆大，SS树将点分到小直径区域。由于区域的直径对最邻近查询性能的影响较大，因此SS树的最邻近查询性能优于R树；边界矩形的平均容积比边界圆小，R树将点分到小容积区域；由于大的容积会产生较多的覆盖，因此边界矩形在容积方面要优于边界圆。SR树既采用了最小边界圆（MBS），也采用了最小边界矩形（MBR），相对于SS树，减小了区域的面积，提高了区域之间的分离性，相对于R*树，提高了邻近查询的性能。
在二维的情况下，我们称之为最小限定矩形。MBR(minimum bounding retangle)
三维的情况下，我们称最新限定箱MBB(minimum bounding box)
R树
对于B/B+-Trees 由于它的线性特点，通常用来索引一维数据。（比它大的往一边走，比它小的往一边走，但只是在一个维度下进行比较）。
B树是一棵平衡树，它是把一维直线分为若干段线段，当我们查找满足某个要求的点的时候，只要去查找它所属的线段即可。这种思想其实就是先找一个大的空间，再逐步缩小所要查找的空间，最终在一个自己设定的最小不可分空间内找出满足要求的解。一个典型的B树查找如下：
要查找某一满足条件的点，先去找到满足条件的线段，然后遍历所在线段上的点，即可找到答案。B树是一种相对来说比较复杂的数据结构，尤其是在它的删除与插入操作过程中，因为它涉及到了叶子结点的分解与合并。
简介
B树是解决低纬度数据（通常一维，也就是一个数据维度上进行比较），R树很好的解决了这种高维空间搜索问题。它把B树的思想很好的扩展到了多维空间，采用了B树分割空间的思想（如果B树在一维的线段进行分割，R树就是在二维甚至多维度的空间），并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，R树就是一棵用来存储高维数据的平衡树。
我们说过，B树是采用切分线段来缩小数据查询范围的一种思想，我们又说了，R树是b树的多维版，以及R树也采用了B树的这一种分割的思想，那么，如果说线段的分割是一维的分割。那二维的分割就应该是区域的分割，而三维的就是几何空间的分割了。要注意的是R树并不只是二维空间数据的索引而已，它还可以索引三维甚至更高维。
一个三维的R树
此外R树还可以退化成一维，但是分割的线段存在重叠问题，效果不如Btree。
R树的数据结构
如上所述，R树是B树在高维空间的扩展，是一棵平衡树。每个R树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。
根据R树的这种数据结构，当我们需要进行一个高维空间查询时，我们只需要遍历少数几个叶子结点所包含的指针（即缩小到某个区域下去进行查询，还是采用缩小范围的思想），查看这些指针指向的数据是否满足要求即可。这种方式使我们不必遍历所有数据即可获得答案，效率显著提高。
