R树

R树
类型
发明时间1984
发明者Antonin Guttman
大O符号时间复杂度
算法平均最差
搜索O(logMn)
一个简单的二维矩形上的R树的例子
用ELKI做出的三维R*树视觉效果图(每个立方体是一个目录页)

R树是用来做空间数据存储的树状数据结构。例如给地理位置矩形多边形这类多维数据建立索引。R树是由Antonin Guttman于1984年提出的[1]。人们随后发现它在理论和应用方面都非常实用[2]。 在现实生活中,R树可以用来存储地图上的空间信息,例如餐馆地址,或者地图上用来构造街道,建筑,湖泊边缘和海岸线的多边形。然后可以用它来回答“查找距离我2千米以内的博物馆”,“检索距离我2千米以内的所有路段”(然后显示在导航系统中)或者“查找(直线距离)最近的加油站”这类问题。R树还可以用来加速使用包括大圆距离[3]在内的各种距离度量方式的最邻近搜索[4]

其他语言
čeština: R-strom
Deutsch: R-Baum
English: R-tree
español: Árbol-R
עברית: עץ R
hrvatski: R-stablo
italiano: R-tree
日本語: R木
한국어: R 트리
polski: R-drzewo
português: Árvores R
српски / srpski: Р-стабло
українська: R-дерево