R+树

✍ dations ◷ 2025-12-07 02:06:34 #R树,数据库索引技术

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

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

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

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

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

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


相关

  • 布尔函数在数学中,布尔函数(Boolean function)描述如何基于对布尔输入的某种逻辑计算确定布尔值输出。它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在
  • 蛋白质微阵列蛋白质微阵列(英语:Protein microarray,亦称为蛋白质芯片)是将不同的具有生物活性的蛋白质分别置于微量板的不同孔内来进行蛋白质功能筛选的文库。它实质上是cDNA阵列文库的继续
  • 尤金·舒梅克尤金·摩尔·休梅克(英语:Eugene Merle Shoemaker,或别名吉恩·休梅克,英语:Gene Shoemaker,1928年4月28日-1997年7月18日),出生在洛杉矶,美国天文学家,行星科学领域的奠基者。他最有名
  • 磷化钙磷化钙(化学式:Ca3P2)是一种化学燃烧弹或作为灭鼠剂使用。外观呈红棕色结晶粉末或灰色块状,熔点1600℃。磷化钙与酸或水会发生反应,自燃及释放出磷化氢。在潮湿空气中能自燃,与氯
  • 255年
  • 赵陀赵佗(前240年-前137年),恒山郡真定县(今河北省正定县)人,秦朝南海龙川令 ,南越国创建者,是南越国第一代王和皇帝。前204年,赵佗建立南越国。南越国的建立年代,无史籍直接记载,现代的研究
  • 相思树属相思树属(学名:),原名“金合欢属”,最早由瑞典生物学家卡尔·林奈于1773年在非洲描述。而后分子生物学研究发现本属并非单系群,占本属主体的900多种澳大利亚类群和包括模式种阿拉
  • 联合饼干联合饼干(United Biscuits,UB)是一家英国的跨国食品生产商,制造BN Biscuit、McVitie's、Jacob's等数个品牌的饼干。原本该公司在伦敦证券交易所上市,且是富时100指数成份股,但2006
  • 中华音乐人交流协会中华音乐人交流协会成立于1996年5月4日,是一个由台湾音乐工作者成立的民间组织,前身为1993年创立的“音乐人交流协会”,以促进音乐人交流、自我成长,并积极参与各种公益性活动为
  • 四棱果科四棱果科又名缨缘科,只有1属1种,是一个单种科,只生长在南非好望角一带,是当地的特有种。本科植物为旱生植物,小型常绿灌木,单叶对生,革质;花两性,花瓣4数;果实为蒴果,有4棱,包含4个种子