Binary Search Trees

While textbook Binary Search Trees (BSTs) store 1 key per heap-allocated node with left and right child pointers, pointer-per-node binary trees perform poorly on modern CPUs because every step down the tree chases a pointer to a separate cache line. Consequently, Rust's standard library provides BTreeMap<K, V> and BTreeSet<T>—cache-optimized B-Trees that store $B - 1$ to $2B - 1$ sorted keys contiguously inside each node (where $B = 6$, i.e., up to 11 keys per node).

1. Pointer-Based Binary Search Tree (1 Key per Node -> High Cache Miss Rate):
         [ 50 ]
        /      \        (Every comparison chases an 8-byte pointer to a random heap address)
    [ 20 ]    [ 80 ]

2. Rust `std::collections::BTreeMap` (B-Tree with up to 11 Keys per Contiguous Node):
         [ 20 | 35 | 50 | 65 | 80 | ... ]  (Fits in 1-2 CPU Cache Lines!)
        /     |    |    |    |     \
     [...]  [...] [...] [...] [...] [...]  (Shallow tree depth; $O(\log n)$ with tiny constant!)

When to Choose BTreeMap Over HashMap

Range Queries and Floor/Ceiling Lookups with BTreeMap::range

One of the most powerful capabilities of BTreeMap and BTreeSet is double-ended range iteration (map.range(bounds)). Because the returned Range iterator implements DoubleEndedIterator, you can find both the ceiling (smallest key $\ge x$) and floor (largest key $\le x$) in $O(\log n)$ time:

use std::collections::BTreeMap;
use std::ops::Bound::{Included, Excluded};

pub struct TimeSeriesIndex {
    events: BTreeMap<u64, &'static str>,
}

impl TimeSeriesIndex {
    pub fn new() -> Self {
        Self {
            events: BTreeMap::new(),
        }
    }

    pub fn insert(&mut self, timestamp: u64, label: &'static str) {
        self.events.insert(timestamp, label);
    }

    /// Returns all events in the inclusive window `[start_ts, end_ts]` in O(log n + k) time.
    pub fn query_window(&self, start_ts: u64, end_ts: u64) -> Vec<(u64, &'static str)> {
        self.events
            .range((Included(start_ts), Included(end_ts)))
            .map(|(&ts, &label)| (ts, label))
            .collect()
    }

    /// Finds the most recent event at or before `timestamp` (Floor query) in O(log n) time!
    pub fn floor_event(&self, timestamp: u64) -> Option<(u64, &'static str)> {
        self.events
            .range(..=timestamp)
            .next_back()
            .map(|(&ts, &label)| (ts, label))
    }

    /// Finds the next event strictly after `timestamp` (Strict Ceiling query) in O(log n) time!
    pub fn next_event_after(&self, timestamp: u64) -> Option<(u64, &'static str)> {
        self.events
            .range((Excluded(timestamp), std::ops::Bound::Unbounded))
            .next()
            .map(|(&ts, &label)| (ts, label))
    }
}

fn main() {
    let mut index = TimeSeriesIndex::new();
    index.insert(100, "boot");
    index.insert(250, "connected");
    index.insert(400, "checkpoint");
    index.insert(600, "shutdown");

    let window = index.query_window(200, 450);
    assert_eq!(window, vec![(250, "connected"), (400, "checkpoint")]);

    // Floor lookup for timestamp 300 finds (250, "connected"):
    assert_eq!(index.floor_event(300), Some((250, "connected")));
    // Strict ceiling lookup after 250 finds (400, "checkpoint"):
    assert_eq!(index.next_event_after(250), Some((400, "checkpoint")));

    println!("Window [200..=450]: {window:?}");
    println!("Floor at ts=300:    {:?}", index.floor_event(300));
}

Window [200..=450]: [(250, "connected"), (400, "checkpoint")]
Floor at ts=300:    Some((250, "connected"))