Uma estrutura que mantém dados sempre ordenados e permite buscas, inserções e remoções em tempo O(log n) — mesmo com milhões de registros em disco.
Imagine que você tem uma biblioteca gigante com milhões de livros. Uma lista simples seria lenta demais — você teria que verificar livro por livro. Uma árvore binária de busca (BST) ajuda, mas pode ficar desequilibrada. A Árvore B resolve isso de forma elegante.
Criada em 1972 por Rudolf Bayer e Edward McCreight nos laboratórios da Boeing, a Árvore B foi projetada especificamente para funcionar bem com armazenamento em disco, onde ler dados é muito mais lento que na memória RAM.
A diferença fundamental: numa árvore binária, cada nó tem no máximo 2 filhos. Numa Árvore B, cada nó pode ter dezenas ou centenas de filhos. Isso deixa a árvore muito mais "achatada" (com menos níveis), reduzindo o número de leituras em disco.
| Característica | Árvore Binária (BST) | Árvore B |
|---|---|---|
| Filhos por nó | Até 2 | Até m (ordem da árvore) |
| Chaves por nó | 1 | Até m-1 |
| Altura típica | O(n) pior caso | O(log n) garantido |
| Balanceamento | Pode degerar | Sempre balanceada |
| Uso ideal | Memória RAM | Disco / grandes volumes |
Uma Árvore B de ordem m (também chamada de grau mínimo t onde m = 2t) segue regras rígidas que garantem que ela se mantenha sempre balanceada:
| Tipo | Dados nos nós internos | Dados nas folhas | Ligação entre folhas | Uso comum |
|---|---|---|---|---|
| B-Tree | Sim | Sim | Não | Índices gerais |
| B+-Tree | Só chaves | Chaves + dados | Sim (lista encadeada) | PostgreSQL, MySQL |
| B*-Tree | Sim | Sim | Parcial | HFS+ (macOS) |
Na B+-Tree as folhas formam uma lista ligada, o que torna buscas por intervalo (ex: "todos os usuários entre 20 e 30 anos") muito eficientes.
Abaixo temos uma Árvore B de ordem 5 (cada nó comporta até 4 chaves e até 5 filhos). Passe o mouse sobre os nós para ver as informações.
Cada retângulo representa um nó. Dentro dele, as chaves estão separadas por linhas verticais. Entre cada par de chaves (e antes da primeira e após a última) existe um ponteiro implícito para um nó filho.
[10 | 20 | 30]: tudo menor que 10 vai para o
1º filho, entre 10 e 20 vai para o 2º filho, entre 20 e 30 para o 3º
filho, e maior que 30 para o 4º filho.
No livro Entendendo Algoritmos, estruturas são representadas de forma simples e direta. Seguindo esse espírito, usamos apenas dicionários Python:
# Um nó de Árvore B é apenas um dicionário Python
# Sem classes, sem complicação — só dados!
# Criando um nó folha com 2 chaves
no_folha = {
"chaves": [5, 8], # as chaves armazenadas, sempre ordenadas
"filhos": [], # folha não tem filhos
"eh_folha": True
}
# Criando um nó interno (raiz) com 3 chaves e 4 filhos
no_raiz = {
"chaves": [10, 20, 30],
"filhos": [filho1, filho2, filho3, filho4],
"eh_folha": False
}
# A árvore inteira é representada assim
arvore_b = {
"raiz": no_raiz,
"ordem": 5 # cada nó tem no máximo 4 chaves (ordem - 1)
}
Simples assim! Um nó é um dicionário com três campos:
chaves, filhos e eh_folha. A
árvore toda é um dicionário com a raiz e a ordem.
Buscar um valor numa Árvore B é como seguir um mapa: em cada nó, você decide se encontrou o valor, se vai para a esquerda, para o meio ou para a direita.
def buscar(no, valor):
"""
Busca um valor na árvore B.
Retorna (nó, índice) se encontrado, ou None se não existe.
no → dicionário representando o nó atual
valor → o número que estamos procurando
"""
# Percorre as chaves do nó da esquerda para a direita
i = 0
while i < len(no["chaves"]) and valor > no["chaves"][i]:
i += 1
# Encontrou o valor exato!
if i < len(no["chaves"]) and valor == no["chaves"][i]:
return (no, i) # ✅ achou
# Chegou em folha e não achou: valor não existe
if no["eh_folha"]:
return None # ❌ não existe
# Desce para o filho adequado e repete
return buscar(no["filhos"][i], valor)
# --- Exemplo de uso ---
resultado = buscar(arvore_b["raiz"], 25)
if resultado:
no, idx = resultado
print(f"Encontrado! Chave 25 está no índice {idx} do nó {no['chaves']}")
else:
print("Valor não encontrado na árvore.")Inserir numa Árvore B é mais elaborado que buscar. O desafio: a árvore deve sempre manter suas propriedades após a inserção. O mecanismo chave é o split (divisão) de nós cheios.
Quando um nó está cheio (tem o máximo de chaves), ele é dividido em dois. A chave do meio sobe para o nó pai. É como dividir um compartimento lotado em dois menores.
Insira valores na árvore abaixo e observe o comportamento visual:
# ─────────────────────────────────────────────────
# SPLIT: divide um filho cheio em dois nós menores
# ─────────────────────────────────────────────────
def split_filho(pai, i, ordem):
"""
pai → nó pai (dicionário)
i → índice do filho cheio em pai["filhos"]
ordem → ordem da árvore (máximo de filhos por nó)
"""
t = ordem // 2 # metade da ordem (grau mínimo)
filho_cheio = pai["filhos"][i]
# Cria o novo nó que receberá a metade direita
novo_no = {
"chaves": filho_cheio["chaves"][t:], # metade direita
"filhos": filho_cheio["filhos"][t:] if not filho_cheio["eh_folha"] else [],
"eh_folha": filho_cheio["eh_folha"]
}
# A chave do meio sobe para o pai
chave_do_meio = filho_cheio["chaves"][t - 1]
# Filho original fica só com a metade esquerda
filho_cheio["chaves"] = filho_cheio["chaves"][:t - 1]
if not filho_cheio["eh_folha"]:
filho_cheio["filhos"] = filho_cheio["filhos"][:t]
# Insere a chave do meio no pai, na posição correta
pai["chaves"].insert(i, chave_do_meio)
pai["filhos"].insert(i + 1, novo_no)
# ─────────────────────────────────────────────────
# INSERÇÃO num nó que não está cheio
# ─────────────────────────────────────────────────
def inserir_nao_cheio(no, valor, ordem):
"""Insere valor num nó que tem espaço disponível."""
max_chaves = ordem - 1
i = len(no["chaves"]) - 1 # começa pelo final
if no["eh_folha"]:
# Folha: insere o valor na posição correta (mantém ordenado)
no["chaves"].append(None)
while i >= 0 and valor < no["chaves"][i]:
no["chaves"][i + 1] = no["chaves"][i]
i -= 1
no["chaves"][i + 1] = valor
else:
# Interno: encontra o filho correto para descer
while i >= 0 and valor < no["chaves"][i]:
i -= 1
i += 1
# Se o filho está cheio, faz split antes de descer
if len(no["filhos"][i]["chaves"]) == max_chaves:
split_filho(no, i, ordem)
# Após split, decide qual dos dois novos filhos usar
if valor > no["chaves"][i]:
i += 1
inserir_nao_cheio(no["filhos"][i], valor, ordem)
# ─────────────────────────────────────────────────
# INSERÇÃO principal (ponto de entrada)
# ─────────────────────────────────────────────────
def inserir(arvore, valor):
"""
Insere um valor na árvore B.
arvore → dicionário com "raiz" e "ordem"
"""
raiz = arvore["raiz"]
ordem = arvore["ordem"]
max_chaves = ordem - 1
# Caso especial: raiz está cheia → cresce a altura da árvore
if len(raiz["chaves"]) == max_chaves:
nova_raiz = {
"chaves": [],
"filhos": [raiz], # raiz antiga vira filho
"eh_folha": False
}
arvore["raiz"] = nova_raiz # nova raiz assume o topo
split_filho(nova_raiz, 0, ordem) # divide a raiz antiga
inserir_nao_cheio(nova_raiz, valor, ordem)
else:
inserir_nao_cheio(raiz, valor, ordem)
# --- Exemplo completo ---
minha_arvore = {
"raiz": {"chaves": [], "filhos": [], "eh_folha": True},
"ordem": 5
}
for num in [10, 20, 5, 6, 12, 30, 7, 17]:
inserir(minha_arvore, num)
print(f"Inserido {num}. Raiz: {minha_arvore['raiz']['chaves']}")A remoção é a operação mais complexa. Depois de remover uma chave, o nó pode ficar com poucas chaves (violando as propriedades). A solução: redistribuição (empresta do irmão) ou merge (une dois nós).
def predecessor(no):
"""Maior chave da subárvore esquerda (predecessor em-ordem)."""
while not no["eh_folha"]:
no = no["filhos"][-1] # sempre vai para o filho mais à direita
return no["chaves"][-1]
def merge_filhos(pai, i, ordem):
"""
Une filho[i] com filho[i+1], descendo chave[i] do pai.
Resultado: filho[i] absorve tudo, filho[i+1] some.
"""
t = ordem // 2
filho_esq = pai["filhos"][i]
filho_dir = pai["filhos"][i + 1]
# Chave separadora do pai desce para o meio
filho_esq["chaves"].append(pai["chaves"].pop(i))
# Absorve todas as chaves e filhos do irmão direito
filho_esq["chaves"].extend(filho_dir["chaves"])
filho_esq["filhos"].extend(filho_dir["filhos"])
# Remove o filho direito (não existe mais)
pai["filhos"].pop(i + 1)
def remover(no, valor, ordem):
"""
Remove um valor da subárvore com raiz em 'no'.
Mantém todas as propriedades da Árvore B.
"""
t = ordem // 2
min_chaves = t - 1 # mínimo de chaves por nó (exceto raiz)
max_chaves = ordem - 1
# Encontra a posição do valor (ou onde deveria estar)
i = 0
while i < len(no["chaves"]) and valor > no["chaves"][i]:
i += 1
# CASO 1: Valor encontrado neste nó
if i < len(no["chaves"]) and no["chaves"][i] == valor:
if no["eh_folha"]:
# 1a. Folha: remove diretamente
no["chaves"].pop(i)
else:
# 1b. Nó interno: substitui pelo predecessor
pred = predecessor(no["filhos"][i])
no["chaves"][i] = pred # substitui
remover(no["filhos"][i], pred, ordem) # remove predecessor da folha
# CASO 2: Valor não está neste nó → desce para o filho certo
else:
if no["eh_folha"]:
print(f"Valor {valor} não encontrado na árvore.")
return
filho = no["filhos"][i]
# Garante que o filho tem chaves suficientes antes de descer
if len(filho["chaves"]) == min_chaves:
# Tenta redistribuir com irmão esquerdo
if i > 0 and len(no["filhos"][i-1]["chaves"]) > min_chaves:
irm_esq = no["filhos"][i - 1]
filho["chaves"].insert(0, no["chaves"][i - 1])
no["chaves"][i - 1] = irm_esq["chaves"].pop()
if not irm_esq["eh_folha"]:
filho["filhos"].insert(0, irm_esq["filhos"].pop())
# Tenta redistribuir com irmão direito
elif i < len(no["filhos"]) - 1 and len(no["filhos"][i+1]["chaves"]) > min_chaves:
irm_dir = no["filhos"][i + 1]
filho["chaves"].append(no["chaves"][i])
no["chaves"][i] = irm_dir["chaves"].pop(0)
if not irm_dir["eh_folha"]:
filho["filhos"].append(irm_dir["filhos"].pop(0))
# Nenhum irmão tem chaves sobrando → faz merge
else:
if i > 0:
merge_filhos(no, i - 1, ordem)
i -= 1 # após merge, o filho ficou em i-1
else:
merge_filhos(no, i, ordem)
remover(no["filhos"][i], valor, ordem)
# --- Exemplo de uso ---
remover(minha_arvore["raiz"], 20, minha_arvore["ordem"])
print("Após remover 20:", minha_arvore["raiz"]["chaves"])A beleza das Árvores B está na garantia matemática de eficiência. Como a árvore está sempre balanceada, todas as operações têm comportamento previsível.
| Operação | Tempo (melhor) | Tempo (pior) | Espaço |
|---|---|---|---|
| Busca | O(log n) | O(log n) | O(1) |
| Inserção | O(log n) | O(log n) | O(log n)* |
| Remoção | O(log n) | O(log n) | O(log n)* |
| Percurso em ordem | O(n) | O(n) | O(h) |
* Espaço da pilha de recursão, onde h = O(log n) é a altura da árvore.
A altura de uma Árvore B de ordem m com n chaves é no máximo:
Com m=1000 (comum em bancos de dados), uma árvore com 1 bilhão de registros tem altura máxima de apenas 3 níveis! Ou seja, qualquer busca exige no máximo 3 leituras em disco.
| Estrutura | Busca | Inserção | Remoção | Balanceamento |
|---|---|---|---|---|
| Árvore B | O(log n) | O(log n) | O(log n) | Automático |
| AVL | O(log n) | O(log n) | O(log n) | Estrito |
| Red-Black | O(log n) | O(log n) | O(log n) | Parcial |
| Hash Table | O(1) médio | O(1) médio | O(1) médio | Não suporta ordem |
| Lista Ordenada | O(log n)* | O(n) | O(n) | Manual |
| BST (pior caso) | O(n) | O(n) | O(n) | Pode degerar |
* Busca binária em lista ordenada é O(log n), mas inserção e remoção são O(n) por deslocamento de elementos.
5 perguntas para fixar o conteúdo. Cada resposta inclui uma explicação.