bbtree vs BTreeMap: Which API Fits Your Rust Workload?
The bbtree author reports 5× the single-thread speed of BTreeMap. If your Rust service leans on range queries, how much of your existing read code survives the switch?
- bbtree is a Rust ordered map for sorted traversal and range queries.
- The unsync map lends references like BTreeMap; the concurrent map uses copied values or read closures.
- The author reports a 5× speedup over BTreeMap on one thread and 12× over crossbeam-skiplist at 96 threads.
HashMap lookups versus ordered ranges
HashMap fits a lookup by account ID. Reading every key from 100 through 200 in order calls for an ordered map. Rust’s collection guide recommends BTreeMap for sorted keys, range queries and minimum or maximum lookups.
bbtree offers ordered access through separate single-threaded and concurrent map APIs. Like BTreeMap, it follows the key’s Ord implementation. Timestamp keys produce chronological traversal; account-ID keys produce account-ID order.
The unsync map lends references like BTreeMap
In version 0.1.5, bbtree::unsync::BBTreeMap provides the BTreeMap-style interface. Mutations use exclusive access. get returns a reference to a stored value, while range traverses a selected interval.
range(100..200) includes 100 and excludes 200. Use range(100..=200) to include both endpoints.
| Requirement | Candidate to evaluate |
|---|---|
| Individual lookups without ordering | Keep the existing HashMap as the baseline |
| BTreeMap-style ownership and ordered access | bbtree::unsync::BBTreeMap |
| Multiple threads reading and changing one map | bbtree::BBTreeMap |
Concurrent reads use copies or closures
The concurrent BBTreeMap returns a copied value through get_copied. To work with a value without copying it, use a read closure. Calling into the same map from inside that closure can deadlock.
A scan does not freeze the entire map at one instant. Another thread can insert or remove entries during traversal, and those entries may be visited or missed. It therefore does not provide the point-in-time view required by a snapshot read.
Concurrent keys require InlineKey support for order-preserving encoding. A custom key outside the default strategy’s coverage needs its own implementation and strategy. Moving from unsync to the concurrent map changes these key requirements as well as the read API.
5× over BTreeMap, 12× over crossbeam-skiplist
The README reports a 5× speedup over standard BTreeMap on one thread and 12× over crossbeam-skiplist at 96 threads. The first compares single-threaded ordered maps; the second compares concurrent data structures under a multithreaded workload.
The unsync type provides the matching API for existing BTreeMap code. The concurrent BBTreeMap supports multiple threads reading and changing one map. Copying values and consuming an entire range also contribute to the application’s total processing time.