GitHub - XiangpengHao/bbtree: Fastest concurrent ordered map

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.

Checkout how it works at bbtree.xiangpeng.systems.

Usage

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.