Ordered Collections

BTreeMap

BTreeMap<K, V> (std::collections::BTreeMap) is a self-balancing ordered associative map backed by a multi-element B-Tree ($B = 6$) that keeps its keys sorted in ascending K: Ord order and guarantees $O(\log n)$ worst-case lookup, insertion, removal, and boundary queries.

Internal B-Tree Node Architecture ($B = 6$)

Unlike a binary search tree (which allocates one node per key and chases pointers at every binary step), Rust's BTreeMap uses a branching factor of $B = 6$:

  • Every non-root node contains between $B - 1 = 5$ and $2B - 1 = 11$ sorted keys (and values) stored in contiguous inline arrays.
  • Internal (non-leaf) nodes also store between $B = 6$ and $2B = 12$ child node pointers (edges).
                Internal Node (up to 11 keys, 12 child pointers)
                +---------------------------------------------+
                | keys: [     20     |     50     | ... ]     |
                | vals: [     v20    |     v50    | ... ]     |
                +---------+----------+----------+-------------+
                          |                     |                     \
                          v                     v                      v
        Leaf Node (< 20)             Leaf Node (20..50)             Leaf Node (> 50)
   +-----------------------+    +------------------------+    +------------------------+
   | keys: [ 5, 10, 15 ]   |    | keys: [ 25, 30, 40 ]   |    | keys: [ 60, 75, 90 ]   |
   | vals: [ v5, v10, v15 ]|    | vals: [ v25, v30, v40 ]|    | vals: [ v60, v75, v90 ]|
   +-----------------------+    +------------------------+    +------------------------+

Because each internal node branches up to 12 ways, a BTreeMap holding 1,000,000 entries has a tree height of at most 5 to 6 levels, and searching within a single node scans a tiny contiguous array inside 1–2 CPU cache lines.

Constructing and Querying a BTreeMap<K, V>

BTreeMap::new() is a const fn that performs zero heap allocation until the first key-value pair is inserted. Unlike HashMap, BTreeMap has no with_capacity or reserve method because B-Tree nodes are allocated incrementally as keys are inserted and split:

use std::collections::BTreeMap;

static EMPTY_MAP: BTreeMap<u32, &str> = BTreeMap::new();

fn main() {
    let mut routing_table = BTreeMap::from([
        (30, "gateway-c"),
        (10, "gateway-a"),
        (20, "gateway-b"),
    ]);

    routing_table.insert(15, "gateway-a-backup");

    // Iteration is guaranteed to visit keys in ascending `Ord` order (10, 15, 20, 30):
    for (metric, gateway) in &routing_table {
        println!("metric {metric:>2} -> {gateway}");
    }
    println!("Static empty len: {}", EMPTY_MAP.len());
}

metric 10 -> gateway-a
metric 15 -> gateway-a-backup
metric 20 -> gateway-b
metric 30 -> gateway-c
Static empty len: 0