Finally something that I think is a worthwhile contribution from me to the Rust ecosystem :'D Almost 2 months of work porting this almost insane data structure from a research grade C++ implementation... but it seems to be worth it based on the current performance under high contention, where the std RwLock<BTreeMap> seems to fall behind significantly, so it may be of use for some actual projects. I am actually considering rewriting it in nightly because some of the unstable features would make the implementation much easier and maintainable. I will highly appreciate any feedback.

A high-performance concurrent ordered map for Rust. It stores keys as &[u8] and supports variable-length keys by building a trie of B+trees, based on the Masstree paper.

Keeping this post short, because I know it's a really niche and complex data structure that not many people will be interested in. Please check links below, I tried to keep an iterative divan benchmark record throughout the development, which you will be able to find in the repo inside the runs/ folder. It does win in almost all realistic workload against similar data structures compared with (which is highly suspicious and I am not sure what else I can do to make the benches more fair and rigorous O.O).

Crate: crates.io: Rust Package Registry
Repo: GitHub - consistent-milk12/masstree: An implementation of the C++ Masstree data structure in Rust.
C++ Reference: GitHub - kohler/masstree-beta: Beta release of Masstree.

Disclaimer: Yes, a $20 claude subscription was used during development to write the large amount of tests and docs for the codebase :'D Sorry! I checked most of them, but some of the docs may still be stale, especially for the WIDTH 24 variant, which I wouldn't recommend using anyway.

1 post - 1 participant

Read full topic