indexset

一个纯 Rust 动态有序统计 b-tree。

该软件包实现了一种紧凑的集合数据结构，它保留其元素的排序顺序，并允许通过值或排序顺序位置查找条目。

此外，它（在大多数情况下）是 stdlib BTree 的直接替换品。

背景

该项目受到了 indexmap 和 python 的 sortedcontainers 的强烈启发。

与两者不同的是

• indexmap 是一个提供数值查找的哈希表，但在删除的情况下不会保持顺序，而 indexset 是一个始终保持顺序的 BTree，无论执行哪种突变操作。
• sortecontainers 在精神上类似，但使用不同的算法来平衡树，并且依赖于堆进行数值查找。

indexset 提供以下功能

• 与 vec 一样快速迭代。
• 零间接。
• 按位置和范围查找。
• 分配最少的内存。
• select（按位置查找）和 rank（按值查找）操作在接近常数时间内完成。

性能

BTreeSet 和 BTreeMap 从其构建方式直接推导出一些性能事实，大致为

一个二级 B-Tree，其中使用 Fenwick 树作为数值查找的低成本索引

• 迭代非常快，因为它继承了 vec 的迭代结构。
• 在最佳情况下，插入和删除操作是常数时间，在最坏情况下，在节点大小上是对数时间
• 查找非常快，并且仅依赖于少量数据的两次二分搜索。

基准测试

运行 cargo bench 并自行查看。

在一台最低配置的 M1 Macbook Pro 上，我得到了以下数据

插入 100k 随机 usize

• stdlib::collections::BTreeSet.insert(i): 8.25ms
• indexset::BTreeSet.insert(i): 17.3ms

检查每个100k随机usize整数是否存在

• stdlib::collections::BTreeSet.contains(i): 7.5ms
• indexset::BTreeSet.contains(i): 6.8ms

获取所有100k个i-th元素

• stdlib::collections::BTreeSet.iter.nth(i): 13.28s yes, seconds!
• indexset::BTreeSet.get_index(i): 3.93ms

遍历所有100k个元素并将它们收集到一个vec中

• Vec::from_iter(stdlib::collections::BTreeSet.iter()): 227.28us
• Vec::from_iter(indexset::BTreeSet.iter()): 123.21.us

是的。

获取第i个元素比stdlib的btree快3400倍，contains快10%，迭代快两倍，但插入速度减半。

如果你的使用场景是std::collections::BTreeSet和BTreeMap更侧重于读取，或者你确实需要按排序顺序位置索引，那么检查这个indexset可能是有价值的。

局限性

• BTreeMap比BTreeSet更不成熟。这个crate已经针对更精简的BTreeSet进行了优化。
• 这是**beta**级别的软件，所以请自行承担使用风险。我对每个迭代器的实现（尽管所有内容都有测试）并不完全确定。
• 还有相当多的实用特性尚未实现。

命名

这个库叫做indexset，因为基本数据结构是BTreeSet。BTreeMap是一个具有Pair<K, V>项类型的BTreeSet。

变更日志

见CHANGELOG.md。