R+树

✍ dations ◷ 2025-04-04 05:12:29 #R树,数据库索引技术

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

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

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

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

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

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


相关

  • 媒介语所谓媒介语,是指为了机器翻译的需要,人工所创造出来的一种提供在不同语言之间交流用的算法。对媒介语的要求,是国际交流频繁的情况下,机器翻译向多语种发展的一种需求。例如,没有
  • 人口减少人口不足(又称人口稀少或人口过稀),通常是指一个国家的人口减少至无法支持该国的社会经济。举例来说,假如现时已退休的上一辈当年的每个家庭平均有三个小孩,而现时的新一代则平均
  • 蛮蚁亚科蛮蚁亚科(Agroecomyrmecinae)隶属蚁科,下辖2个现生的属及2个已灭绝的属。该亚科起初是由 Carpenter 在1930年以家蚁亚科蛮蚁族发表。Barry Bolton 于2003年将其提升至亚科,并提
  • 客体关系理论客体关系理论是一种精神分析理论,于1940至1950年代由英国心理学家罗纳德·费尔贝恩和梅兰妮·克莱因等人所开拓。不同于弗洛伊德理论,客体关系理论认为人并非寻求“驱力”的满
  • 被认定是伪科学的主题列表被认定是伪科学的主题列表(List of topics characterized as pseudoscience)表列出在自身发展过程中曾被学者或研究者认定为伪科学的主题。有关这类主题的具体讨论都在其对应
  • 长滩寺河长滩寺河,原名盐滩溪、岳池水、灵溪水,是嘉陵江的一条支流。此河发源于四川省南充市东北部金城山南坡东林寺,因流经岳池县城南长滩寺,故名长滩寺河。至岳池县朝阳乡西北接纳余家
  • 奥吉拉语奥吉拉语或奥季拉语,在利比亚昔兰尼加地区的奥吉拉绿洲使用的一种语言,属于柏柏尔语族。联合国教科文组织将其列为严重濒危语言,由于该语言最年轻的使用者们已经都是人到中年或
  • 阿兰-勒内·勒萨日阿兰-勒内·勒萨日(法语:Alain-René Lesage,法语发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","
  • BLK BLK(朝鲜语:비엘케이)为“Beyond Limit Key”的简称,韩国J&B娱乐在2017年11月28日推出的韩国男子音乐团体,由D.A(队长)、Tae Bin、So Rim、Il Kyoung、INNO、I六位成员组成。后
  • 温家宝被扔鞋事件温家宝被扔鞋事件是2009年2月2日时任中国国务院总理温家宝在英国伦敦剑桥大学被该校德国籍男研究生马丁·杨克扔鞋的事件。当时温家宝正在“瑞德讲坛”发表题为“用发展的眼