Boost RTree的rtree.begin()为何缓慢？求优化方法

问题描述 #

我基于boost::geometry::index（bgi）库实现RTree算法，用于存储多达数十亿个2D点。业务逻辑为：随机选取树中一点，基于该点执行查询，将查询结果与选中点从树中删除，重复至树为空。

最初采用版本2方案：配合unordered_set存储点ID，删除树中点时同步删除对应ID，性能表现良好，但会占用额外内存。为节省内存改用版本1方案，直接依赖rtree.empty()判断循环结束，从树中取点并删除，但执行速度远慢于版本2。通过简化测试代码对比，怀疑rtree.begin()是性能瓶颈。

编译环境：g++ 9.4.0、Boost 1.80，编译参数-Wall -Wextra -g3。测试代码如下：

#include <iostream>
#include <vector>
#include <ctime>
#include <chrono>
#include <unordered_set>
#include <numeric>

#include <boost/geometry.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>

namespace bg  = boost::geometry;
namespace bgi = bg::index;
namespace bgm = bg::model;

typedef bgm::point<float, 2, bg::cs::cartesian> Point;
typedef std::pair<Point, int> PtPair;

boost::mt19937 gen;
int roll_die(int min, int max) {
    boost::uniform_int<> dist(min, max);
    boost::variate_generator<boost::mt19937&, boost::uniform_int<> > die(gen, dist);
    return die();
}

int main() {
    using Tree = bgi::rtree<PtPair, bgi::rstar<16> >;
    const int NP = 1000000;
    std::vector<PtPair> pts;
    
    pts.reserve(NP);
    int rdmin = 1;
    int rdmax = 1000;
    gen.seed(static_cast<unsigned int>(std::time(NULL)));

    for(int i = 0; i < NP; ++i) {
        pts.push_back(PtPair(Point(roll_die(rdmin, rdmax), roll_die(rdmin, rdmax)), i));
    }

    // 版本1：直接操作RTree
    Tree rtree(pts);
    std::cout << "Tree contains " << rtree.size() << " points." << std::endl;

    std::chrono::time_point<std::chrono::system_clock> start, end;
    std::cout << "version 1 ====================================\n";
    start = std::chrono::system_clock::now();
    
    while (!rtree.empty()) {
        auto it_tree = rtree.begin();
        auto pt_temp = it_tree->first;
        auto pt_id = it_tree->second;

        /* 省略：查询及删除结果集的逻辑 */
        
        rtree.remove(*it_tree);
    }
    
    end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
    std::cout << (rtree.empty() ? "empty rtree\n" : "");

    // 版本2：配合unordered_set
    std::cout << "version 2 ====================================\n";
    std::vector<int> vec_temp(NP);
    std::iota(vec_temp.begin(), vec_temp.end(), 0);
    std::unordered_set<int> set_op(std::begin(vec_temp), std::end(vec_temp));
    Tree rtree2(pts);
    start = std::chrono::system_clock::now();

    while (!rtree2.empty()) {
        auto it = set_op.begin();
        auto pt_temp = pts[*it].first;
        auto pt_id = pts[*it].second;

        /* 省略：查询及删除结果集、同步删除set_op中ID的逻辑 */

        rtree2.remove(pts[*it]);
        set_op.erase(it);
    }
    
    end = std::chrono::system_clock::now();
    elapsed_seconds = end - start;
    std::cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
    std::cout << (rtree2.empty() ? "empty rtree2\n" : "");
}

原因分析 #

1. rtree.begin()的实现开销：Boost RTree采用R*树结构，begin()需要从根节点遍历到最左侧的叶子节点，获取空间排序的第一个元素，时间复杂度为O(log n)。每次删除操作会触发树的节点分裂/合并调整，反复调用begin()会累积大量遍历开销，这是版本1性能差的核心原因。
2. 版本2的对比优势：unordered_set::begin()是O(1)操作，直接返回哈希表的第一个元素，无需遍历复杂的树结构，单次取点开销极低。
3. 业务逻辑偏差：版本1中用rtree.begin()并非真正的“随机取点”——R*树的迭代器是按空间顺序遍历，而非随机选取，这其实不符合业务需求。

优化方案（保留版本1架构，不依赖额外ID集合） #

1. 正确实现随机取点，替代rtree.begin() #

Boost RTree无直接随机访问接口，但可通过以下方式高效获取随机点：

• 使用bgi::nth_element获取第k个元素，结合随机索引实现真正的随机选取：

// 生成随机索引（需确保rtree.size() > 0）
boost::uniform_int<size_t> dist(0, rtree.size() - 1);
size_t rand_idx = dist(gen);

// 获取第rand_idx个元素，时间复杂度O(log n)
auto it_tree = bgi::nth_element(rtree, rand_idx);
PtPair selected = *it_tree;

2. 批量删除减少树结构调整 #

每次查询后收集所有待删除元素（包括选中点和查询结果），一次性执行删除操作。RTree每次删除都会触发节点调整，批量操作可大幅减少调整次数，降低整体开销。

3. 调整RTree节点参数 #

当前使用bgi::rstar<16>，可尝试增大节点大小（如32、64），减少树的高度，从而降低遍历和调整的开销。节点大小建议匹配缓存行大小（如64字节倍数），提升缓存命中率。

4. 启用编译优化 #

当前编译参数-g3会启用调试信息，严重影响运行效率。生产环境改用-O2或-O3优化级别，同时去掉-g3，可大幅提升RTree操作速度。

5. 迭代器范围批量处理（适合中大规模数据） #

若内存允许，可一次性获取树的所有元素迭代器，随机打乱后逐个处理删除。但此方式不适合数十亿级别的点数据，避免内存溢出。

内容的提问来源于stack exchange，提问作者learner_lyf