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