Think about the difference between a pile of business cards and a physical address book. If you have a pile of cards, you can find a specific person quickly if you have a magic index (that's your HashMap), but if I ask you to "show me everyone whose last name starts with the letter M through P," you're stuck. You'd have to look at every single card in the pile.

An address book, however, is sorted. Because the entries are ordered, you don't just find one person; you can find a range of people. You flip to the 'M' section and stop when you hit 'Q'. That's exactly what BTreeMap does for you in Rust. It keeps your keys in a sorted order, allowing you to perform range queries that would be impossibly slow with a hash map.

When to ditch the HashMap

I'll be honest: 90% of the time, HashMap is your go-to. It's faster for basic insertions and lookups. But the moment you need your data to stay sorted, or you need to find "all keys between X and Y," BTreeMap is the only way to go. It's implemented as a B-Tree, which is specifically designed to be cache-friendly and efficient for these kinds of ordered operations.

use std::collections::BTreeMap;

fn main() {
    let mut scores = BTreeMap::new();
    
    // We're inserting scores for players. 
    // Note that BTreeMap will sort these by the key (the score).
    scores.insert(100, "Alice");
    scores.insert(50, "Bob");
    scores.insert(150, "Charlie");
    scores.insert(75, "Dave");

    // When we iterate, they come out in order of the key: 50, 75, 100, 150.
    for (score, name) in &scores {
        println!("{}: {}", score, name);
    }
}

The "Ord" Requirement

You'll notice that BTreeMap has a stricter requirement for its keys than HashMap does. While a HashMap key just needs to be Hash + Eq, a BTreeMap key must implement Ord. This is because the map needs to know exactly how to compare two keys to decide which one comes first. If you try to use a custom struct as a key without implementing Ord and PartialOrd, the compiler will stop you right there.

Slicing your data with Range Queries

This is where the real power lies. The .range() method allows you to pull out a slice of the map. You can use standard Rust range syntax (like a..b or a..=b) to define exactly what you're looking for. I find this incredibly useful for things like time-series data or any scenario where you have a "start" and "end" boundary.

use std::collections::BTreeMap;

fn main() {
    let mut events = BTreeMap::new();
    events.insert(10, "System Boot");
    events.insert(20, "Network Up");
    events.insert(30, "User Login");
    events.insert(40, "File Opened");
    events.insert(50, "System Shutdown");

    // Let's say we only care about events that happened between time 15 and 35.
    println!("Events in window 15..35:");
    for (time, desc) in events.range(15..35) {
        println!("At time {}: {}", time, desc);
    }
    // This will print "Network Up" and "User Login".
}

One little tip: .range() returns an iterator. It doesn't clone the data or create a new map; it just gives you a window into the existing one. This makes it extremely efficient, even if your map contains millions of entries.

📋 Practical Task

Build a Versioned Document History

You are building a simple version control system for a text document. Each version is identified by a u32 version number and contains a string representing the document's content at that point in time.

Your goal:

• Create a BTreeMap where the key is the version number (u32) and the value is the content (String).
• Insert at least five different versions of the document, but insert them out of order (e.g., insert version 5, then 1, then 3).
• Implement a function get_version_range(map: &BTreeMap<u32, String>, start: u32, end: u32) that prints all document versions between the start and end values (inclusive).

Testing your logic: If you insert versions 1 through 5, calling get_version_range with 2 and 4 should print the content for versions 2, 3, and 4 in the correct numerical order, regardless of the order you inserted them into the map.