Árvores em Memória Secundária (Árvores B)

1. O Abismo da Memória

Por que não usamos AVL ou Árvore Rubro-Negra para bancos de dados em disco (como PostgreSQL ou MySQL)? - RAM: Acesso em nanossegundos (\(10^{-9}\) s). - Disco (SSD/HDD): Acesso em milissegundos (\(10^{-3}\) s). É 1.000.000x mais lento.

Se usarmos uma árvore binária, buscar um registro em 1 milhão de itens requer altura \(\log_2(10^6) \approx 20\). Isso significa 20 leituras de disco aleatórias. Se cada leitura leva 10ms, a busca leva 0.2 segundos. Inaceitável para bancos de dados de alta performance.

Precisamos de uma árvore mais baixa e mais gorda, que aproveite o fato de que, quando lemos do disco, lemos um bloco inteiro (ex: 4KB ou 8KB) de uma vez.

2. Árvore B (B-Tree)

Inventada por Bayer e McCreight (1972), a Árvore B generaliza a árvore binária. Em vez de 2 filhos, um nó pode ter milhares de filhos.

Propriedades da Árvore B de ordem \(M\)

  1. Cada nó contém no máximo \(M-1\) chaves.
  2. Cada nó (exceto raiz e folhas) tem pelo menos \(\lceil M/2 \rceil\) filhos.
  3. Todas as folhas estão no mesmo nível. A árvore é perfeitamente balanceada por definição.
  4. As chaves dentro de um nó estão ordenadas.

A Vantagem da Altura

Se \(M=1000\) (ordem mil), um nó raiz com 1000 filhos, e cada filho com 1000 netos, gera: - Nível 1: \(1.000\) itens. - Nível 2: \(1.000.000\) itens. - Nível 3: \(1.000.000.000\) (1 bilhão) de itens.

Com apenas 3 acessos a disco, encontramos qualquer chave em 1 bilhão.

3. Lógica de Inserção (Split)

Diferente de árvores binárias que crescem para baixo (adicionando folhas), a Árvore B cresce para cima.

  1. Busque a folha onde a chave deve entrar.
  2. Se a folha tiver espaço (menos de \(M-1\) chaves), insira ordenado.
  3. Se a folha estiver cheia (Overflow):
    • Divida o nó em dois.
    • A chave do meio sobe para o pai (“promovida”).
    • Se o pai encher, divida o pai… (pode propagar até a raiz).
    • Se a raiz dividir, cria-se uma nova raiz, aumentando a altura da árvore em 1.

4. Árvore B+ (B-Plus Tree)

É a variação usada na prática (sistemas de arquivos NTFS, ext4, bancos SQL).

Diferenças da B-Tree Clássica

  1. Dados apenas nas Folhas: Os nós internos guardam apenas cópias das chaves para guiar a busca (índices). Os registros reais (ou ponteiros para o arquivo de dados) ficam exclusivamente nos nós folha.
  2. Folhas Encadeadas: Todas as folhas são ligadas como uma Lista Encadeada.

Por que B+ é melhor?

  • Range Queries (Consultas de Faixa): Para fazer SELECT * FROM users WHERE id BETWEEN 100 AND 200:
    • Buscamos o 100 (Custo \(\log_M N\)).
    • Percorremos a lista encadeada das folhas até passar de 200.
    • Na Árvore B clássica, teríamos que subir e descer na árvore várias vezes (in-order traversal custoso em disco).
  • Densidade: Como nós internos não guardam dados pesados, cabem muito mais chaves em um bloco de disco, aumentando o fator de ramificação \(M\) e diminuindo a altura.

5. Exemplo Conceitual (Ordem 4)

Imagine uma Árvore B de ordem 4 (Máximo 3 chaves por nó). Inserindo: 10, 20, 30 Nó: [10, 20, 30]

Inserindo 40: Nó estoura (4 chaves). Dividimos! - 20 sobe. - Raiz: [20] - Filhos: [10] e [30, 40]

Inserindo 50, 60: O filho da direita enche [30, 40, 50, 60]. Split! - 50 sobe para a raiz. - Raiz: [20, 50] - Filhos: [10], [30, 40], [60]

6. Implementação

Implementar uma B-Tree do zero é um projeto complexo (centenas de linhas para gerenciar leitura/escrita de arquivos). Em Java, não há B-Tree na biblioteca padrão (pois é focada em memória RAM), mas bibliotecas como H2 Database ou Apache Derby implementam B+ Trees em Java puro.

Para fins educacionais em AED2, focamos no entendimento conceitual: - Calcular altura mínima/máxima. - Simular inserções e splits no papel. - Entender o custo de I/O.

Complexidade

  • Tempo: \(O(\log_M N)\) acessos a disco.
  • Espaço: \(O(N)\).
Back to top