R 树(R-Tree)

定义

R 树(R-Tree)是一种平衡的空间索引结构,由 Antonin Guttman 于 1984 年提出,用于索引矩形、点、多边形等多维空间对象,是 B 树思想向多维空间的推广,"R"代表 Rectangle。

原理

R 树的每个节点存放若干条目,每个条目用最小外接矩形(MBR,Minimum Bounding Rectangle)概括其子树中所有对象的空间范围。查询时从根节点出发,只需进入 MBR 与查询区域相交的子树,从而剪掉大量无关分支。与 B 树不同,兄弟节点的 MBR 允许重叠,重叠越多查询需要探查的路径越多,因此插入与分裂算法(如二次分裂、R* 树的强制重插)都在尽量减小重叠与面积。

变体

常见变体包括查询性能更优的 R* 树、通过预排序批量构建的 STR 打包 R 树,以及适合静态数据的 R+ 树。

应用

PostGIS、MySQL 空间索引、SQLite 的 R-Tree 模块、Oracle Spatial 等均采用 R 树族结构,支撑"查找附近的点""范围相交"等地理查询。