The Problem

Applications that rely on an ordered key/value store often use the standard library’s BTreeMap. At high concurrency it becomes a bottleneck: insertions and lookups contend on a single lock, and the map’s memory layout leads to cache misses. Developers need a low‑latency, high‑throughput ordered map that can be dropped in without adding external dependencies.

What This Does

bbtree supplies two drop‑in replacements for BTreeMap.

  • bbtree::BBTreeMap – a lock‑free concurrent map.
  • bbtree::unsync::BBTreeMap – a single‑threaded version with identical API.

Both reside in bbtree/src/lib.rs. Internally the map is a B‑tree whose nodes are laid out in contiguous pages (bbtree/src/tree/node/*.rs). Keys implement the InlineKey trait (bbtree/src/inline_key.rs) for high‑speed comparisons. The concurrent implementation uses fine‑grained latching (bbtree/src/tree/latched/*.rs) and a lock‑free allocator (bbtree/src/allocator.rs). No external crates are required; the crate is no_std compatible.

How It Is Wired

ENTRY POINT – bbtree/src/lib.rs re‑exports BBTreeMap and unsync::BBTreeMap. INSERT – BBTreeMap::insert → bbtree/src/map/mod.rs → bbtree/src/tree/insert.rs. The insert routine walks the tree using bbtree/src/tree/latched/lookup.rs for a read‑only path, then acquires a latch on the target node (latched/insert.rs). If a split is needed, bbtree/src/tree/latched/batch.rs performs the split in a single atomic batch. LOOKUP – BBTreeMap::get_copied → bbtree/src/map/mod.rs → bbtree/src/tree/search.rs. The search path reads through latched/lookup.rs without mutating latches, returning a copied value. RANGE – BBTreeMap::range delegates to bbtree/src/tree/range.rs, which walks leaf nodes and yields key/value pairs.

The only external effect is on the OS file system when bbtree-mmap is used. Its entry point is bbtree-mmap/src/lib.rs; it opens a memory‑mapped file (mapped_file.rs) and constructs a map that persists across processes. All other modules are in‑memory.

How To Use It

Setup – add to a Cargo project:

cargo add bbtree

The repository contains a Cargo.toml with the dependency declaration. No additional build steps are required.

Configuration – none required for the in‑memory map. For the mmap variant, create a file and pass its path to bbtree-mmap::BbtreeMapFile::open(&path). No environment variables or config files are present.

Running a tiny example – see README.md for snippets. To build the examples in bbtree-mmap/examples/, run:

cargo run --example first_query

This pulls bbtree-mmap/src/lib.rs as the entry point.

Real‑World Use

An OLTP service that needs ordered keys with sub‑microsecond lookups can drop bbtree::unsync::BBTreeMap in place of a HashMap for read‑heavy workloads. For a multi‑process analytics engine, bbtree-mmap::BbtreeMapFile can be mounted once and shared between workers, avoiding serialization overhead.

Code Health & Issues

  • Tests – 28 test files (bbtree/src/map/tests/*.rs, bbtree/src/unsync/map/tests/*.rs).
  • CI – GitHub Actions workflows (.github/workflows/*.yml) run unit tests, miri checks, sanitizer builds, fuzzing, and formal verification (verus.yml).
  • Dependencies – Zero runtime dependencies; only alloc and core.
  • License – Dual Apache‑2.0 / MIT (LICENSE).

No structural red flags were reported in the static analysis. All entry points and public APIs are well documented in README.md and Rustdoc comments.

The Bottom Line

bbtree delivers a fast, zero‑dependency ordered map suitable for both single‑threaded and highly concurrent workloads. Its rigorous test suite and formal verification give confidence for production use. The API is straightforward, but developers must implement the InlineKey trait for custom key types to reach peak performance. The mmap variant adds persistence with minimal overhead, though it requires a writable file. Overall, the crate is ready for deployment in performance‑critical Rust services.