rtree

> 编程语言

开源

在 Java 中实现不变的内存 R 树和 R*-树,采用反应式 API

1.1K stars0 点赞1 次浏览

访问官网 GitHub

工具介绍

在 Java 中实现不变的内存 R 树和 R*-树,采用反应式 API

rtree ===========

在内存中实现了不可变的 2D R-tree,使用 RxJava Observables 来对搜索结果进行反应式处理。

实现不可变性的算法很可爱。对于插入/删除操作，它需要递归到所需的叶子节点，然后再递归回上方，替换父节点直至根节点。其核心代码位于 Leaf.java 和 NonLeaf.java。

Backpressure 支持需要一些复杂性，因为实际上需要保留树中某个位置的书签，并随后返回继续遍历。一个不可变的栈包含了路径节点的节点和子节点索引，这在这里起到了救命作用，并放弃了递归，转而使用循环来防止栈溢出（不幸的是，Java 不支持尾递归！）。Maven 站点报告在这里，包括 javadoc。

特性 --------------- * 适用于并发的不可变 R-tree * Guttman 的启发式算法 (二次分割器) (论文) * R*-tree 启发式算法 (论文) * 可自定义分割器和选择器