二、R树
R树可以看作B树在高维空间上的扩展，类似于B树索引，R树索引同样可以用于组织数据，加速数据访问。它专门用于包含了多维数据和空间数据类型的表，很好地解决了高维空间上的搜索问题。
在GBase 8s数据库中采用了这种R树索引结构，主要用于为以下几种数据类型创建索引：
1、包含了多个维度的空间数据，如(X,Y)地理坐标系；
2、额外增加了时间维度的数据；
3、区间值，例如时间段数据（9:00P.M~9:30P.M）；
4、多个数值类型的组合，也可以看作多维数据值。
假设我们需要查找距离当前所在位置两公里之内的博物馆。在一般情况下，数据库会使用两个字段(X,Y)来存放博物馆的地理位置信息，我们需要遍历所有的博物馆，获取其地理位置来计算距离，从而得到满足要求的全部博物馆。在没有索引的情况下，需要遍历表中的全部数据行来进行计算。如果我们在这个高维空间数据上创建R树索引，则能大幅提高搜索性能。
它的思想类似于B树，在B树种是根据数值的大小对数据进行分割的，将分块的数据组织成树的形式进行存储，而R树则是对空间数据进行分割的，将B树的方法有效地扩展到了高维空间上。
R树是一棵存储高维数据的多叉平衡树，在每个节点中存储了多个矩形区域，每个区域I对应一个指针。叶子节点中的矩形区域I为数据对象的外包矩形，且指针指向区域I内包含的实际数据行数据。非叶子节点（根节点和分支节点）中的矩形区域I为所有孩子节点矩形区域的外包矩形，且指针指向位于下一层的孩子节点，所以孩子节点中的所有区域都在区域I的范围之内。
如图是一个使用R树进行二维矩形索引的例子，数据可以看作二维空间上的点。为了实现R树索引，我们用一个最小边界矩形紧紧围绕住空间对象，R8就是这样的一个矩形区域，在R8中包含一个或多个空间数据对象，对所有的数据进行划分，一共使用了12个最小矩形（R8-R19）来包围所有数据，它们被存储在R树的叶子节点中，每个区域都有一个指向区域内所包含数据对象的指针。接下来对这些最小矩形区域进行合并，存储到R树的上一层节点中。我们发现R8，R8和R10三个区域距离最近，将它们合并到一个更大的矩形区域R3中，同理，这棵R树分支节点中的5个区域（R3~R7）都包含了叶子节点中的几个最小矩形，且每个区域都有指向下一层节点的指针，用于记录该区域包含的几个小矩形。重复迭代这个过程，知道所有数据都存放到了根节点中几大最大区域（R1和R2）为止。
与B树类似，一棵R树需要满足如下性质：
1、根节点至少有两个孩子节点，除非它是叶子节点；
2、除根节点外，每个节点（分支节点和叶子节点）所包含的实体（矩形区域）个数都介于最小项数m和最大项数M之间，通常m=M/2；
3、所有叶子节点都处于同一层
4、在一个节点中，每个实体的排列没有顺序要求。
值得注意的是，这里我们所说的二维空间上的矩形区域可以扩展到高维空间中。
R树兄弟节点对应的空间区域可以重叠，这可以比较容易地进行插入和删除操作，但搜索时可能要对多条路径进行查找才能得到最终结果，因此重叠区域的大小对搜索效率有着较大影响。R+树就是对这一点进行改进，兄弟节点对应的空间区域没有重叠。
R树索引是一种动态索引。也就是说，当数据表发生了修改、插入和删除操作时，R树索引也会相应地维护自身的数据。另外，在创建R树索引前，我们不必知道索引列中的数据个数或范围等信息，可以方便地创建R树索引。
