Ordered Collections

Performance and Complexity

BTreeMap<K, V> and BTreeSet<T> guarantee $O(\log n)$ worst-case time for all single-element lookups and updates, while achieving much better CPU cache locality and lower memory overhead than pointer-per-element binary search trees.

Asymptotic Complexity Summary for BTreeMap and BTreeSet

($n$ = number of elements in self, $m$ = number of elements in other, $k$ = number of elements in the queried range.)

Operation Method Time Complexity Notes
Lookup get(&k), contains_key(&k), contains(&x) $O(\log n)$ $\approx \log_{12}(n)$ node hops + linear/binary scan of $\le 11$ keys
Insert insert(k, v), entry(k).or_insert(v) $O(\log n)$ Splits full 11-key nodes on the path
Remove remove(&k), pop_first(), pop_last() $O(\log n)$ Rebalances underfull ($< 5$ keys) nodes
Min / Max inspect first_key_value(), last_key_value(), first(), last() $O(\log n)$ Walks leftmost or rightmost spine of the B-Tree
Range query range(start..end), range_mut(start..end) $O(\log n + k)$ $O(\log n)$ seek to start, then $O(1)$ amortized step per item
Split at key split_off(&key) $O(\log n)$ Splits tree along root-to-leaf path for key
Merge two trees a.append(&mut b) $O(n + m)$ Linear sorted merge
Full iteration iter(), keys(), values(), into_iter() $O(n)$ Visits only populated slots (unlike HashMap's $O(\text{capacity})$)

Cache Locality: B-Tree ($B = 6$) vs. Red-Black Tree ($B = 1$)

Red-Black Tree (1 key per node):
  1,000,000 items ──> ~20 pointer dereferences (up to 20 L3/RAM cache misses!)
                      + 3 pointers (24 bytes) overhead per single element

Rust BTreeMap (B = 6, up to 11 keys per node):
  1,000,000 items ──> ~5–6 node dereferences (only 5–6 cache lines fetched!)
                      + keys packed contiguously inside each node

Comparing Sorted Vec<(K, V)> vs. BTreeMap<K, V>

When a dataset is built once and queried many times without interleaved insertions/removals, a sorted Vec<(K, V)> queried via .binary_search_by_key(&k, |(k, _)| k) uses a single contiguous allocation with zero node pointers. Use BTreeMap<K, V> when insertions, removals, and queries are interleaved dynamically, since inserting into the middle of a Vec<(K, V)> costs $O(n)$ whereas inserting into a BTreeMap<K, V> costs $O(\log n)$:

use std::collections::BTreeMap;

fn main() {
    // Dynamic workload: interleaved insertions, range queries, and removals -> BTreeMap
    let mut metrics = BTreeMap::new();
    for step in [40, 10, 30, 20, 50] {
        metrics.insert(step, step * 100);
    }
    metrics.remove(&30);

    let active_range: Vec<_> = metrics.range(15..=45).collect();
    println!("Interleaved BTreeMap range 15..=45: {active_range:?}");
}

Interleaved BTreeMap range 15..=45: [(20, &2000), (40, &4000)]