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

Checkout how it works at bbtree.xiangpeng.systems.

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.

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.