空间索引与数据分片：构建R-tree、四叉树等空间索引

地图数据量一大，最头疼的问题就来了——查询慢。我早期做高精地图的时候，遇到过一辆车在路口等了几秒钟才加载完周围路网的情况。嗯，那会儿我就意识到，没有空间索引，地图就是个死数据。

说白了，空间索引就是给地图数据「划片儿」。你想想看，一个城市几百万条车道线、几十万个交通标志，如果每次查询都全量扫描，那CPU得累死。我们需要一种机制，让查询只落在「可能相关的」数据块上。

R-tree：高维空间查询的利器

R-tree 是我个人最常用的空间索引结构。它把空间对象用最小外接矩形（MBR）包裹起来，然后逐层聚合。查询的时候，从根节点往下走，只访问那些与查询区域相交的节点。

我在项目中遇到过一个问题：R-tree 的节点分裂策略直接影响查询性能。如果分裂得不好，兄弟节点的 MBR 重叠区域太大，查询时就得同时走多个分支，性能直接打折扣。

// 简化的R-tree节点结构
struct RTreeNode {
    Rect mbr;           // 最小外接矩形
    bool isLeaf;        // 是否为叶子节点
    union {
        RTreeNode* children[MAX_CHILDREN];  // 内部节点
        MapObject* objects[MAX_OBJECTS];    // 叶子节点
    };
    int count;          // 子节点或对象数量
};

// 查询：给定一个矩形区域，返回所有相交的对象
void query(RTreeNode* node, const Rect& queryRect, vector<MapObject*>& result) {
    if (!node->mbr.intersects(queryRect)) return;  // 剪枝
    
    if (node->isLeaf) {
        for (int i = 0; i < node->count; i++) {
            if (node->objects[i]->bbox.intersects(queryRect)) {
                result.push_back(node->objects[i]);
            }
        }
    } else {
        for (int i = 0; i < node->count; i++) {
            query(node->children[i], queryRect, result);
        }
    }
}

四叉树：均匀空间划分的经典方案

四叉树跟 R-tree 的思路不太一样。它把空间均匀地四等分，递归下去。适合数据分布比较均匀的场景，比如城市道路网。

我曾经在做一个全国地图的预加载系统时，发现四叉树的深度控制很关键。深度太浅，每个叶子节点包含的数据太多；深度太深，树本身的内存开销就上去了。

深度	叶子节点数	每个叶子平均数据量	查询耗时(ms)
4	256	~1200条	45
6	4096	~75条	12
8	65536	~5条	8

你看这个表，深度从4到6，查询时间降了将近4倍。但再往深走，收益就不明显了，反而内存占用翻了好几倍。所以，我一般建议深度控制在6-7层。

空间分片：把地图切成「瓦片」

空间索引是逻辑上的组织方式，空间分片则是物理上的存储策略。说白了，就是把地图按经纬度切成一块一块的瓦片，每个瓦片独立存储、独立加载。

我习惯用墨卡托投影的瓦片网格，因为它是全球统一的。每个瓦片有一个唯一的行列号，查询的时候直接计算瓦片ID，比遍历索引树还快。

// 瓦片ID计算
struct TileID {
    int x, y, z;  // 行列号 + 层级
};

TileID latLonToTile(double lat, double lon, int zoom) {
    TileID tile;
    double n = pow(2.0, zoom);
    double latRad = lat * M_PI / 180.0;
    
    tile.x = (int)((lon + 180.0) / 360.0 * n);
    tile.y = (int)((1.0 - log(tan(latRad) + 1.0/cos(latRad)) / M_PI) / 2.0 * n);
    tile.z = zoom;
    
    return tile;
}

// 加载车辆周围9宫格瓦片
void loadSurroundingTiles(double lat, double lon, int zoom) {
    TileID center = latLonToTile(lat, lon, zoom);
    
    for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            TileID neighbor = {center.x + dx, center.y + dy, zoom};
            loadTileFromDisk(neighbor);  // 异步加载
        }
    }
}

索引与分片的协同策略

光有索引或者光有分片都不够。我个人的做法是：先用四叉树做粗粒度分片，每个叶子节点对应一个瓦片文件。然后在瓦片内部，用R-tree做细粒度索引。

这样做的原因是：四叉树适合「快速定位到哪个瓦片」，R-tree适合「在瓦片内精确查找」。两者结合，查询效率能提升一个数量级。

嗯，这里要注意一点：瓦片边界上的对象怎么办？比如一条车道线横跨两个瓦片。我的做法是：在瓦片边界处做「重叠存储」，即边界上的对象在两个瓦片里都存一份。虽然多了点冗余，但避免了跨瓦片查询的复杂逻辑。

你想想看，如果每次查询都要去合并两个瓦片的结果，那代码复杂度就上去了。而且合并过程中还要去重，性能损耗不小。所以，用一点存储换代码简洁和查询速度，我觉得值。

最后总结一下我的经验：空间索引选型要看数据分布。均匀分布用四叉树，不均匀用R-tree。分片粒度要跟查询范围匹配，车辆周围9宫格是最常用的。索引和分片要协同设计，不要各自为政。