bbtree README

项目的 README,来自 github.com/XiangpengHao/bbtree。合并为一个 markdown 文件:README.md。

bbtree

crates.io docs.rs
test miri sanitizer DST fuzzing verification

B-trees are by far the most important access path structure in database and file systems. — Jim Gray

bbtree is by far the fastest btree (ordered map):

  1. 5x faster than std's BTreeMap at single thread, 12x faster than crossbeam-skiplist at 96 threads.
  2. 30% lower memory usage, 5x lower p99 latency.
  3. Zero dependencies, no_std compatible.
  4. unsync::BBTreeMap is a drop-in replacement for std's BTreeMap/BTreeSet.
  5. Production-ready by formal verification, model checking, deterministic simulation, fuzzing, and lots of testing.
  6. Brought to you by decades of database research and careful curation by Xiangpeng Hao.

bbtree vs other concurrent maps, get throughput at 96 threads

Checkout how it works at bbtree.xiangpeng.systems.

Usage

cargo add bbtree

Concurrent bbtree

use bbtree::BBTreeMap;

let map = BBTreeMap::new();

std::thread::scope(|scope| {
    scope.spawn(|| map.insert(1_u64, 10_u64));
    scope.spawn(|| map.insert(2, 20));
});

assert_eq!(map.get_copied(&1), Some(10));
assert_eq!(map.read(&2, |_, value| value + 1), Some(21));
assert_eq!(map.get_many_copied([&1, &2, &3]), [Some(10), Some(20), None]);

Single thread

use bbtree::unsync::BBTreeMap;

let mut map = BBTreeMap::new();
map.insert(1, "one");
map.insert(2, "two");
assert_eq!(map.get(&1), Some(&"one"));

Agent's guide

  1. Implement InlinkeKey trait for best performance, check how String and Vec implement it.
  2. Consider using batching api if semantically appropriate.
  3. Create an issue here if you see any performance regression.

license

Licensed under either of Apache License, Version 2.0 or MIT license, at your option; LICENSE holds both texts.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in bbtree by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

bbtree (XiangpengHao/bbtree)

正在搜索数据库…

667 ·GitHub
这是什么?bbtree 是一个 Rust 库,实现了并发有序映射(B 树),官方称它是目前最快的同类实现:单线程下比标准库的 BTreeMap 快 5 倍,在 96 线程下比 crossbeam-skiplist 快 12 倍。
这是要加到我项目里的库,还是一个独立的数据库?它是一个 Rust crate(库),不是独立的服务器或数据库。它提供了用于多线程场景的并发 BBTreeMap,以及用于单线程场景的 unsync::BBTreeMap。
怎样把它添加到 Rust 项目里?将 bbtree 添加为 Cargo 依赖。多线程场景使用并发的 BBTreeMap;单线程场景可以直接用 unsync::BBTreeMap 替换标准库的 BTreeMap 或 BTreeSet。
它会引入其他外部依赖吗?不会。它没有任何依赖,并且兼容 no_std,因此可以在资源受限或嵌入式环境中运行,无需标准库。
怎样才能让它发挥最佳性能?使用自定义键类型时,为获得最佳性能,请参照 String 和 Vec 的实现方式,自行实现 InlinkeKey trait;如果符合你的工作负载,也可以考虑使用批处理 API。
bbtree 相比其他方案究竟快多少?README 声称:单线程下比标准库的 BTreeMap 快 5 倍,96 线程下比 crossbeam-skiplist 快 12 倍,内存占用低 30%,p99 延迟低 5 倍。
像这样的并发数据结构,正确性是如何验证的?项目声明,它已通过形式化验证、模型检测、确定性模拟、模糊测试以及大量测试,可用于生产环境。
我能直接把现有的 BTreeMap 换成 bbtree 吗?可以。unsync::BBTreeMap 的设计目的就是在单线程代码中直接替换标准库的 BTreeMap 和 BTreeSet。
大小
3.7 MB
星标
667
时长
1个月
提交 · 90 天