BTreeSet e BTreeMap: B-Tree em Rust | Rust Brasil

Introdução

A B-Tree (Árvore B) é uma árvore de busca generalizada onde cada nó pode conter múltiplas chaves e ter múltiplos filhos. Inventada por Rudolf Bayer e Edward McCreight em 1970 na Boeing, ela foi projetada para minimizar o número de acessos a disco, sendo a estrutura de dados padrão para sistemas de arquivos e bancos de dados.

A B-Tree é especialmente relevante em Rust porque BTreeMap e BTreeSet — as coleções ordenadas da biblioteca padrão — são implementadas como B-Trees. Diferentemente de árvores binárias, a B-Tree agrupa muitas chaves em cada nó, aproveitando melhor a localidade de cache da CPU e reduzindo o número de indireções de ponteiros.

Conceito e Teoria

Estrutura de uma B-Tree

Uma B-Tree de ordem t (grau mínimo) tem as seguintes propriedades:

Cada nó tem no máximo 2t - 1 chaves.
Cada nó (exceto a raiz) tem no mínimo t - 1 chaves.
A raiz tem no mínimo 1 chave (se não estiver vazia).
Um nó com k chaves tem exatamente k + 1 filhos (se não for folha).
Todas as folhas estão no mesmo nível.
As chaves dentro de cada nó estão ordenadas.

    B-Tree de ordem t=2 (cada nó tem 1 a 3 chaves):

                    [16]
                   /    \
          [3, 7]         [20, 25, 30]
         /  |  \        /   |    |   \
       [1,2][4,5][8,9] [17,18][21,23][26,28][31,35]

    Propriedades verificadas:
    - Todas as folhas no mesmo nível (nível 2)         ✓
    - Nós internos: 1 a 3 chaves                       ✓
    - Nó com k chaves tem k+1 filhos                   ✓
    - Chaves ordenadas dentro de cada nó                ✓

Busca na B-Tree

A busca é semelhante à BST, mas em cada nó procuramos a posição correta entre múltiplas chaves:

    Buscar a chave 23:

    Nó raiz [16]:
        23 > 16 → vai para filho direito

    Nó [20, 25, 30]:
        23 > 20 e 23 < 25 → vai para filho entre 20 e 25

    Nó folha [21, 23]:
        23 encontrado! ✓

Inserção com Splitting

Quando um nó está cheio (2t - 1 chaves), ele é dividido (split) antes da inserção:

    Inserir 15 em uma B-Tree de ordem t=2:

    Antes (nó cheio):
                [10]
               /    \
          [3, 7]   [12, 14, 16]  ← Cheio! (3 chaves = 2t-1)

    Passo 1: Split do nó [12, 14, 16]
    A chave mediana (14) sobe para o pai:

                [10, 14]
               /   |    \
          [3, 7] [12]  [16]

    Passo 2: Inserir 15 no nó adequado:
    15 > 14 → vai para [16]

                [10, 14]
               /   |    \
          [3, 7] [12]  [15, 16]

    Resultado final: árvore continua balanceada! ✓

Por que B-Trees são Cache-Friendly?

    Árvore Binária (muitos saltos de ponteiro):

    [A] → ptr → [B] → ptr → [C] → ptr → [D]
     ↑           ↑           ↑           ↑
    Cache miss  Cache miss  Cache miss  Cache miss

    B-Tree (dados agrupados no mesmo bloco):

    [A, B, C, D, E, F, G]  ← Todo o nó em um bloco de memória
     ↑
    1 cache miss para acessar até 7 chaves

    Comparação (n = 1.000.000 chaves, t = 512):
    - Árvore binária: ~20 níveis, 20 acessos à memória
    - B-Tree: ~3 níveis, 3 acessos à memória

Complexidade

Operação	Complexidade	Acessos a disco (B-Tree de ordem t)
Busca	O(t * log_t(n))	O(log_t(n))
Inserção	O(t * log_t(n))	O(log_t(n))
Remoção	O(t * log_t(n))	O(log_t(n))
Travessia	O(n)	O(n / t)
Espaço	O(n)	O(n)
Split	O(t)	O(1)

Nota: O fator t na complexidade é constante para uma árvore de ordem fixa. Na prática, o número de acessos a disco é o que importa, e B-Trees minimizam esse valor.

Implementação em Rust

use std::fmt::Display;

/// Ordem mínima da B-Tree (cada nó tem entre T-1 e 2T-1 chaves)
const T: usize = 3; // Ordem 3: nós com 2 a 5 chaves

/// Nó da B-Tree
#[derive(Debug, Clone)]
struct NoBTree<K: Ord + Display + Clone, V: Clone + Display> {
    chaves: Vec<(K, V)>,            // Pares chave-valor ordenados
    filhos: Vec<NoBTree<K, V>>,     // Filhos (vazio se for folha)
    eh_folha: bool,
}

/// B-Tree com pares chave-valor
#[derive(Debug)]
struct BTree<K: Ord + Display + Clone, V: Clone + Display> {
    raiz: Option<NoBTree<K, V>>,
    tamanho: usize,
}

impl<K: Ord + Display + Clone, V: Clone + Display> NoBTree<K, V> {
    /// Cria um nó folha vazio
    fn nova_folha() -> Self {
        NoBTree {
            chaves: Vec::new(),
            filhos: Vec::new(),
            eh_folha: true,
        }
    }

    /// Verifica se o nó está cheio
    fn esta_cheio(&self) -> bool {
        self.chaves.len() >= 2 * T - 1
    }

    /// Busca uma chave no nó e seus descendentes
    fn buscar(&self, chave: &K) -> Option<&V> {
        // Encontra a posição da chave neste nó
        let mut i = 0;
        while i < self.chaves.len() && *chave > self.chaves[i].0 {
            i += 1;
        }

        // Verifica se a chave foi encontrada neste nó
        if i < self.chaves.len() && *chave == self.chaves[i].0 {
            return Some(&self.chaves[i].1);
        }

        // Se é folha, a chave não existe
        if self.eh_folha {
            return None;
        }

        // Desce para o filho apropriado
        self.filhos[i].buscar(chave)
    }

    /// Divide o filho no índice especificado (que deve estar cheio)
    fn dividir_filho(&mut self, indice: usize) {
        let filho = &mut self.filhos[indice];
        let meio = T - 1;

        // Cria novo nó com a metade direita das chaves
        let mut novo_no = NoBTree {
            chaves: filho.chaves.split_off(meio + 1),
            filhos: Vec::new(),
            eh_folha: filho.eh_folha,
        };

        // Move os filhos da metade direita para o novo nó
        if !filho.eh_folha {
            novo_no.filhos = filho.filhos.split_off(T);
        }

        // A chave mediana sobe para o pai
        let chave_mediana = filho.chaves.pop().unwrap();

        // Insere o novo nó e a chave mediana no pai
        self.chaves.insert(indice, chave_mediana);
        self.filhos.insert(indice + 1, novo_no);
    }

    /// Insere em um nó que NÃO está cheio
    fn inserir_nao_cheio(&mut self, chave: K, valor: V) {
        let mut i = self.chaves.len();

        if self.eh_folha {
            // Encontra a posição correta e insere
            while i > 0 && chave < self.chaves[i - 1].0 {
                i -= 1;
            }
            // Verifica duplicata
            if i < self.chaves.len() && chave == self.chaves[i].0 {
                self.chaves[i].1 = valor; // Atualiza valor existente
                return;
            }
            self.chaves.insert(i, (chave, valor));
        } else {
            // Encontra o filho correto
            while i > 0 && chave < self.chaves[i - 1].0 {
                i -= 1;
            }
            // Verifica duplicata no nó atual
            if i < self.chaves.len() && chave == self.chaves[i].0 {
                self.chaves[i].1 = valor;
                return;
            }

            // Se o filho está cheio, divide antes de descer
            if self.filhos[i].esta_cheio() {
                self.dividir_filho(i);
                // Decide qual dos dois filhos recebe a chave
                if chave > self.chaves[i].0 {
                    i += 1;
                } else if chave == self.chaves[i].0 {
                    self.chaves[i].1 = valor;
                    return;
                }
            }

            self.filhos[i].inserir_nao_cheio(chave, valor);
        }
    }

    /// Travessia em ordem (produz chaves ordenadas)
    fn em_ordem(&self, resultado: &mut Vec<(K, V)>) {
        for i in 0..self.chaves.len() {
            if !self.eh_folha {
                self.filhos[i].em_ordem(resultado);
            }
            resultado.push(self.chaves[i].clone());
        }
        // Último filho (à direita da última chave)
        if !self.eh_folha {
            self.filhos[self.chaves.len()].em_ordem(resultado);
        }
    }

    /// Exibe a estrutura da árvore com indentação
    fn exibir(&self, nivel: usize) {
        let indent = "  ".repeat(nivel);
        let chaves_str: Vec<String> = self.chaves.iter().map(|(k, _)| format!("{}", k)).collect();
        let tipo = if self.eh_folha { "folha" } else { "interno" };
        println!("{}[{}] ({})", indent, chaves_str.join(", "), tipo);
        for filho in &self.filhos {
            filho.exibir(nivel + 1);
        }
    }
}

impl<K: Ord + Display + Clone, V: Clone + Display> BTree<K, V> {
    /// Cria uma B-Tree vazia
    fn nova() -> Self {
        BTree {
            raiz: None,
            tamanho: 0,
        }
    }

    /// Retorna o número de elementos
    fn tamanho(&self) -> usize {
        self.tamanho
    }

    /// Busca uma chave na B-Tree
    fn buscar(&self, chave: &K) -> Option<&V> {
        match &self.raiz {
            None => None,
            Some(raiz) => raiz.buscar(chave),
        }
    }

    /// Insere um par chave-valor na B-Tree
    fn inserir(&mut self, chave: K, valor: V) {
        match self.raiz.take() {
            None => {
                // Árvore vazia — cria a raiz
                let mut raiz = NoBTree::nova_folha();
                raiz.chaves.push((chave, valor));
                self.raiz = Some(raiz);
            }
            Some(mut raiz) => {
                if raiz.esta_cheio() {
                    // Raiz está cheia — cria nova raiz e divide
                    let mut nova_raiz = NoBTree {
                        chaves: Vec::new(),
                        filhos: vec![raiz],
                        eh_folha: false,
                    };
                    nova_raiz.dividir_filho(0);
                    nova_raiz.inserir_nao_cheio(chave, valor);
                    self.raiz = Some(nova_raiz);
                } else {
                    raiz.inserir_nao_cheio(chave, valor);
                    self.raiz = Some(raiz);
                }
            }
        }
        self.tamanho += 1;
    }

    /// Travessia em ordem (pares chave-valor ordenados)
    fn em_ordem(&self) -> Vec<(K, V)> {
        let mut resultado = Vec::new();
        if let Some(raiz) = &self.raiz {
            raiz.em_ordem(&mut resultado);
        }
        resultado
    }

    /// Exibe a estrutura da árvore
    fn exibir(&self) {
        println!("=== Estrutura da B-Tree (T={}) ===", T);
        match &self.raiz {
            None => println!("  (vazia)"),
            Some(raiz) => raiz.exibir(0),
        }
    }
}

fn main() {
    let mut btree = BTree::nova();

    // Inserir valores para demonstrar splits
    let valores = vec![
        10, 20, 5, 6, 12, 30, 7, 17, 3, 1,
        25, 35, 22, 27, 15, 40, 45, 50, 8, 9,
    ];

    println!("Inserindo: {:?}\n", valores);

    for v in &valores {
        btree.inserir(*v, format!("val_{}", v));
    }

    btree.exibir();

    println!("\nTamanho: {}", btree.tamanho());

    // Busca
    println!("\nBuscar chave 17: {:?}", btree.buscar(&17));
    println!("Buscar chave 99: {:?}", btree.buscar(&99));

    // Travessia ordenada
    let ordenados = btree.em_ordem();
    let chaves: Vec<_> = ordenados.iter().map(|(k, _)| k).collect();
    println!("\nChaves em ordem: {:?}", chaves);
}

Métodos Principais

Método	Descrição
`nova()`	Cria uma B-Tree vazia
`inserir(chave, valor)`	Insere par chave-valor com split automático
`buscar(chave)`	Busca uma chave e retorna referência ao valor
`em_ordem()`	Retorna todos os pares em ordem crescente de chave
`tamanho()`	Retorna o número total de elementos
`exibir()`	Mostra a estrutura hierárquica da árvore
`dividir_filho(indice)`	Divide um filho cheio em dois nós
`inserir_nao_cheio(k, v)`	Inserção em nó que tem espaço disponível

BTreeMap e BTreeSet na Biblioteca Padrão

Em Rust, use as coleções da stdlib ao invés de implementar do zero:

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

fn main() {
    // BTreeMap: mapa ordenado por chave
    let mut mapa = BTreeMap::new();
    mapa.insert("banana", 3);
    mapa.insert("abacaxi", 1);
    mapa.insert("cereja", 5);
    mapa.insert("damasco", 2);

    println!("BTreeMap (sempre ordenado por chave):");
    for (fruta, qtd) in &mapa {
        println!("  {}: {}", fruta, qtd);
    }

    // Busca por intervalo
    println!("\nFrutas de 'b' a 'd':");
    for (fruta, qtd) in mapa.range("banana"..="damasco") {
        println!("  {}: {}", fruta, qtd);
    }

    // BTreeSet: conjunto ordenado
    let mut conjunto = BTreeSet::new();
    conjunto.insert(30);
    conjunto.insert(10);
    conjunto.insert(50);
    conjunto.insert(20);
    conjunto.insert(40);

    println!("\nBTreeSet (sempre ordenado): {:?}", conjunto);
    println!("Menor: {:?}", conjunto.iter().next());
    println!("Maior: {:?}", conjunto.iter().next_back());
}

Exemplo Prático: Índice de Sistema de Arquivos

use std::collections::BTreeMap;

/// Simula um índice de sistema de arquivos
struct IndiceFS {
    /// Mapeia caminho do arquivo → metadados
    indice: BTreeMap<String, MetadadosArquivo>,
}

#[derive(Debug, Clone)]
struct MetadadosArquivo {
    tamanho_bytes: u64,
    modificado: String,  // Data simplificada
    eh_diretorio: bool,
}

impl IndiceFS {
    fn novo() -> Self {
        IndiceFS {
            indice: BTreeMap::new(),
        }
    }

    /// Adiciona um arquivo ao índice
    fn adicionar(&mut self, caminho: &str, tamanho: u64, data: &str, dir: bool) {
        self.indice.insert(
            caminho.to_string(),
            MetadadosArquivo {
                tamanho_bytes: tamanho,
                modificado: data.to_string(),
                eh_diretorio: dir,
            },
        );
    }

    /// Lista todos os arquivos em um diretório (busca por prefixo)
    fn listar_diretorio(&self, dir: &str) -> Vec<(&String, &MetadadosArquivo)> {
        let prefixo = if dir.ends_with('/') {
            dir.to_string()
        } else {
            format!("{}/", dir)
        };

        self.indice
            .range(prefixo.clone()..)
            .take_while(|(k, _)| k.starts_with(&prefixo))
            .collect()
    }

    /// Busca um arquivo pelo caminho exato
    fn buscar(&self, caminho: &str) -> Option<&MetadadosArquivo> {
        self.indice.get(caminho)
    }

    /// Calcula o tamanho total de um diretório
    fn tamanho_diretorio(&self, dir: &str) -> u64 {
        self.listar_diretorio(dir)
            .iter()
            .filter(|(_, m)| !m.eh_diretorio)
            .map(|(_, m)| m.tamanho_bytes)
            .sum()
    }
}

fn main() {
    let mut fs = IndiceFS::novo();

    // Populando o índice
    fs.adicionar("/home/user/docs", 0, "2025-01-15", true);
    fs.adicionar("/home/user/docs/relatorio.pdf", 2048000, "2025-01-10", false);
    fs.adicionar("/home/user/docs/planilha.xlsx", 512000, "2025-01-12", false);
    fs.adicionar("/home/user/docs/notas.txt", 1024, "2025-01-15", false);
    fs.adicionar("/home/user/fotos", 0, "2025-01-14", true);
    fs.adicionar("/home/user/fotos/ferias.jpg", 4096000, "2025-01-14", false);
    fs.adicionar("/home/user/fotos/perfil.png", 256000, "2025-01-13", false);

    // Listar diretório (busca por prefixo — eficiente na B-Tree)
    println!("=== Conteúdo de /home/user/docs ===");
    for (caminho, meta) in fs.listar_diretorio("/home/user/docs") {
        let tipo = if meta.eh_diretorio { "DIR" } else { "ARQ" };
        println!("  [{}] {} ({} bytes)", tipo, caminho, meta.tamanho_bytes);
    }

    // Tamanho total do diretório
    let tam = fs.tamanho_diretorio("/home/user/docs");
    println!("\nTamanho total de docs: {:.2} MB", tam as f64 / 1_000_000.0);

    // Busca direta
    match fs.buscar("/home/user/fotos/ferias.jpg") {
        Some(meta) => println!("\nferias.jpg: {} bytes, modificado: {}",
            meta.tamanho_bytes, meta.modificado),
        None => println!("Arquivo não encontrado"),
    }
}

Comparação com Outras Estruturas

Critério	B-Tree	AVL / RB-Tree	HashMap	Array Ordenado
Busca	O(log n)	O(log n)	O(1)*	O(log n)
Inserção	O(log n)	O(log n)	O(1)*	O(n)
Busca por intervalo	Excelente	Boa	Ruim	Boa
Localidade de cache	Excelente	Ruim	Média	Excelente
Performance em disco	Excelente	Ruim	Ruim	Boa
Uso de memória	Moderado	Alto (ponteiros)	Moderado	Baixo

* Amortizado.

Quando usar B-Tree?

Use BTreeMap/BTreeSet quando precisa de dados ordenados em Rust.
Use quando faz muitas buscas por intervalo (range()).
Use em sistemas de arquivo e bancos de dados (performance em disco).
Não use se não precisa de ordenação — HashMap é mais rápido para busca pura.
Não use se o volume de dados é pequeno — a complexidade extra não compensa.

Exercícios

Exercício 1: Implementar Remoção na B-Tree

Implemente o método remover(chave) para a B-Tree. A remoção em B-Trees envolve três cenários: remoção de uma folha, remoção de um nó interno (substituir pelo predecessor ou sucessor), e fusão (merge) de nós quando ficam abaixo do mínimo.

Exercício 2: Comparação BTreeMap vs HashMap

Escreva um benchmark que insira 100.000 elementos aleatórios em um BTreeMap e um HashMap, e depois faça 100.000 buscas aleatórias. Compare os tempos. Em seguida, faça 10.000 buscas por intervalo (range()) no BTreeMap e simule o equivalente no HashMap. Qual é a diferença?

Exercício 3: Índice Invertido com BTreeMap

Implemente um índice invertido simples usando BTreeMap<String, BTreeSet<usize>>, onde a chave é uma palavra e o valor é o conjunto de IDs dos documentos que contêm essa palavra. Implemente busca por uma palavra e busca por prefixo (ex: todas as palavras que começam com “pro”).

Conclusão

A B-Tree é uma estrutura de dados essencial que equilibra eficiência de busca com localidade de memória. Ao agrupar múltiplas chaves por nó, ela minimiza acessos à memória e ao disco, sendo a escolha padrão para sistemas de armazenamento.

Em Rust, BTreeMap e BTreeSet oferecem uma implementação robusta e eficiente de B-Trees, com suporte a buscas por intervalo via range(), iteração ordenada e todas as operações em O(log n). Para a maioria dos casos onde dados ordenados são necessários, essas coleções da stdlib são a melhor escolha. Compreender como B-Trees funcionam internamente, especialmente o mecanismo de splitting, é fundamental para entender por que bancos de dados e sistemas de arquivos são tão eficientes.