BTreeMap y BTreeSet: mapas ordenados y consultas por rango

El HashMap es rapidísimo, pero paga ese precio renunciando a algo: el orden. Sus claves están esparcidas por buckets según su huella, así que preguntar “dame las claves entre 100 y 200” o “cuál es la menor” le resulta imposible sin recorrerlo entero. BTreeMap<K, V> hace la apuesta contraria: mantiene las claves siempre ordenadas, aceptando un coste logarítmico por operación a cambio de tres superpoderes que el hash no puede dar —iteración en orden, mínimo y máximo instantáneos, y consultas por rango—. Y lo hace sobre un B-tree, una estructura pensada para la memoria real, no para la pizarra teórica.

Un mapa que mantiene el orden

Un BTreeMap se usa casi igual que un HashMap —insert, get, remove, entry— pero con una diferencia visible en cuanto lo recorres: la iteración sale en orden ascendente de clave, siempre, de forma determinista. El requisito sobre la clave también cambia: ya no es Hash + Eq, sino K: Ord, porque para colocar cada clave en su sitio el árbol necesita compararlas, no resumirlas en una huella.

use std::collections::BTreeMap;

fn main() {
    let mut m = BTreeMap::new();
    m.insert(30, "treinta");
    m.insert(10, "diez");
    m.insert(20, "veinte");

    for (k, v) in &m {
        println!("{k}: {v}");   // 10, 20, 30 SIEMPRE en ese orden
    }
    println!("{:?}", m.get(&20)); // Some("veinte"), en O(log n)
}

Pese a su nombre, un B-tree no es un árbol binario. Cada nodo almacena un pequeño arreglo contiguo de claves ordenadas —en la implementación de std, hasta once por nodo— y ramifica en muchos hijos, no en dos. Esa anchura mantiene el árbol muy bajo (pocos saltos de puntero desde la raíz a una hoja) y hace que cada nodo llene líneas de caché enteras, en lugar de dispersar un dato por nodo como haría un árbol binario clásico. El resultado es una estructura logarítmica que, además, respeta la memoria real de la máquina.

flowchart TB
root[Nodo raiz claves 20 y 40] --> a[Hoja 5 10 15]
root --> b[Hoja 25 30 35]
root --> c[Hoja 45 50 55]
style root fill:#cba6f7,color:#11111b
style a fill:#89b4fa,color:#11111b
style b fill:#89b4fa,color:#11111b
style c fill:#89b4fa,color:#11111b

Rangos: la operación que HashMap no tiene

Aquí está la razón número uno para elegir BTreeMap. Como las claves están ordenadas, el mapa puede darte todas las que caen en un intervalo navegando directo al inicio del rango y recorriendo desde allí, en O(log n + k) para k resultados. Un HashMap no puede ni acercarse: tendría que examinar cada entrada.

use std::collections::BTreeMap;

fn main() {
    let mut notas = BTreeMap::new();
    for (k, v) in [(50, "E"), (65, "D"), (72, "C"), (88, "B"), (95, "A")] {
        notas.insert(k, v);
    }

    // Todas las claves en el intervalo semiabierto 65..90:
    for (nota, letra) in notas.range(65..90) {
        println!("{nota} -> {letra}");   // 65, 72, 88 en orden
    }

    // Extremos en O(log n), sin recorrer nada:
    println!("{:?}", notas.first_key_value()); // Some((50, "E"))
    println!("{:?}", notas.last_key_value());  // Some((95, "A"))
    let peor = notas.pop_first();               // saca y devuelve el minimo
    println!("{:?}", peor);                      // Some((50, "E"))
}

range acepta los mismos rangos semiabiertos que ya conoces —a..b, a..=b, ..b, a..— y devuelve un iterador ordenado. Junto a él, first_key_value, last_key_value, pop_first y pop_last te dan el mínimo y el máximo, para leer o para extraer, todo en tiempo logarítmico. Estas operaciones son la definición misma de por qué existe un mapa ordenado: consultas de vecindad y de extremo que en un hash costarían recorrerlo entero.

BTreeMap frente a HashMap: cuándo cada uno

La elección no es de gusto, es de perfil de acceso. Puestos lado a lado:

La regla práctica se lee sola. Elige HashMap cuando solo haces búsquedas puntuales y el orden te da igual: es más rápido en el caso común. Elige BTreeMap cuando necesites cualquier cosa que dependa del orden —iterar ordenado, consultar rangos, sacar el menor o el mayor, o simplemente querer una iteración reproducible entre ejecuciones—. Hay un matiz de rendimiento que sorprende: para mapas pequeños, el BTreeMap a veces gana incluso en búsqueda puntual, porque O(log n) sobre unas decenas de claves contiguas y sin hashear puede batir el coste fijo de calcular una huella SipHash. Como siempre, el asintótico no es toda la historia; lo veremos en la lección 19.5.

BTreeSet: el conjunto ordenado

Del mismo modo que HashSet es un HashMap sin valores, BTreeSet<T> es un BTreeMap<T, ()>: un conjunto que guarda elementos únicos y ordenados, con T: Ord. Hereda las tres ventajas del mapa —iteración ordenada, extremos rápidos y, sobre todo, range— además de las operaciones de conjunto (union, intersection, difference).

use std::collections::BTreeSet;

fn main() {
    let mut s: BTreeSet<i32> = [40, 10, 30, 20, 10].into_iter().collect();
    // Los duplicados se funden y queda ordenado: {10, 20, 30, 40}
    println!("{:?}", s);
    println!("min {:?} max {:?}", s.first(), s.last()); // Some(10) Some(40)

    for x in s.range(15..35) {   // elementos en un intervalo, en orden
        println!("{x}");          // 20, 30
    }
    s.insert(25);
}

Cuando quieras un conjunto pero necesites recorrerlo ordenado o consultarlo por rango —fechas dentro de una ventana, identificadores en un intervalo—, BTreeSet es la herramienta; si solo te importa la pertenencia rápida, quédate con HashSet, que veremos en la próxima lección.