--- title: "BTreeSet e BTreeMap: B-Tree em Rust | Rust Brasil" url: "https://rustlang.com.br/estruturas-dados/b-tree/" markdown_url: "https://rustlang.com.br/estruturas-dados/b-tree.MD" description: "B-Tree em Rust: BTreeMap, BTreeSet da stdlib. Implementação, splitting de nós e uso prático de árvores de busca multi-way." date: "" author: "Equipe Rust Brasil" --- # BTreeSet e BTreeMap: B-Tree em Rust | Rust Brasil B-Tree em Rust: BTreeMap, BTreeSet da stdlib. Implementação, splitting de nós e uso prático de árvores de busca multi-way. ## 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: 1. Cada nó tem no máximo **2t - 1** chaves. 2. Cada nó (exceto a raiz) tem no mínimo **t - 1** chaves. 3. A raiz tem no mínimo **1** chave (se não estiver vazia). 4. Um nó com **k** chaves tem exatamente **k + 1** filhos (se não for folha). 5. Todas as folhas estão no **mesmo nível**. 6. As chaves dentro de cada nó estão **ordenadas**. ```text 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: ```text 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: ```text 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? ```text Á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 ```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 { chaves: Vec<(K, V)>, // Pares chave-valor ordenados filhos: Vec>, // Filhos (vazio se for folha) eh_folha: bool, } /// B-Tree com pares chave-valor #[derive(Debug)] struct BTree { raiz: Option>, tamanho: usize, } impl NoBTree { /// 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 = 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 BTree { /// 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: ```rust 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 ```rust use std::collections::BTreeMap; /// Simula um índice de sistema de arquivos struct IndiceFS { /// Mapeia caminho do arquivo → metadados indice: BTreeMap, } #[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>`, 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.