R+树

✍ dations ◷ 2025-06-08 12:42:35 #R树,数据库索引技术

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

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

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

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

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

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


相关

  • VIIAbr /17固体、 液体、 气体卤素是指在元素周期表中同属第17族(旧称ⅦA族)的六个元素:氟(F)、氯(Cl)、溴(Br)、碘(I)、砹(At)、(Ts),其中砹和具有极高的放射性,且属于人造元素。卤素是一类化学性质非
  • 德累斯顿圣母教堂德累斯顿圣母教堂(Dresdner Frauenkirche)是德国萨克森州首府德累斯顿的一座路德会教堂。该处原址早期的教堂建筑是罗马天主教教堂,直到宗教改革期间被改为新教徒教堂,并在18世
  • ACTH促肾上腺皮质激素(英语:adrenocorticotropic hormone, ACTH)——或简称促皮质素(corticotropin)——是一种多肽激素,生产并分泌于脑垂体,是下丘脑-脑垂体-肾上腺皮质轴(hypothalamic
  • 1996年1996年被中华人民共和国处决的死刑犯列表,旨在列出1996年被中华人民共和国处决的死刑犯。
  • 怀氏副盲鳗怀氏副盲鳗(学名:Paramyxine wisneri),又名青眠鳗、无目鳗、鳗背、龙筋,为盲鳗科副盲鳗属下的一个种。
  • 交换交换:
  • α-胎儿蛋白n/an/an/an/an/an/an/an/an/an/aα-胎儿蛋白(英语:Alpha-Fetoprotein,缩写AFP;又译甲种胎儿球蛋白或甲胎蛋白)是一种α-1球蛋白,由胎儿肠胃道、卵黄囊及肝脏分泌,但可经由肾脏排入
  • 莎草香附(学名:Cyperus rotundus),别名莎草、大香附、香头草、土香草、土香(台湾和闽南一带)、水香棱、地藾草,为莎草科的多年生草本植物,茎直立,三棱形,高40厘米;叶近基生出,细长,呈线形,略比
  • 劳埃德·本特森小劳埃德·米拉德·本特森(英语:Lloyd Millard Bentsen, Jr.,1921年2月11日-2006年5月23日),美国政治人物,民主党人,在1971年至1993年间曾担任四届德州美国参议员。在1949年至1955年
  • 二次互反律的证明这个条目给出了二次互反律的证明。对于两个奇素数 p , q {\displaystyle p,q} , (