Standard Collections

BTreeMap<K, V>

BTreeMap<K, V> (std::collections::BTreeMap) is an ordered key-value associative map backed by a cache-friendly B-Tree that keeps keys sorted by K: Ord at all times and supports $O(\log n)$ lookup, insertion, removal, min/max queries, and key-range iteration.

Why Rust Uses a B-Tree Instead of a Binary Search Tree

Traditional balanced binary search trees (such as Red-Black or AVL trees, like C++'s std::map) allocate a separate heap node for every single (K, V) pair with parent/left/right pointers—incurring high memory overhead and a CPU cache miss on every tree level.

Rust's BTreeMap groups multiple keys and values (B = 6, storing up to 2B - 1 = 11 key-value pairs per node) in contiguous arrays inside each heap node:

Single B-Tree Node (up to 11 keys and 11 values in contiguous arrays):
+-----------------------------------------------+
| keys:   [ 10 | 25 | 40 | 60 | 85 | .. ]       |  <-- scanned in 1-2 CPU cache lines
| vals:   [ v0 | v1 | v2 | v3 | v4 | .. ]       |
| edges:  [ e0 | e1 | e2 | e3 | e4 | e5 | .. ]  |
+-----------------------------------------------+

Core BTreeMap<K, V> Operations

Operation Method Time Complexity
Insert / lookup / remove map.insert(k, v) / map.get(&q) / map.remove(&q) $O(\log n)$
Smallest key-value pair map.first_key_value() / map.pop_first() $O(\log n)$
Largest key-value pair map.last_key_value() / map.pop_last() $O(\log n)$
Ordered range iteration map.range(start..=end) / map.range_mut(start..=end) $O(\log n + k)$ for $k$ yielded items 
use std::collections::BTreeMap;

fn main() {
    let mut timeline = BTreeMap::from([
        (1050_u64, "deploy_finished"),
        (1000, "build_started"),
        (1020, "tests_passed"),
        (1010, "lint_ok"),
    ]);

    println!("First event: {:?}", timeline.first_key_value());
    println!("Last event:  {:?}", timeline.last_key_value());

    // Efficient range query over timestamps in `1005..=1030`:
    println!("Events in 1005..=1030:");
    for (ts, event) in timeline.range(1005..=1030) {
        println!("  [{ts}] {event}");
    }

    let popped_earliest = timeline.pop_first();
    println!("Popped earliest: {popped_earliest:?}");
}

First event: Some((1000, "build_started"))
Last event:  Some((1050, "deploy_finished"))
Events in 1005..=1030:
  [1010] lint_ok
  [1020] tests_passed
Popped earliest: Some((1000, "build_started"))