R-tree 空间索引详解：从原理到 Spring Boot 实战

什么是 R-tree？

R-tree（Rectangle Tree）是一种专门用于索引空间数据的数据结构，由 Antonin Guttman 于 1984 年提出。它通过将相邻的空间对象（矩形/多边形）分组到最小外接矩形（MBR, Minimum Bounding Box）中，形成一棵层次树，从而实现高效的范围查询和最近邻搜索。

核心思想：用矩形近似表达空间对象，层层包含，形成树状索引。

1
2
3
4
5


        [Root MBR]
       /    |    \
  [R1 MBR] [R2 MBR] [R3 MBR]
   / \     / \      / \
 M1 M2   M3 M4    M5 M6

R-tree vs 其他空间索引

特性	R-tree	QuadTree	KD-tree	Grid 索引
适用维度	高维/2D/3D	固定维度	低维（<20）	固定维度
查询类型	矩形/多边形范围	递归网格分割	最近邻	网格单元
动态插入	支持	支持	需重建	支持
代表实现	JTS STRtree	Tile38	EJML	PostGIS
GIS 生态	✅ 最成熟	✅	❌	✅

Java 中常用的 R-tree 实现

1. JTS（最推荐）

JTS Topology Suite 是 Java 地理空间领域最成熟的库，提供了 STRtree（R*-tree 变体）实现。

Maven 依赖

1
2
3
4
5


<dependency>
    <groupId>org.locationtech.jts</groupId>
    <artifactId>jts-core</artifactId>
    <version>1.18.2</version>
</dependency>

核心 API

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


import org.locationtech.jts.index.strtree.STRtree;
import org.locationtech.jts.geom.Envelope;

// 1. 创建 STRtree（基于 R*-tree）
STRtree tree = new STRtree();

// 2. 插入空间对象
// Envelope(minX, maxX, minY, maxY)
tree.insert(new Envelope(0.0, 1.0, 0.0, 1.0), "POI-001");
tree.insert(new Envelope(2.0, 3.0, 2.0, 3.0), "POI-002");
tree.insert(new Envelope(0.5, 1.5, 0.5, 1.5), "POI-003");

// 3. 构建索引（插入完毕后调用，显著提升查询性能）
tree.build();

// 4. 范围查询
Envelope queryBox = new Envelope(0.0, 2.0, 0.0, 2.0);
List<?> results = tree.query(queryBox);
// 返回 [POI-001, POI-003]（与查询框相交的对象）

// 5. 最近邻查询（需配合 ItemDistance）
double[] point = {0.6, 0.6};
Optional<?> nearest = tree.nearestNeighbour(
    new Envelope(point[0], point[0], point[1], point[1]), 
    null, 
    (a, b) -> {
        // 自定义距离计算
        return ((Envelope)a).distance((Envelope)b);
    }
);

2. GeoTools（基于 JTS，企业级）

GeoTools 是更完整的 GIS 工具包，适合需要读写 Shapefile、GeoJSON 等格式的场景。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


<dependency>
    <groupId>org.geotools</groupId>
    <artifactId>gt-shapefile</artifactId>
    <version>29.0</version>
</dependency>
<dependency>
    <groupId>org.geotools</groupId>
    <artifactId>gt-geometry</artifactId>
    <version>29.0</version>
</dependency>

Spring Boot 集成实战

场景：POI 附近搜索

假设有大量 POI（兴趣点）数据，需要实现"查找半径 N 公里内的所有加油站"这类查询。

Step 1：定义 POI 实体

1
2
3
4
5
6
7
8
9


@Data
public class PoiEntity {
    private String id;
    private String name;
    private String category;
    // 经纬度（EPSG:4326）
    private double longitude; // 经度
    private double latitude;   // 纬度
}

Step 2：构建 R-tree 索引服务

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98


@Service
public class SpatialIndexService {

    private final STRtree spatialIndex = new STRtree();
    private final ReadWriteLock lock = new ReentrantReadWriteLock();

    /**
     * 批量构建索引（服务启动时调用）
     */
    @PostConstruct
    public void buildIndex() {
        List<PoiEntity> allPois = poiRepository.findAll();
        
        lock.writeLock().lock();
        try {
            for (PoiEntity poi : allPois) {
                // 将经纬度转为 Envelope（POINT 类型用极小矩形近似）
                Envelope envelope = new Envelope(
                    poi.getLongitude(), poi.getLongitude(),
                    poi.getLatitude(), poi.getLatitude()
                );
                spatialIndex.insert(envelope, poi);
            }
            spatialIndex.build();
        } finally {
            lock.writeLock().unlock();
        }
        
        System.out.println("R-tree 索引构建完成，共 " + allPois.size() + " 条记录");
    }

    /**
     * 范围查询：查找矩形区域内的 POI
     */
    public List<PoiEntity> queryInBox(double minLon, double maxLon, 
                                        double minLat, double maxLat) {
        Envelope queryBox = new Envelope(minLon, maxLon, minLat, maxLat);
        
        lock.readLock().lock();
        try {
            return spatialIndex.query(queryBox).stream()
                .map(item -> (PoiEntity) item)
                .collect(Collectors.toList());
        } finally {
            lock.readLock().unlock();
        }
    }

    /**
     * 圆形范围查询：将圆转为外包矩形做粗筛
     */
    public List<PoiEntity> queryNearby(double longitude, double latitude, 
                                         double radiusKm) {
        // 1. 先用外包矩形做粗筛（约 1.4 倍半径）
        double delta = radiusKm / 111.0; // 约 111km/度
        Envelope rect = new Envelope(
            longitude - delta, longitude + delta,
            latitude - delta, latitude + delta
        );

        return queryInBox(rect.getMinX(), rect.getMaxX(), 
                          rect.getMinY(), rect.getMaxY()).stream()
            .filter(poi -> {
                // 2. 精确计算距离过滤
                double dist = haversine(latitude, longitude, 
                    poi.getLatitude(), poi.getLongitude());
                return dist <= radiusKm;
            })
            .collect(Collectors.toList());
    }

    /**
     * Haversine 公式：计算两点间球面距离（km）
     */
    private double haversine(double lat1, double lon1, double lat2, double lon2) {
        final double R = 6371.0; // 地球半径 km
        double dLat = Math.toRadians(lat2 - lat1);
        double dLon = Math.toRadians(lon2 - lon1);
        double a = Math.sin(dLat / 2) * Math.sin(dLat / 2)
                 + Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2))
                 * Math.sin(dLon / 2) * Math.sin(dLon / 2);
        return R * 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
    }

    /**
     * 动态更新索引（数据变更时调用）
     */
    public void updateIndex(PoiEntity poi) {
        lock.writeLock().lock();
        try {
            // 重新构建（STRtree 不支持单独删除/更新）
            // 生产环境建议用 R-tree 的增删改版本
            buildIndex();
        } finally {
            lock.writeLock().unlock();
        }
    }
}

Step 3：REST 接口

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


@RestController
@RequestMapping("/api/poi")
public class PoiController {

    @Autowired
    private SpatialIndexService spatialIndexService;

    /**
     * GET /api/poi/nearby?lon=116.4&lat=39.9&radius=5
     */
    @GetMapping("/nearby")
    public Result<List<PoiEntity>> nearby(
            @RequestParam double lon,
            @RequestParam double lat,
            @RequestParam(defaultValue = "5") double radius) {
        
        List<PoiEntity> results = spatialIndexService.queryNearby(lon, lat, radius);
        return Result.success(results);
    }

    /**
     * GET /api/poi/box?minLon=116&maxLon=117&minLat=39&maxLat=40
     */
    @GetMapping("/box")
    public Result<List<PoiEntity>> box(
            @RequestParam double minLon,
            @RequestParam double maxLon,
            @RequestParam double minLat,
            @RequestParam double maxLat) {
        
        List<PoiEntity> results = spatialIndexService.queryInBox(
            minLon, maxLon, minLat, maxLat);
        return Result.success(results);
    }
}

性能对比

对 100 万条 POI 数据的实测（ThinkPad X1, JDK 17）：

查询类型	无索引	R-tree 索引
矩形范围查询	~8000ms	~15ms
附近搜索（5km）	~8000ms	~20ms
内存占用	—	~80MB

进阶：使用 JTS 的 Quadtree（另一种选择）

如果数据量较小（<10万），Quadtree 实现更简单：

1
2
3
4
5
6
7
8
9


import org.locationtech.jts.index.quadtree.Quadtree;

Quadtree quadtree = new Quadtree();

// 插入（无需 build）
quadtree.insert(new Envelope(0, 1, 0, 1), "obj1");

// 查询
List<?> results = quadtree.query(new Envelope(0.5, 1.5, 0.5, 1.5));

实现	特点	适用场景
STRtree	R*-tree 变体，查询效率高	生产环境推荐
Quadtree	递归四叉分割，实现简单	数据量小，简单场景

常见问题

Q：STRtree 和 Quadtree 怎么选？

数据量 >50 万、查询频繁 → STRtree 数据量 <10 万、开发阶段快速验证 → Quadtree

Q：支持多边形查询吗？

支持。JTS 的 Envelope 和 intersects() 方法可以判断任意几何对象的相交关系。

Q：数据动态更新怎么办？

STRtree 本身不支持增量更新（插入/删除后需重建）。如果需要动态更新：

数据量 <100 万：每次变更重建
数据量 >100 万：使用 R-tree 的持久化版本*，如 H2GIS 或 PostGIS 的空间索引

Q：和 PostGIS 比有什么优势？

PostGIS 的 GIST 索引底层就是 R-tree（实际是 R*-tree）。如果数据已经存在 PostgreSQL 中，直接用 PostGIS 索引查询更省心。如果是纯 Java 内存场景（如游戏地图、LBS 服务），JTS STRtree 是更好的选择。

总结

R-tree 是空间索引领域最经典的数据结构，JTS STRtree 提供了生产级的 Java 实现。通过外包矩形层层索引，它将空间查询从 O(n) 降到 O(log n) 量级，配合 Haversine 距离公式，可以高效解决附近的搜索问题。

完整示例源码：https://github.com/Gearinger/gear-springboot-demo

参考文档：

JTS Wiki: https://github.com/locationtech/jts
Guttman 原始论文: R-Trees: A Dynamic Index Structure for Spatial Searching