数据库必知词汇：R-Tree

1984年，加州大学伯克利分校的Guttman发表了一篇题为“R-trees: a dynamic index structure for spatial searching”的论文，向世人介绍了R树这种处理高维空间存储问题的数据结构。R-Tree是B-Tree向多维空间发展的另一种形式，它将对象空间按范围划分，每个结点都对应一个区域和一个磁盘页，非叶结点的磁盘页中存储其所有子结点的区域范围，非叶结点的所有子结点的区域都落在它的区域范围之内；叶结点的磁盘页中存储其区域范围之内的所有空间对象的外接矩形。

R-Tree是一种空间索引数据结构，下面做简要介绍：

（1）R-Tree是n 叉树，n称为R-Tree的扇（fan）。

（2）每个结点对应一个矩形。

（3）叶子结点上包含了小于等于n 的对象，其对应的矩为所有对象的外包矩形。

（4）非叶结点的矩形为所有子结点矩形的外包矩形。

R-Tree的定义很宽泛，同一套数据构造R-Tree，不同方可以得到差别很大的结构。什么样的结构比较优呢？有两标准：

（1）位置上相邻的结点尽量在树中聚集为一个父结点。

（2）同一层中各兄弟结点相交部分比例尽量小。

R树是一种动态索引结构。每个结点所能拥有的子结点数目有上、下限，下限保证对磁盘空间的有效利用，上限保证每个结点对应一个磁盘页，当插入新的结点导致某结点要求的空间大于一个磁盘页时，该结点一分为二(分裂)。R树是一种动态索引结构，即：它的查询可与插入或删除同时进行，而且不需要定期地对树结构进行重新组织。

R-树是一种用于处理多维数据的数据结构，用来访问二维或者更高维区域对象组成的空间数据.R树是一棵平衡树。树上有两类结点：叶子结点和非叶子结点。每一个结点由若干个索引项构成。对于叶子结点，索引项形如(Index，Obj_ID)。其中，Index表示包围空间数据对象的最小外接矩形MBR，Obj_ID标识一个空间数据对象。对于一个非叶子结点，它的索引项形如(Index，Child_Pointer)。 Child_Pointer 指向该结点的子结点。Index仍指一个矩形区域，该矩形区域包围了子结点上所有索引项MBR的最小矩形区域。

R树满足的性质：

1. 除根结点之外，所有非根结点包含有m至M个记录索引（条目）。根结点的记录个数可以少于m。通常，m=M/2。
2. 对于所有叶子中存储的记录（条目），I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（注意：此处所说的“矩形”是可以扩展到高维空间的）。
3. 对于所有非叶子结点上的记录（条目），i是最小的可以在空间上完全覆盖这些条目所代表的点的矩形（同性质2）。
4. 所有叶子结点都位于同一层，因此R树为平衡树。

资料来源：

邓红艳, 武芳, 翟仁健, et al. 一种用于空间数据多尺度表达的R树索引结构[J]. 计算机学报, 2016, 32(01).

肖予钦, 张巨, 景宁, et al. 基于R树的方向关系查询处理[J]. 软件学报, 2004(01):106-114.

雷小锋, 谢昆青, 韩亮, et al. 基于惰性聚类分裂的动态R树实现方法[J]. 计算机科学, 2007, 34(4):102-103.

张明波, 陆锋, 申排伟,等. R树家族的演变和发展[J]. 计算机学报, 2005, 28(3):289-300.