Interavl

这个crate实现了一个由增强的平衡二叉搜索树（一个AVL树 - interavl - 看到没？）支持的区间树。

IntervalTree将半开区间映射到不透明值，并提供高效查询所有存储的(interval, value)元组，这些元组匹配由Allen的区间代数描述的各种时间关系。

使用它

use interavl::IntervalTree;

// Initialise an empty tree.
let mut t = IntervalTree::default();

// Insert interval & value tuples into the tree.
//
// Intervals can be composed of any type that implements "Ord" such
// as timestamps, strings, etc.
t.insert(24..80, "Bob");
t.insert(10..100, "Doris");
t.insert(40..55, "Frank");
t.insert(100..400, "Nigel");

// Find which intervals overlap with a query interval:
for (interval, name) in t.iter_overlaps(&(42..50)) {
	println!("{name} overlaps (matching interval is {interval:?})");
}

性能

针对IntervalTree的查找操作非常快速，每秒可执行数百万/数十亿个键

由于使用子树剪枝来减少搜索空间，区间戳记和成员资格查询特别快速。[^filter-perf]

• 构建树：将列出的N个键插入到空树中（包括随机值生成）
• 查找值：在树中查找一个区间，并返回其值
• 戳记查询：产生与给定查询区间重叠的所有区间

上述测量捕获了在M1 MacBook Pro上具有不同键数的树的单线程操作性能。

生成这些数字的基准测试包含在此仓库中（运行cargo bench）。

[^filter-perf]：区间戳记每秒过滤约53亿个区间。