R+树
R+树（英語：R+ tree）可以用地址来查询数据。地址用坐标来表示，一般是(x, y)轴坐标，常用于地理坐标。单个地址查询问题早已被解决，而多地址查询，或者查询在坐标系上的附近地址则需要更巧妙的算法。
R+树本质上来说是树结构，是R树的一个变体，也被用来检索空间信息。
R+树和R树的区别[编辑]
R+树是R树和k-d树这两种空间检索方式的折中办法。为了避免子节点重叠，R+树允许把同一个对象插入到多个叶子节点中。当对象跟多个子节点相交时，将其切割成多份，使每一份只跟一个子节点相交。根据具体情况，可以让每个分割持有完整或部分数据，或者把对象存储在其它地方，每个分割持有一个指向存储位置的标识符。定义覆盖范围为树上所有外接矩形覆盖的区域，重叠范围为所有存在至少两个外界矩形的区域[1]。让覆盖范围尽量小可以减少R树上节点涵盖的“无效区”，也就是不存在对象的区域。让重叠范围尽量小可以减少搜索路径。就减少访问时间而言，最小化重叠范围比最小化覆盖范围更关键。为了提高搜索性能，要让覆盖范围和重叠范围都尽量小。
R+树和R树的区别在于：R+树的节点并不保证至少填充一半，节点互不相交，并且指向同一个对象的标识符可能会存在于多个叶子节点中。
优势[编辑]
因为节点互不相交，所以在搜索时最多只会有一个子树（子节点）覆盖一个点，因此R+树的点搜索操作性能极佳。在搜索一个点时，算法只需要沿着一条路径一直往下访问就可以了，这要比R树的访问量少很多。
劣势[编辑]
因为一个对象的外接矩形可能会被分割成多份分别插入不同的节点，所以使用同样的数据集，R+树可能比R树需要更多空间。创建和维护R+树也比R树和其它R树的变体更加复杂。
注释[编辑]
- ^ Härder, Rahm, Theo, Erhard. Datenbanksysteme. 2., überarb. Aufl. Berlin [etc.]: Gardners Books. 2007: 285, 286. ISBN 3-540-42133-5.
参考资料[编辑]
- T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-Tree: A dynamic index for multi-dimensional objects（页面存档备份，存于互联网档案馆）. In VLDB, 1987.
| |||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||
|
这个算法或数据结构相关的文章是个小作品，你可以帮助维基扩充它的内容。 |