R+树

✍ dations ◷ 2025-05-19 06:40:38 #R树,数据库索引技术

R+树可以用地址来查询数据。地址用坐标来表示,一般是(x, y)轴坐标,常用于地理坐标。单个地址查询问题早已被解决,而多地址查询,或者查询在坐标系上的附近地址则需要更巧妙的算法。

R+树本质上来说是树结构,是R树的一个变体,也被用来检索空间信息。

R+树是R树和k-d树这两种空间检索方式的折中办法。为了避免子节点重叠,R+树允许把同一个对象插入到多个叶子节点中。当对象跟多个子节点相交时,将其切割成多份,使每一份只跟一个子节点相交。根据具体情况,可以让每个分割持有完整或部分数据,或者把对象存储在其它地方,每个分割持有一个指向存储位置的标识符。定义覆盖范围为树上所有外接矩形覆盖的区域,重叠范围为所有存在至少两个外界矩形的区域。让覆盖范围尽量小可以减少R树上节点涵盖的“无效区”,也就是不存在对象的区域。让重叠范围尽量小可以减少搜索路径。就减少访问时间而言,最小化重叠范围比最小化覆盖范围更关键。为了提高搜索性能,要让覆盖范围和重叠范围都尽量小。

R+树和R树的区别在于:R+树的节点并不保证至少填充一半,节点互不相交,并且指向同一个对象的标识符可能会存在于多个叶子节点中。

因为节点互不相交,所以在搜索时最多只会有一个子树(子节点)覆盖一个点,因此R+树的点搜索操作性能极佳。在搜索一个点时,算法只需要沿着一条路径一直往下访问就可以了,这要比R树的访问量少很多。

因为一个对象的外接矩形可能会被分割成多份分别插入不同的节点,所以使用同样的数据集,R+树可能比R树需要更多空间。创建和维护R+树也比R树和其它R树的变体更加复杂。


相关

  • 丹尼尔·伯努利丹尼尔·伯努利(Daniel Bernoulli,1700年2月8日-1782年3月17日),生于荷兰格罗宁根,著名数学家,约翰·伯努利之子,为伯努利家族代表人物之一。其伯努利定律适用于沿着一条流线的稳定
  • 放大器放大器(英语:Amplifier),俗称音箱,一般而言是指能够使用较小的能量来控制较大能量的任何器件。现在,在日常使用中,这个名词常常是指放大器电路,经常用于音频应用中。一个放大器的输
  • 玻璃棉玻璃棉属于一种玻璃纤维。玻璃棉是将熔融玻璃纤维化,形成纤维状的材料,化学成分属玻璃类,是一种无机质纤维,具有体积密度小、保温绝热、吸音性能好、耐腐蚀、化学性能稳定。采用
  • 高仰云高仰云,陕西米脂人。1924年考入陕北联合县立榆林中学,1927年5月加入中国共产党。1958年调任南开大学党委书记兼副校长,文化大革命期间遭受批斗迫害,1968年7月27日于天津大学投湖
  • 缩微文字微缩印刷,又称微小字,是一种在纸币、银行支票以及其他有价印刷品和证件上广泛使用的防伪技术。在纸币或者其他一些印刷品上的不起眼的地方,通常都会使用缩微印刷技术——一些文
  • 清齿无咝塞擦音清齿无咝塞擦音是一种辅音,使用于一些口语中。国际音标写作⟨t͡θ⟩、⟨t͜θ⟩、⟨t̪͡θ⟩或⟨t̟͡θ⟩。清齿无咝塞擦音的特征包括:当符号成对出现时,左边的是清音,右边的
  • 我们结婚吧《我们结婚吧》(英文:Merry Me)是一部台湾偶像剧,由贺军翔、刘喆莹 、周采诗、锺欣愉主演,2006年7月19日起于华视首播。《爱情合约》电视原声带于2006年8月发行。原声带中收录了
  • 2017年阿斯塔纳世界博览会2017年世界博览会于2017年6月10日至9月10日在哈萨克阿斯塔纳举行。本届世博会的主题为“未来能源”,旨在建立国家、非政府组织,企业和公众之间的全球性讨论,探讨“我们如何确保
  • 汉泽尔汉泽尔(Ľuboš Hanzel),(出生于1987年5月7日)是斯洛伐克的职业足球运动员,司职左后卫,现效力于亚美尼亚足球超级联赛班兰特斯。2009年6月6日汉泽尔首次代表斯洛伐克国家足球队在
  • 苏联特别用途机动单位袭击立陶宛边境检察站事件 立陶宛 苏联数起苏联特别用途机动单位袭击立陶宛边境检察站事件 (立陶宛语:1990–1991 m. Lietuvos pasienio kontrolės punktų puolimai)发生于1990年3月11日立陶宛宣