Sweep-bptree(开发中)

内存可扩展的b+树。

特性

• 可扩展的搜索树，例如，您可以使用 Count 参数将树转换为有序统计树。或者创建自己的参数以支持更高级的用法。
• 性能，与std::collections::BTreeMap相当。

安装

[dependencies]
sweep-bptree = "0.4"

示例

映射

作为普通的映射/集合

use sweep_bptree::BPlusTreeMap;

let mut map = BPlusTreeMap::<i32, i32>::new();
map.insert(1, 2);

assert_eq!(map.get(&1).unwrap(), &2);
assert!(map.get(&2).is_none());

有序统计树

或通过 Argument 增强功能

use sweep_bptree::BPlusTreeMap;
use sweep_bptree::argument::count::Count;

// use Count as Argument to create a order statistic tree
let mut map = BPlusTreeMap::<i32, i32, Count>::new();
map.insert(1, 2);
map.insert(2, 3);
map.insert(3, 4);

// get by order, time complexity is log(n)
assert_eq!(map.get_by_argument(0), Some((&1, &2)));
assert_eq!(map.get_by_argument(1), Some((&2, &3)));

// get the offset for key

// 0 does not exists
assert_eq!(map.rank_by_argument(&0), Err(0));

assert_eq!(map.rank_by_argument(&1), Ok(0));
assert_eq!(map.rank_by_argument(&2), Ok(1));
assert_eq!(map.rank_by_argument(&3), Ok(2));

// 4 does not exists
assert_eq!(map.rank_by_argument(&4), Err(3));

双层键

另一个可扩展树的示例。通过内置的 GroupCount 参数，树可以支持双层键，例如 (年, 日期)，(部分, 行) 等。

use sweep_bptree::BPlusTreeMap;
use sweep_bptree::argument::group::{GroupCount, Tuple2};

// Tuple2 use pair's first element as group value
let mut tree = BPlusTreeMap::<_, _, GroupCount<Tuple2<_>>>::new();

// group count is 0 for empty tree
assert_eq!(tree.root_argument().group_count(), 0);

tree.insert((1, 1), 100);
assert_eq!(tree.root_argument().group_count(), 1);
tree.remove(&(1, 1));
assert_eq!(tree.root_argument().group_count(), 0);

tree.insert((1, 1), 100);
tree.insert((1, 2), 101);
assert_eq!(tree.root_argument().group_count(), 1);

// get group size for Tuple2(1)
assert_eq!(
    tree.descend_visit(ExtractGroupSize::new(Tuple2(1))),
    Some(2)
);

// get (k, v) by (group, offset)
assert_eq!(tree.get_by_argument((Tuple2(1), 0)).unwrap().1, &100);

// or get the (group, offset) tuple by key
assert_eq!(tree.rank_by_argument(&(1, 0)), Err(Some((Tuple2(1), 0))));

不安全

此crate使用不安全代码来提高性能。主要用于内存初始化、复制和移动操作。它已通过模糊测试进行测试。

贡献

欢迎贡献！请打开一个问题或一个PR。目前，文档、与 std::collections::BTreeMap 的功能对等性和性能改进是主要兴趣领域。