GBASE 8s 索引R树

        R 树可以看作 B 树在高维空间上的扩展，类似于 B 树索引，R 树索引同样可以用于组织数据，加速数据访问。它专门用于包含了多维数据和空间数据类型的表，很好地解决了高维空间上的搜索问题。 在 GBase 8s 数据库中采用了这种 R 树索引结构，主要用于为以下几种数据类型创建索引：

1. 包含了多个维度的空间数据，如（X，Y）地理坐标系；
2. 额外增加了时间维度的数据；
3. 区间值，例如时间段数据（9:00 P.M～9:30 P.M）；
4. 多个数值类型的组合，也可以看作多维数据值。

        在一般情况下，数据库会使用两个字段(X，Y)来存放博物馆的地理位置信息，我们需要遍历所有的博物馆，获取其地理位置来计算距离，从而得到满足要求的全部博物馆。在没有索引的情况下，需要遍历表中的全部数据行来进行计算。如果我们在这个高维空间数据上创建R树索引，则能大幅提高搜索性能。它的思想类似于 B 树，在 B 树中是根据数值的大小对数据进行分割的，将分块的数据组织成树的形式进行存储，而 R 树则是对空间数据进行分割的，将B树的方法有效地扩展到了高维空间上。

        R 树是一棵存储高维数据的多叉平衡树，在每个节点中存储了多个矩形区域，每个区域 I 对应一个指针。叶子节点中的矩形区域 I 为数据对象的外包矩形，且指针指向区域I内包含的实际数据行数据。非叶子节点（根节点和分支节点）中的矩形区域I 为所有孩子节点矩形区域的外包矩形，且指针指向位于下一层的孩子节点，所以孩子节点中的所有区域都在区域 I 的范围之内。

 

        为了实现 R 树索引，我们用一个最小边界矩形紧紧围绕住空间对象，R8 就是这样的一个矩形区域，在 R8 中包含了一个或多个空间数据对象，对所有的数据进行划分，一共使用了12 个最小矩形（R8-R19）来包围所有数据，它们被存储在R 树的叶子节点中，每个区域都有一个指向区域内所包含数据对象的指针。接下来对这些最小矩形区域进行合并，存储到 R 树的上一层节点中。我们发现 R8、R9 和 R10 三个区域距离最近，将它们合并到一个更大的矩形区域 R3 中，同理，这棵 R 树分支节点中的 5 个区域（R3～R7）都包含了叶子节点中的几个最小矩形，且每个区域都有指向下一层节点的指针，用于记录该区域包含的几个小矩形。重复迭代这个过程，直到所有数据都存放到了根节点中几个最大区域（R1和 R2）为止。

        与 B 树类似，一棵 R 树需要满足如下性质：

1. 根节点至少有两个孩子节点，除非它是叶子节点；
2. 除根节点外，每个节点（分支节点和叶子节点）所包含的实体（矩形区域）个数都介于最小项数 m 和最大项数 M 之间，通常 m=M/2；
3. 所有叶子节点处于同一层；
4. 在一个节点中，每个实体的排列没有顺序要求。

        这里我们所说的二维空间上的矩形区域可以扩展到高维空间中。

        R 树的搜索、插入和删除操作与 B 树类似，因此可以有效地应用于数据库中。R树兄弟节点对应的空间区域可以重叠，这可以比较容易地进行插入和删除操作，但搜索时可能要对多条路径进行查找才能得到最终结果，因此重叠区域的大小对搜索效率有着较大影响。R+树就是对这一点进行改进，兄弟节点对应的空间区域没有重叠。

        R 树索引是一种动态索引，也就是说，当数据表发生了修改、插入和删除操作时，R树索引也会相应地维护自身的数据。另外，在创建 R 树索引前，我们不必知道索引列中的数据个数或范围等信息，可以方便地构建 R 树索引。