简介

R-tree结构

R-tree性质

R-tree构造标准

简介

R-tree是B-tree向多维空间发展的另一种形式，它将空间对象按范围划分，每个结点都对应一个区域和一个磁盘页，非叶结点的磁盘页中存储其所有子结点的区域范围，非叶结点的 所有子结点的区域都落在它的区域范围之内；叶结点的磁盘页中存储其区域范围之内的所有空间对象的外接矩形。每个结点所能拥有的子结点数目有上、下限，下限 保证对磁盘空间的有效利用，上限保证每个结点对应一个磁盘页，当插入新的结点导致某结点要求的空间大于一个磁盘页时，该结点一分为二(分裂)。R树是一种动态索引结构，即：它的查询可与插入或删除同时进行，而且不需要定期地对树结构进行重新组织。

R-tree结构

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

（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的最小矩形区域。一棵R树的示例如图所示：

R-tree性质

M：结点中单元的最大数目，m(1<= m <= M/2)为非根结点中单元个数的下限。

一个R树满足如下性质:

(1) 每一个叶子结点中包含的单元的个数介于m和M之间，除非他同样是根结点

(2) 每一个叶子结点中的单元(I, tuple-identifier),I为包含所有子结点的最小包含矩形(MBR)

(3) 每一个非叶子结点的子结点数介于m和M之间，除非他是根结点

(4) 每一个非叶子结点单元(I, child -pointer)I是包含子结点的MBR.Pointer是指向子结点的指针。通过该指针可以访问到叶子结点。

(5) 根结点至少有两个子结点，除非他同时是叶子结点

(6) 所有的叶子结点都处在树的同一层上。

R-tree构造标准

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

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

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