BTreeMap & BTreeSet

BTreeMap<K, V> and BTreeSet<T> keep their contents sorted by key. They are implemented as B-trees (wide, cache-friendly trees) rather than red-black trees. Every operation is O(log n).

Choose them over HashMap/HashSet when you need:

iteration in key order, or deterministic output,
the smallest or largest key,
range queries: "all keys between A and B", "the first key after X",
keys that implement Ord but not Hash.

Operation	Rust `BTreeMap` / `BTreeSet`
Smallest and largest entry	`first_key_value()`, `last_key_value()`
Remove the smallest entry	`pop_first()`
Entries between two keys	`range(a..b)`
Entries before or after a key	`range(..x)`, `range(x..)`
Greatest key at or below `x` (floor)	`range(..=x).next_back()`
Least key at or above `x` (ceiling)	`range(x..).next()`
Descending iteration	`iter().rev()`

1. Keys come out sorted

Rust

use std::collections::BTreeMap;

fn main() {
    let mut population: BTreeMap<&str, u32> = BTreeMap::new();
    population.insert("Porto", 232_000);
    population.insert("Lisbon", 545_000);
    population.insert("Braga", 193_000);
    population.insert("Faro", 67_000);
    for (city, people) in &population {
        println!("{city:<7} {people}");
    }
}

Output

Braga   193000
Faro    67000
Lisbon  545000
Porto   232000

Unlike HashMap, the output is the same on every run: sorted by key.

2. The same API as `HashMap`

insert, get, get_mut, remove, contains_key, entry, retain, and extend all work the same way.

Rust

use std::collections::BTreeMap;

fn main() {
    let mut word_counts: BTreeMap<&str, usize> = BTreeMap::new();
    for w in "b a c a b a".split(' ') {
        *word_counts.entry(w).or_insert(0) += 1;
    }
    println!("{:?}", word_counts);
    word_counts.remove("c");
    println!("{:?} {}", word_counts.get("a"), word_counts.contains_key("c"));
}

Output

{"a": 3, "b": 2, "c": 1}
Some(3) false

Printing a BTreeMap with {:?} shows the entries in key order, which is perfect for tests and logs.

3. First and last entries

Rust

use std::collections::BTreeMap;

fn main() {
    let scores = BTreeMap::from([(71, "ben"), (92, "ana"), (85, "cy"), (64, "dee")]);
    println!("lowest:  {:?}", scores.first_key_value());
    println!("highest: {:?}", scores.last_key_value());
}

Output

lowest:  Some((64, "dee"))
highest: Some((92, "ana"))

4. `pop_first` and `pop_last`

These remove and return the smallest or largest entry, which makes a BTreeMap a priority queue that can also be searched and iterated in order.

Rust

use std::collections::BTreeMap;

fn main() {
    let mut deadlines = BTreeMap::from([(1_700, "report"), (900, "standup"), (1_300, "review")]);
    while let Some((time, task)) = deadlines.pop_first() {
        println!("{time:>5}: {task}");
    }
}

Output

  900: standup
 1300: review
 1700: report

5. Iterating in reverse

Rust

use std::collections::BTreeMap;

fn main() {
    let releases = BTreeMap::from([(2021, "edition 2021"), (2015, "1.0"), (2024, "edition 2024"), (2018, "edition 2018")]);
    let newest_first: Vec<(&i32, &&str)> = releases.iter().rev().collect();
    println!("{:?}", newest_first);
    let latest_two: Vec<&&str> = releases.values().rev().take(2).collect();
    println!("{:?}", latest_two);
}

Output

[(2024, "edition 2024"), (2021, "edition 2021"), (2018, "edition 2018"), (2015, "1.0")]
["edition 2024", "edition 2021"]

6. Range queries

range returns the entries whose keys fall in a range, in order, without scanning the whole map.

Rust

use std::collections::BTreeMap;

fn main() {
    let mut events: BTreeMap<u32, &str> = BTreeMap::new();
    for (t, e) in [(100, "boot"), (240, "login"), (310, "click"), (480, "purchase"), (900, "logout")] {
        events.insert(t, e);
    }
    println!("200..500:  {:?}", events.range(200..500).collect::<Vec<_>>());
    println!("..=310:    {:?}", events.range(..=310).map(|(_, e)| *e).collect::<Vec<_>>());
    println!("480..:     {:?}", events.range(480..).map(|(_, e)| *e).collect::<Vec<_>>());
}

Output

200..500:  [(240, "login"), (310, "click"), (480, "purchase")]
..=310:    ["boot", "login", "click"]
480..:     ["purchase", "logout"]

7. Floor and ceiling lookups

"The last key at or before X" and "the first key at or after X" come from a range plus next_back or next.

Rust

use std::collections::BTreeMap;

fn main() {
    let tax_brackets = BTreeMap::from([(0, 0), (12_000, 10), (50_000, 20), (150_000, 40)]);
    for income in [8_000, 12_000, 75_000, 400_000] {
        let (&floor, &rate) = tax_brackets.range(..=income).next_back().unwrap();
        println!("income {income:>7}: bracket from {floor} at {rate}%");
    }

    let departures = BTreeMap::from([(810, "08:10"), (905, "09:05"), (1140, "11:40")]);
    let now = 830;
    match departures.range(now..).next() {
        Some((_, time)) => println!("next train at {time}"),
        None => println!("no more trains today"),
    }
}

Output

income    8000: bracket from 0 at 0%
income   12000: bracket from 12000 at 10%
income   75000: bracket from 50000 at 20%
income  400000: bracket from 150000 at 40%
next train at 09:05

8. Custom key types need `Ord`

A BTreeMap compares keys, so keys must implement Ord (not Hash). Derived Ord compares fields in order.

Rust

use std::collections::BTreeMap;

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Date {
    year: u16,
    month: u8,
    day: u8,
}

fn main() {
    let mut sales: BTreeMap<Date, u32> = BTreeMap::new();
    sales.insert(Date { year: 2026, month: 9, day: 27 }, 410);
    sales.insert(Date { year: 2025, month: 12, day: 31 }, 980);
    sales.insert(Date { year: 2026, month: 1, day: 15 }, 220);
    for (d, amount) in &sales {
        println!("{}-{:02}-{:02}: {amount}", d.year, d.month, d.day);
    }
    let from = Date { year: 2026, month: 1, day: 1 };
    let this_year: u32 = sales.range(from..).map(|(_, v)| v).sum();
    println!("2026 so far: {this_year}");
}

Output

2025-12-31: 980
2026-01-15: 220
2026-09-27: 410
2026 so far: 630

9. Sorting in reverse with `Reverse` keys

Wrap keys in std::cmp::Reverse to store them in descending order.

Rust

use std::cmp::Reverse;
use std::collections::BTreeMap;

fn main() {
    let mut leaderboard: BTreeMap<Reverse<u32>, Vec<&str>> = BTreeMap::new();
    for (name, score) in [("ana", 980), ("ben", 1_200), ("cy", 980), ("dee", 750)] {
        leaderboard.entry(Reverse(score)).or_default().push(name);
    }
    for (rank, (Reverse(score), names)) in leaderboard.iter().enumerate() {
        println!("#{} {score}: {}", rank + 1, names.join(", "));
    }
}

Output

#1 1200: ben
#2 980: ana, cy
#3 750: dee

10. `split_off` and `append`

split_off(&k) moves every entry with key >= k into a new map.

Rust

use std::collections::BTreeMap;

fn main() {
    let mut log: BTreeMap<u32, &str> = (1..=6).map(|i| (i * 100, "entry")).collect();
    let recent = log.split_off(&400);
    println!("archived: {:?}", log.keys().collect::<Vec<_>>());
    println!("recent:   {:?}", recent.keys().collect::<Vec<_>>());

    let mut all = log;
    let mut more = recent;
    all.append(&mut more);
    println!("merged:   {:?}, other empty: {}", all.keys().collect::<Vec<_>>(), more.is_empty());
}

Output

archived: [100, 200, 300]
recent:   [400, 500, 600]
merged:   [100, 200, 300, 400, 500, 600], other empty: true

11. Deterministic output for configuration and reports

Because iteration is ordered, BTreeMap is the right choice when output must be stable, such as generated config files, snapshots in tests, or signatures over key-value data.

Rust

use std::collections::BTreeMap;

fn to_env_file(settings: &BTreeMap<&str, String>) -> String {
    settings.iter().map(|(k, v)| format!("{}={}", k.to_uppercase(), v)).collect::<Vec<_>>().join("\n")
}

fn main() {
    let mut settings = BTreeMap::new();
    settings.insert("port", String::from("8080"));
    settings.insert("database_url", String::from("postgres://localhost/app"));
    settings.insert("log_level", String::from("info"));
    println!("{}", to_env_file(&settings));
}

Output

DATABASE_URL=postgres://localhost/app
LOG_LEVEL=info
PORT=8080

12. `BTreeSet`: sorted unique values

Rust

use std::collections::BTreeSet;

fn main() {
    let mut versions: BTreeSet<(u32, u32, u32)> = BTreeSet::new();
    for v in [(1, 2, 0), (1, 10, 3), (1, 2, 0), (0, 9, 9), (2, 0, 0)] {
        versions.insert(v);
    }
    println!("{:?}", versions);
    println!("oldest {:?}, newest {:?}", versions.first(), versions.last());
    println!("1.x releases: {}", versions.range((1, 0, 0)..(2, 0, 0)).count());
}

Output

{(0, 9, 9), (1, 2, 0), (1, 10, 3), (2, 0, 0)}
oldest Some((0, 9, 9)), newest Some((2, 0, 0))
1.x releases: 2

13. Set operations in order

BTreeSet has the same set algebra as HashSet, but the results come out sorted.

Rust

use std::collections::BTreeSet;

fn main() {
    let required: BTreeSet<&str> = BTreeSet::from(["auth", "db", "cache", "queue"]);
    let running: BTreeSet<&str> = BTreeSet::from(["db", "auth", "search"]);
    println!("missing:    {:?}", required.difference(&running).collect::<Vec<_>>());
    println!("unexpected: {:?}", running.difference(&required).collect::<Vec<_>>());
    println!("all:        {:?}", required.union(&running).collect::<Vec<_>>());
}

Output

missing:    ["cache", "queue"]
unexpected: ["search"]
all:        ["auth", "cache", "db", "queue", "search"]

14. `BTreeSet` range queries

Rust

use std::collections::BTreeSet;

fn main() {
    let busy_minutes: BTreeSet<u32> = [540, 541, 542, 600, 601, 780].into_iter().collect();
    let between_9_and_10: Vec<&u32> = busy_minutes.range(540..600).collect();
    println!("{:?}", between_9_and_10);
    let next_busy_after_noon = busy_minutes.range(720..).next();
    println!("{:?}", next_busy_after_noon);
}

Output

[540, 541, 542]
Some(780)

15. When to use which map

Need	`HashMap`	`BTreeMap`
Average lookup	O(1)	O(log n)
Iteration order	Unspecified	Sorted by key
Key requirements	`Eq + Hash`	`Ord`
Range queries, min/max	No	Yes
Typical use	Caches, indexes, counters	Time series, schedules, ordered reports

Rust

use std::collections::{BTreeMap, HashMap};

fn main() {
    let pairs = [("c", 3), ("a", 1), ("b", 2)];
    let hash: HashMap<&str, i32> = pairs.into_iter().collect();
    let tree: BTreeMap<&str, i32> = pairs.into_iter().collect();
    println!("same contents: {}", hash.len() == tree.len() && tree.iter().all(|(k, v)| hash.get(k) == Some(v)));
    println!("ordered: {:?}", tree);
}

Output

same contents: true
ordered: {"a": 1, "b": 2, "c": 3}

16. Realistic example: an order book

A trading order book keeps price levels sorted. The best bid is the highest buy price and the best ask is the lowest sell price.

Rust

use std::collections::BTreeMap;

struct OrderBook {
    bids: BTreeMap<u32, u32>, // price in cents -> quantity
    asks: BTreeMap<u32, u32>,
}

impl OrderBook {
    fn add(side: &mut BTreeMap<u32, u32>, price: u32, qty: u32) {
        *side.entry(price).or_insert(0) += qty;
    }

    fn best_bid(&self) -> Option<(&u32, &u32)> {
        self.bids.last_key_value()
    }

    fn best_ask(&self) -> Option<(&u32, &u32)> {
        self.asks.first_key_value()
    }

    fn spread(&self) -> Option<u32> {
        Some(self.best_ask()?.0 - self.best_bid()?.0)
    }
}

fn main() {
    let mut book = OrderBook { bids: BTreeMap::new(), asks: BTreeMap::new() };
    OrderBook::add(&mut book.bids, 10_050, 200);
    OrderBook::add(&mut book.bids, 10_045, 500);
    OrderBook::add(&mut book.bids, 10_050, 100);
    OrderBook::add(&mut book.asks, 10_060, 300);
    OrderBook::add(&mut book.asks, 10_075, 50);
    println!("best bid {:?}, best ask {:?}, spread {:?}", book.best_bid(), book.best_ask(), book.spread());
    println!("asks up to 100.70: {:?}", book.asks.range(..=10_070).collect::<Vec<_>>());
}

Output

best bid Some((10050, 300)), best ask Some((10060, 300)), spread Some(10)
asks up to 100.70: [(10060, 300)]

17. Realistic example: a timer wheel / event scheduler

Events are stored by due time. Each tick pops everything that's due, in order.

Rust

use std::collections::BTreeMap;

struct Scheduler {
    queue: BTreeMap<u64, Vec<String>>,
}

impl Scheduler {
    fn schedule(&mut self, at_ms: u64, job: &str) {
        self.queue.entry(at_ms).or_default().push(job.to_string());
    }

    fn run_due(&mut self, now_ms: u64) -> Vec<String> {
        let later = self.queue.split_off(&(now_ms + 1));
        let due = std::mem::replace(&mut self.queue, later);
        due.into_values().flatten().collect()
    }
}

fn main() {
    let mut s = Scheduler { queue: BTreeMap::new() };
    s.schedule(500, "send reminder");
    s.schedule(100, "refresh token");
    s.schedule(500, "flush metrics");
    s.schedule(2_000, "nightly cleanup");
    for now in [50, 600, 1_000, 3_000] {
        println!("t={now:>4}: {:?}", s.run_due(now));
    }
}

Output

t=  50: []
t= 600: ["refresh token", "send reminder", "flush metrics"]
t=1000: []
t=3000: ["nightly cleanup"]

18. Realistic example: downsampling a time series

Group readings into 1-minute buckets and average each bucket, in time order.

Rust

use std::collections::BTreeMap;

fn main() {
    let readings = [(5, 20.0), (42, 22.0), (61, 25.0), (65, 27.0), (130, 24.0), (170, 26.0), (175, 28.0)];
    let mut buckets: BTreeMap<u64, (f64, u32)> = BTreeMap::new();
    for (second, value) in readings {
        let entry = buckets.entry(second / 60 * 60).or_insert((0.0, 0));
        entry.0 += value;
        entry.1 += 1;
    }
    for (start, (sum, n)) in &buckets {
        println!("{:02}:{:02} avg {:.1} ({n} readings)", start / 60, start % 60, sum / *n as f64);
    }
}

Output

00:00 avg 21.0 (2 readings)
01:00 avg 26.0 (2 readings)
02:00 avg 26.0 (3 readings)

19. Realistic example: finding the IP range an address belongs to

Map each range's start address to its end and owner. The floor lookup finds the only candidate range in O(log n).

Rust

use std::collections::BTreeMap;

fn ip(a: u8, b: u8, c: u8, d: u8) -> u32 {
    u32::from_be_bytes([a, b, c, d])
}

fn main() {
    let mut ranges: BTreeMap<u32, (u32, &str)> = BTreeMap::new();
    ranges.insert(ip(10, 0, 0, 0), (ip(10, 0, 255, 255), "office"));
    ranges.insert(ip(10, 1, 0, 0), (ip(10, 1, 0, 255), "vpn"));
    ranges.insert(ip(192, 168, 1, 0), (ip(192, 168, 1, 255), "lab"));

    let lookup = |addr: u32| -> &str {
        match ranges.range(..=addr).next_back() {
            Some((_, &(end, owner))) if addr <= end => owner,
            _ => "unknown",
        }
    };
    for (label, addr) in [("10.0.3.7", ip(10, 0, 3, 7)), ("10.1.0.200", ip(10, 1, 0, 200)), ("10.1.5.5", ip(10, 1, 5, 5)), ("192.168.1.42", ip(192, 168, 1, 42))] {
        println!("{label:<13} -> {}", lookup(addr));
    }
}

Output

10.0.3.7      -> office
10.1.0.200    -> vpn
10.1.5.5      -> unknown
192.168.1.42  -> lab

u32::from_be_bytes builds a number from four bytes in network (big-endian) order, which makes IPv4 addresses comparable as integers.

20. Realistic example: autocomplete with a prefix range

In a sorted set, all words with a given prefix are next to each other. A range starting at the prefix finds them without scanning everything.

Rust

use std::collections::BTreeSet;

fn complete<'a>(words: &'a BTreeSet<String>, prefix: &str, limit: usize) -> Vec<&'a str> {
    words
        .range(prefix.to_string()..)
        .take_while(|w| w.starts_with(prefix))
        .take(limit)
        .map(|w| w.as_str())
        .collect()
}

fn main() {
    let words: BTreeSet<String> = ["rust", "rustc", "rustup", "ruby", "react", "rustfmt", "run"].iter().map(|s| s.to_string()).collect();
    println!("{:?}", complete(&words, "rust", 3));
    println!("{:?}", complete(&words, "ru", 10));
    println!("{:?}", complete(&words, "go", 10));
}

Output

["rust", "rustc", "rustfmt"]
["ruby", "run", "rust", "rustc", "rustfmt", "rustup"]
[]

21. Realistic example: free meeting slots

Busy intervals in a BTreeMap<start, end>. Walking them in order finds the gaps.

Rust

use std::collections::BTreeMap;

fn free_slots(busy: &BTreeMap<u32, u32>, day_start: u32, day_end: u32, min_len: u32) -> Vec<(u32, u32)> {
    let mut free = Vec::new();
    let mut cursor = day_start;
    for (&start, &end) in busy {
        if start > cursor && start - cursor >= min_len {
            free.push((cursor, start));
        }
        cursor = cursor.max(end);
    }
    if day_end > cursor && day_end - cursor >= min_len {
        free.push((cursor, day_end));
    }
    free
}

fn fmt(m: u32) -> String {
    format!("{:02}:{:02}", m / 60, m % 60)
}

fn main() {
    let busy = BTreeMap::from([(9 * 60, 10 * 60), (10 * 60 + 30, 11 * 60), (13 * 60, 14 * 60 + 30)]);
    for (s, e) in free_slots(&busy, 9 * 60, 17 * 60, 30) {
        println!("free {} - {}", fmt(s), fmt(e));
    }
}

Output

free 10:00 - 10:30
free 11:00 - 13:00
free 14:30 - 17:00

22. Realistic example: the latest version satisfying a constraint

Rust

use std::collections::BTreeMap;

fn main() {
    let mut registry: BTreeMap<(u32, u32, u32), &str> = BTreeMap::new();
    for (v, date) in [((1, 0, 0), "2025-01"), ((1, 4, 2), "2025-06"), ((1, 9, 0), "2026-02"), ((2, 0, 0), "2026-05"), ((2, 1, 1), "2026-09")] {
        registry.insert(v, date);
    }
    // "^1.2": at least 1.2.0, below 2.0.0
    let best = registry.range((1, 2, 0)..(2, 0, 0)).next_back();
    println!("^1.2 resolves to {:?}", best);
    let newest = registry.last_key_value();
    println!("latest is {:?}", newest);
}

Output

^1.2 resolves to Some(((1, 9, 0), "2026-02"))
latest is Some(((2, 1, 1), "2026-09"))

23. Realistic example: a sliding-window counter

Count requests in the last 60 seconds by removing old timestamps from the front of a sorted map.

Rust

use std::collections::BTreeMap;

struct WindowCounter {
    hits: BTreeMap<u64, u32>, // second -> count
    window: u64,
}

impl WindowCounter {
    fn hit(&mut self, now: u64) -> u32 {
        *self.hits.entry(now).or_insert(0) += 1;
        if let Some(cutoff) = now.checked_sub(self.window) {
            self.hits = self.hits.split_off(&(cutoff + 1)); // keep only seconds after the cutoff
        }
        self.hits.values().sum()
    }
}

fn main() {
    let mut c = WindowCounter { hits: BTreeMap::new(), window: 60 };
    for t in [0, 10, 10, 30, 65, 70, 125] {
        println!("t={t:>3}s requests in last minute: {}", c.hit(t));
    }
}

Output

t=  0s requests in last minute: 1
t= 10s requests in last minute: 2
t= 10s requests in last minute: 3
t= 30s requests in last minute: 4
t= 65s requests in last minute: 4
t= 70s requests in last minute: 3
t=125s requests in last minute: 2

24. Realistic example: ranking with a sorted set of tuples

A BTreeSet<(score, name)> keeps entries sorted by score, with names breaking ties. Updating a score means removing the old tuple and inserting the new one.

Rust

use std::collections::{BTreeSet, HashMap};

struct Ranking {
    by_score: BTreeSet<(u32, String)>,
    current: HashMap<String, u32>,
}

impl Ranking {
    fn set(&mut self, name: &str, score: u32) {
        if let Some(old) = self.current.insert(name.to_string(), score) {
            self.by_score.remove(&(old, name.to_string()));
        }
        self.by_score.insert((score, name.to_string()));
    }

    fn top(&self, n: usize) -> Vec<(u32, &str)> {
        self.by_score.iter().rev().take(n).map(|(s, name)| (*s, name.as_str())).collect()
    }
}

fn main() {
    let mut r = Ranking { by_score: BTreeSet::new(), current: HashMap::new() };
    r.set("ana", 50);
    r.set("ben", 80);
    r.set("cy", 65);
    println!("{:?}", r.top(2));
    r.set("ana", 95);
    println!("{:?}", r.top(3));
}

Output

[(80, "ben"), (65, "cy")]
[(95, "ana"), (80, "ben"), (65, "cy")]

25. Realistic example: a histogram in sorted order

Rust

use std::collections::BTreeMap;

fn main() {
    let response_times_ms = [12, 45, 18, 230, 51, 7, 88, 44, 120, 15, 49, 31];
    let mut buckets: BTreeMap<u32, u32> = BTreeMap::new();
    for t in response_times_ms {
        let bucket = match t {
            0..=24 => 25,
            25..=49 => 50,
            50..=99 => 100,
            _ => 250,
        };
        *buckets.entry(bucket).or_insert(0) += 1;
    }
    let mut prev = 0;
    for (upper, count) in &buckets {
        println!("{:>3}-{:<3}ms {}", prev, upper - 1, "#".repeat(*count as usize));
        prev = *upper;
    }
}

Output

  0-24 ms ####
 25-49 ms ####
 50-99 ms ##
100-249ms ##

Summary

BTreeMap and BTreeSet are sorted by key, with O(log n) operations. Keys need Ord, not Hash.
They share the HashMap/HashSet API, plus first_key_value, last_key_value, pop_first, pop_last, range, split_off, and ordered iteration in both directions.
Floor and ceiling: range(..=x).next_back() and range(x..).next().
Use them for deterministic output, time series, schedules, order books, interval lookups, and prefix search.
Use Reverse(key) for descending order.

Next: VecDeque & BinaryHeap.

1. Keys come out sorted

2. The same API as HashMap

3. First and last entries

4. pop_first and pop_last

5. Iterating in reverse

6. Range queries

7. Floor and ceiling lookups

8. Custom key types need Ord

9. Sorting in reverse with Reverse keys

10. split_off and append

11. Deterministic output for configuration and reports

12. BTreeSet: sorted unique values

13. Set operations in order

14. BTreeSet range queries

15. When to use which map

16. Realistic example: an order book

17. Realistic example: a timer wheel / event scheduler

18. Realistic example: downsampling a time series

19. Realistic example: finding the IP range an address belongs to

20. Realistic example: autocomplete with a prefix range

21. Realistic example: free meeting slots

22. Realistic example: the latest version satisfying a constraint

23. Realistic example: a sliding-window counter

24. Realistic example: ranking with a sorted set of tuples

25. Realistic example: a histogram in sorted order

Summary

2. The same API as `HashMap`

4. `pop_first` and `pop_last`

8. Custom key types need `Ord`

9. Sorting in reverse with `Reverse` keys

10. `split_off` and `append`

12. `BTreeSet`: sorted unique values

14. `BTreeSet` range queries