When order matters more than speed
You're building a game leaderboard. New players join constantly. You need the list sorted by score. You also need to query "show me everyone ranked between 100 and 200". A Vec forces you to sort every time or binary search and shift elements. A HashMap gives you O(1) lookups but the order is random. You need a data structure that stays sorted automatically and lets you slice ranges without scanning everything. That's where BTreeMap and BTreeSet live.
The B-tree: a sorted structure that stays balanced
BTreeMap and BTreeSet use a B-tree internally. Think of a B-tree as a self-balancing filing cabinet. In a regular binary tree, adding items can create a lopsided shape where one side gets deep and slow. A B-tree prevents this. Each "drawer" (node) holds multiple items. When a drawer fills up, it splits and pushes a separator up to the parent. This keeps the tree short and wide. The result is predictable performance. Lookups, inserts, and deletes stay fast even with millions of items. The data stays sorted by key automatically. You get the speed of a hash map for lookups, plus the ability to ask "give me everything from A to Z" efficiently.
Here's the surprising part about Rust's implementation. The nodes in a BTreeMap are allocated as contiguous arrays, not as linked nodes with pointers. This gives you better cache locality than a pointer-heavy binary tree. When the CPU loads a node, it grabs a chunk of keys at once. The tree stays balanced, and the memory layout plays nice with modern hardware.
Minimal example
use std::collections::{BTreeMap, BTreeSet};
fn main() {
// BTreeMap keeps keys sorted. Insert order doesn't matter.
let mut scores = BTreeMap::new();
scores.insert("alice", 85);
scores.insert("bob", 92);
scores.insert("charlie", 78);
// Iterating yields keys in sorted order.
for (name, score) in &scores {
println!("{}: {}", name, score);
}
// BTreeSet stores unique values in sorted order.
let mut tags = BTreeSet::new();
tags.insert("rust");
tags.insert("web");
tags.insert("rust"); // Duplicate ignored.
println!("Tags: {:?}", tags);
}
Run this and you'll see the names printed alphabetically, regardless of insert order. The set prints ["rust", "web"]. The duplicate "rust" vanishes. The structure maintains the sort invariant on every mutation.
How it works under the hood
When you call insert, the tree finds the correct leaf node using binary search at each level. It places the key in the sorted position within that node. If the node overflows, it splits. The split promotes a key to the parent and creates a new sibling node. This propagation can bubble up to the root, potentially increasing the tree height by one. The height grows logarithmically with the number of elements. That's why operations stay fast.
BTreeSet is implemented as a BTreeMap<K, ()> under the hood. It uses the map's sorting and balancing logic but discards the value storage. This is a convention in Rust's standard library: sets are often maps with unit values. You get the same performance characteristics and API shape.
Every key type must implement the Ord trait. The tree needs to compare keys to decide where to route inserts and lookups. Ord requires a total ordering. Every pair of values must be comparable, and the comparison must be transitive. If a < b and b < c, then a < c. The tree breaks if the ordering is inconsistent.
Don't use BTreeMap if you don't need the sort. HashMap will thank you with speed.
Range queries: the superpower
The killer feature of BTreeMap is range queries. You can ask for a slice of the map efficiently. The tree finds the start point in O(log n) time and iterates through the matching items. This is much faster than scanning a Vec or rebuilding a sorted list.
use std::collections::BTreeMap;
use std::ops::Bound;
fn main() {
let mut inventory = BTreeMap::new();
inventory.insert("apple", 10);
inventory.insert("banana", 5);
inventory.insert("cherry", 8);
inventory.insert("date", 12);
// Find items from "banana" (inclusive) to "date" (exclusive).
// range() returns an iterator over the matching entries.
let range = inventory.range(
Bound::Included("banana"),
Bound::Excluded("date")
);
for (fruit, count) in range {
println!("{}: {}", fruit, count);
}
}
This prints banana and cherry. The range iterator doesn't copy the data. It borrows the entries. You can also use the shorthand syntax inventory.range("banana".."date") for the same effect. The range types support Included, Excluded, and Unbounded. You can query "everything after X" or "everything before Y" by mixing bounds.
Range queries are the superpower. If you aren't using ranges, question your choice.
Pitfalls and compiler errors
If you try to put a type that doesn't implement Ord into a BTreeMap, the compiler rejects you with E0277 (trait bound not satisfied). BTreeMap needs to compare keys to decide where to put them. PartialOrd isn't enough. The comparison must be total.
Watch out for f64. Floating point numbers have NaN, which breaks total ordering. NaN is not equal to itself, and comparisons involving NaN are undefined. You can't use f64 as a key directly. Wrap it in a type that handles NaN, or use a library like ordered-float. The standard library doesn't provide a wrapper for this. You'll need to bring your own solution.
Modifying the map while iterating breaks the borrow checker. You get E0502 (cannot borrow as mutable because it is also borrowed as immutable). The iterator holds an immutable borrow. You can't insert or remove while the iterator is alive. Collect the changes first, then apply them. Or use retain if you're filtering.
use std::collections::BTreeMap;
fn main() {
let mut scores = BTreeMap::new();
scores.insert("alice", 85);
scores.insert("bob", 92);
// Collect keys to remove first.
let to_remove: Vec<_> = scores.iter()
.filter(|(_, &score)| score < 90)
.map(|(name, _)| name.clone())
.collect();
// Now it's safe to remove.
for name in to_remove {
scores.remove(&name);
}
}
Wrap your floats. NaN breaks the tree.
Decision: BTreeMap vs HashMap vs Vec
Use BTreeMap when you need sorted keys or range queries. Use BTreeMap when you need deterministic iteration order across runs. Use BTreeMap when your keys are large and you want to avoid hashing overhead, though HashMap is usually faster for point lookups. Use BTreeSet when you need a sorted collection of unique values. Use BTreeSet when you need to find the nearest neighbor or split a collection at a pivot point.
Use HashMap when you only need point lookups and order doesn't matter. HashMap is generally faster for insert and lookup because it uses hashing instead of tree balancing. Reach for HashMap when performance is the priority and you don't care about iteration order.
Use Vec when you have a small number of items or you need random access by index. Sorting a Vec once is cheaper than maintaining a tree if you insert in bulk and query rarely. Use Vec when memory overhead matters; BTreeMap allocates nodes and has higher per-element cost.
Use the entry API for BTreeMap just like HashMap. It avoids double lookups when you need to insert or update based on existence. The convention is the same. The performance benefit is the same.
Range queries are the superpower. If you aren't using ranges, question your choice.