geo-index

一个用于紧凑、静态、零拷贝空间索引的Rust包。

特性

• 使用安全的Rust编写的R树和k-d树。
• 快速。由于可以使用静态索引实现的优化，通常比像rstar这样的动态实现更快。
• 内存高效。索引完全紧凑，这意味着所有节点都处于满容量（除了每个树级别的最后一个节点）。这意味着RTree使用的内存更少。由于索引由单个缓冲区支持，因此具有出色的内存局部性。对于任何数量的输入几何形状，构建索引和存储索引时峰值内存使用量都可以预先计算。
• 多种R树排序方法。目前实现了希尔伯特和排序-瓦片-递归（STR）排序方法，但可以扩展到其他空间排序算法，如重叠最小化自上而下（OMT）。
• ABI稳定：索引包含在一个单个的Vec<u8>中，与flatbush和kdbush JavaScript库兼容。ABI稳定意味着空间索引可以在Rust和另一个程序（如Python）之间共享零拷贝。
• 泛型坐标类型集： i8、u8、i16、u16、i32、u32、f32、f64。
• 高效的批量加载。作为一个静态索引，仅支持批量加载。
• 可选的rayon功能，用于并行化排序-tile-递归（STRSort）方法中的部分排序。

缺点

• 树是静态的。创建索引后，无法再添加或删除项目。
• 仅支持二维数据。如果您只需索引两个维度，则仍可用于更高维度的输入。
• 只允许在JavaScript中存在的坐标类型集合，以保持与参考JavaScript实现的FFI兼容性。这不支持也不会支持其他类型，如u64。
• 查询返回输入集的位置索引，因此您必须管理自己的集合。

替代方案

• rstar：一个动态RTree实现。
• kdtree：一个动态KDTree实现。
• kdbush：是kdbush的一个移植版本，但并不追求FFI兼容性。
• static_aabb2d_index：是flatbush的一个移植版本，但并不追求FFI兼容性。
• static-bushes：是flatbush和kdbush的一个移植版本，但并不追求FFI兼容性。

灵感

@mourner的惊人的flatbush和kdbush库是JavaScript中静态R树和k-d树最快的库。它们在浏览器中的吸引力之一在于它们由一个单一、连续的缓冲区支持，因此可以从主线程移动到另一个线程（一个web worker）无需任何复制。

通过移植和扩展这些JavaScript库，并确保内部内存布局完全保持不变，我们可以在浏览器内外启动零复制用例。在浏览器内使用的情况可以在基于Rust的WebAssembly模块和上游JS库之间互操作，无需复制。在浏览器外使用的情况可以在多个Rust库之间或Rust和Python之间互操作，无需复制。

为什么是零复制？

我很高兴Rust可以通过编译扩展模块加速Python和JavaScript。确实，您可以为Rust库创建Python绑定，让Rust管理内存，并且永远不必担心零复制数据结构。但如果有其他人为C库编写，希望与您的数据接口，如果您没有稳定的ABI来共享数据，您需要序列化它，他们需要反序列化它，这是昂贵的。

例如，在Python中，Shapely（以及通过扩展的C库GEOS）用于大多数地理空间数据存储。但具有C扩展的独立Python库无法使用相同的GEOS内存，因为底层存储不是ABI稳定的。因此，必须在之间进行serde步骤。

GeoArrow为地理空间矢量数据解决了这个问题，因为它定义了一个语言无关、ABI稳定的内存布局。因此，您可以通过交换指针信息安全地在Python/Rust/C之间移动内存。

但能够以零成本共享大量空间数据、声明数据已经空间排序、并且共享空间索引，是非常有用的。

目前，这个库在geoarrow-rs中作为底层使用，以加速布尔运算和空间连接操作。但从中长期时间范围来看，我相信暴露原始索引数据将能够实现目前无法实现的激动人心的FFI用例。

未来工作

• 在R树上的最近邻查询。这已在原始JS版本中实现，但尚未移植。
• 地理查询。目前所有查询都是平面查询。

基准测试

这只是一个基准测试；我建议使用您自己的数据进行基准测试，但这也表明构建速度比rstar快约2倍，搜索速度约快33%。

cargo bench --bench rtree

construction (geo-index, hilbert)
                        time:   [80.503 ms 80.891 ms 81.350 ms]
construction (geo-index, STRTree)
                        time:   [115.60 ms 116.52 ms 117.64 ms]
construction (geo-index, hilbert, f64 to f32, including casting)
                        time:   [86.409 ms 86.681 ms 86.984 ms]
construction (geo-index f32)
                        time:   [78.292 ms 78.393 ms 78.514 ms]
construction (rstar bulk)
                        time:   [158.48 ms 159.34 ms 160.29 ms]

search (flatbush)       time:   [115.97 µs 116.41 µs 116.86 µs]
search (flatbush STRTree)
                        time:   [115.85 µs 117.57 µs 118.95 µs]
search (flatbush f32)   time:   [113.04 µs 114.56 µs 115.99 µs]
search (rstar)          time:   [151.53 µs 153.62 µs 155.84 µs]

使用rayon功能，STRTree的排序阶段更快

cargo bench --bench rtree --features rayon

construction (geo-index, STRTree)
                        time:   [71.825 ms 72.099 ms 72.382 ms]
                        change: [-38.738% -38.125% -37.570%] (p = 0.00 < 0.05)
                        Performance has improved.