bbtree

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):

5x faster than std's BTreeMap at single thread, 12x faster than crossbeam-skiplist at 96 threads.
30% lower memory usage, 5x lower p99 latency.
Zero dependencies, no_std compatible.
unsync::BBTreeMap is a drop-in replacement for std's BTreeMap/BTreeSet.
Production-ready by formal verification, model checking, fuzzing, and lots of testing.
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

Implement InlinkeKey trait for best performance, check how String and Vec implement it.
Consider using batching api if semantically appropriate.
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.