Motivação: o problema do disco

Tudo o que estudamos até agora — ABP, AVL, tabela hash — tem uma premissa implícita: os dados cabem na memória RAM. Quando isso é verdade, as operações custam O(log n) ou O(1) com constantes pequenas, e tudo funciona bem.

Na prática, porém, sistemas reais armazenam bilhões de registros:

• Um banco de dados de e-commerce pode ter 10 bilhões de transações históricas.
• Um sistema de arquivos do Linux indexa milhões de arquivos em um único disco.
• Um índice de mecanismo de busca contém trilhões de URLs.

Esses dados vivem em disco (HD ou SSD). E disco tem uma propriedade fundamental, diferente da RAM:

Agora pense numa AVL com 1 bilhão de nós. A altura é ≈ 30. Uma busca faz 30 comparações, cada uma em um nó diferente — nós espalhados aleatoriamente pelo disco. Resultado: 30 leituras de disco. Cada leitura traz um bloco de 4KB, mas usa apenas os ≈ 20 bytes do nó AVL. 99,5% do bloco é desperdiçado.

A solução é mudar o raciocínio: em vez de guardar 1 chave por nó, guardar centenas de chaves por nó, preenchendo um bloco inteiro. Assim, cada leitura de disco traz informação máxima, e a altura da árvore despenca de 30 para 4 ou 5. Esta é a ideia central da B-Tree.

Exemplos retráteis: os exemplos desta aula ficam recolhidos (clique em "Ver exemplo" ou no título do passo). Expandir todos | Recolher todos

1. B-Tree (Árvore B)

1.1 Definição formal

Uma B-Tree é uma árvore de busca em que cada nó guarda várias chaves em ordem (e não apenas uma, como na ABP e na AVL). Ela é descrita por um número inteiro t ≥ 2, o grau mínimo (minimum degree), que controla o quão cheio ou vazio cada nó pode estar. Propriedades de uma B-Tree de grau mínimo t:

1. Número de filhos. Todo nó interno tem no máximo 2t filhos e, exceto a raiz, no mínimo t.
2. Número de chaves. Todo nó tem no máximo 2t−1 chaves e, exceto a raiz, no mínimo t−1.
3. Raiz. Pode ter menos chaves que os demais nós (no mínimo 1); se for interna (não folha), precisa ter pelo menos 2 filhos.
4. Balanceamento. Todas as folhas estão na mesma profundidade: a árvore é perfeitamente balanceada em altura.
5. Ordem. As chaves dentro de cada nó estão em ordem crescente.
6. Chaves e filhos. Um nó interno com k chaves possui exatamente k+1 filhos, cada um responsável por um intervalo de valores: o 1.º filho guarda as chaves menores que a 1.ª chave do nó; o i-ésimo filho guarda as chaves entre a (i−1)-ésima e a i-ésima chave do nó; o último guarda as chaves maiores que a última chave.

Exemplo da propriedade 6: um nó [20, 40, 60] tem 3 chaves e portanto 4 filhos: o 1.º guarda valores < 20; o 2.º, valores entre 20 e 40; o 3.º, entre 40 e 60; o 4.º, valores > 60.

Por que essas regras? O máximo (2t−1) é o que cabe num bloco de disco. O mínimo (t−1) impede nós quase vazios, garantindo que cada bloco lido seja bem aproveitado e que a árvore seja baixa. A regra das folhas no mesmo nível garante que toda busca percorre o mesmo número de nós. As operações das seções seguintes (divisão, empréstimo e fusão) existem justamente para manter essas propriedades verdadeiras depois de cada inserção e remoção.

Nota: outros livros usam convenções diferentes (por exemplo, a ordem m = máximo de filhos, com m = 2t). Aqui adotamos o grau mínimo t do livro Introduction to Algorithms (Cormen, Leiserson, Rivest e Stein), conhecido pela sigla CLRS, formada pelas iniciais dos autores.

1.2 Estrutura e exemplo usado na seção

Para desenhar, usamos t = 2: cada nó tem de 1 a 3 chaves (a raiz pode ter 1 a 3) e, se for interno, de 2 a 4 filhos. Dizemos que um nó estoura quando passa de 3 chaves (4 chaves) e que fica abaixo do mínimo quando tem menos de 1 chave (0 chaves, vazio). Em um nó, as chaves ficam lado a lado e os filhos penduram entre elas: um nó com k chaves tem k+1 filhos.

Exemplo usado em toda a seção: uma B-Tree de 5 nós com as chaves 10, 20, ..., 90 (a raiz e 4 folhas).

Verificando as propriedades:

• Raiz [20, 40, 60]: 3 chaves = 2t−1, o máximo permitido (a raiz tem 4 filhos, entre 2 e 2t).
• Folhas [10], [30] e [50]: 1 chave = t−1, o mínimo permitido. Folha [70, 80, 90]: 3 chaves, o máximo.
• Todas as folhas estão na profundidade 1, e as chaves estão em ordem dentro de cada nó.
• Guias corretas: a folha [10] só tem valores < 20; [30] está entre 20 e 40; [50] entre 40 e 60; [70, 80, 90] só tem valores > 60.

Esta árvore é exatamente o que se obtém inserindo 10, 20, 30, ..., 90 nessa ordem a partir da árvore vazia (veja o exemplo completo, passos 1 a 9). Numa ABP, essa mesma ordem de inserção produziria uma lista encadeada.

Verde = caminho percorrido (verde forte = encontrado); vermelho = chave a remover, ou nó com problema (estourado ou abaixo do mínimo, tracejado); amarelo = nó novo ou alterado; amarelo forte = chave inserida ou que mudou de lugar.

1.3 Inserção

Inserção em uma B-Tree:

1. Localizar a folha onde a nova chave deve ser inserida, descendo a partir da raiz.
2. Inserir a chave na posição correta, mantendo a ordenação.
3. Se o nó ultrapassar o máximo de chaves (2t−1), ele estoura: realizar um split (divisão), deixando as t−1 chaves menores num nó e as t maiores em outro.
4. Promover a chave mediana (a t-ésima) para o nó pai.
5. Se o pai também ultrapassar o máximo, repetir o processo, subindo até a raiz. Se a raiz estourar, cria-se uma nova raiz (é a única forma de a altura crescer).

Ideia principal: inserir na folha e dividir os nós quando necessário, mantendo a árvore balanceada. Os casos:

Caso 1 — A folha tem espaço

Basta inserir a chave na posição certa. Nada mais muda.

Caso 2 — A folha estoura e o pai tem espaço

Divide-se a folha; a chave do meio sobe e entra em ordem no pai, que continua com no máximo 3 chaves. (Se a folha for a própria raiz, não há pai: a chave que sobe forma uma nova raiz.)

Caso 3 — A divisão se propaga: o pai também estoura

Quando a chave que sobe faz o pai passar de 3 chaves, divide-se o pai do mesmo jeito, e assim por diante. Se a propagação chegar à raiz, nasce uma nova raiz e a altura aumenta em 1.

Caso 4 — A chave já existe

Como as chaves são únicas, nada é inserido (a busca pela posição encontra a chave).

1.4 Busca

Busca em uma B-Tree:

1. Começar pela raiz.
2. Comparar a chave buscada com as chaves do nó atual, que estão em ordem.
3. Se for igual a uma delas, a chave foi encontrada.
4. Se não for e o nó for folha, a chave não existe.
5. Caso contrário, descer para o filho cujo intervalo contém a chave e repetir.

Ideia principal: como na ABP, mas escolhendo entre até 2t caminhos por nó; cada nó visitado é uma leitura de disco, e a altura é pequena. Os casos:

Caso 1 — Encontrada num nó interno

Na B-Tree, as chaves (com seus dados) ficam em qualquer nó, então a busca pode terminar antes de chegar às folhas.

Caso 2 — Encontrada numa folha

Desce-se um nível por leitura até a folha que contém a chave.

Caso 3 — Não encontrada

Chegamos a uma folha que não contém a chave: não há mais para onde descer.

1.5 Remoção

Remoção em uma B-Tree: a remoção sempre acontece numa folha. Se a chave estiver num nó interno, troca-se por seu predecessor (maior chave da subárvore da esquerda) ou sucessor (menor da subárvore da direita), que estão em folhas, e remove-se este (de preferência o de uma folha com folga). Depois de remover da folha, existem três situações:

1. Remoção simples: a folha continua com pelo menos t−1 chaves; nada mais a fazer.
2. Empréstimo (redistribuição): a folha ficou com poucas chaves e um irmão adjacente tem folga; ele empresta uma chave, passando pelo pai (rotação).
3. Fusão (merge): nenhum irmão pode emprestar; junta-se a folha, o irmão e a chave separadora do pai num único nó. O pai perde uma chave e pode ficar com poucas, repetindo o problema um nível acima.

Se o problema chegar à raiz e ela ficar vazia, seu único filho vira a nova raiz (a altura diminui).

Ideia principal: manter todos os nós dentro dos limites de ocupação (pelo menos t−1 chaves) e preservar o balanceamento da árvore. Os casos:

Caso 1 — A chave não existe

A busca termina numa folha sem a chave: nada muda.

Caso 2 — A chave está numa folha com folga

A folha tem mais que t−1 chaves: remove-se a chave e pronto.

Caso 3 — A chave está num nó interno

Troca-se a chave pelo sucessor (ou predecessor) e remove-se este da folha. Se a folha ficar abaixo do mínimo, aplicam-se os casos 4 a 6.

Caso 4 — A folha fica abaixo do mínimo e um irmão pode emprestar

Rotação: a chave separadora do pai desce para a folha e a chave do irmão mais próxima dela sobe para o pai. O irmão perde uma chave, a folha ganha uma, o pai mantém o mesmo número.

Caso 5 — A folha fica abaixo do mínimo, nenhum irmão pode emprestar e o pai tem folga

Fusão: a folha, o irmão e a chave separadora do pai viram um único nó (com no máximo (t−1) + 1 + (t−1) = 2t−1 chaves, sempre cabe). O pai perde uma chave; como tinha mais que o mínimo, termina.

Caso 6 — A fusão se propaga: o pai também fica abaixo do mínimo

O pai passa por um empréstimo (6a) ou por outra fusão (6b), como se fosse uma folha. A diferença é que um nó interno também carrega filhos: na rotação, o filho que fica "entre" as chaves muda de pai; na fusão, os filhos dos dois nós ficam juntos. Se a raiz esvaziar, a árvore perde um nível.

1.6 Exemplo completo: todos os casos em sequência

Exemplos retráteis: os exemplos desta aula ficam recolhidos (clique em "Ver exemplo" ou no título do passo). Expandir todos | Recolher todos

Uma sequência de operações sobre uma única B-Tree (t = 2), partindo da árvore vazia. Cada passo indica o caso (das seções acima) que exemplifica; no conjunto, os passos cobrem todos os casos de busca, inserção e remoção. Nos desenhos, cada passo mostra a árvore após a operação (nas remoções, antes e depois). Ao fim do passo 9 temos a árvore base de 5 nós.

Verde = caminho percorrido (verde forte = encontrado); vermelho = chave a remover, ou nó com problema (estourado ou abaixo do mínimo, tracejado); amarelo = nó novo ou alterado; amarelo forte = chave inserida ou que mudou de lugar.

1.7 Complexidade

n = número de chaves armazenadas; t = grau mínimo (cada nó tem de t−1 a 2t−1 chaves); h = altura da árvore (número de arestas da raiz até uma folha). Como cada nó é um bloco de disco, medimos o custo principal em leituras de disco (uma por nó visitado); o custo de CPU dentro do nó vem à parte.

Pior caso = o maior custo que pode acontecer, para o pior conjunto de chaves e a pior ordem de operações. Caso médio = o custo típico, com chaves em ordem aleatória.

Por que a altura é O(log_t n)?

Intuição: cada nó interno tem pelo menos t filhos (a raiz, pelo menos 2). Então, mesmo no pior caso (todos os nós no mínimo), o número de nós multiplica por t a cada nível: 1 nó na raiz, pelo menos 2 no nível 1, pelo menos 2t no nível 2, 2t² no nível 3, e assim por diante. Contando as chaves, uma árvore de altura h tem no mínimo 2t^h − 1 chaves. Logo n ≥ 2t^h − 1, ou seja, h ≤ log_t((n+1)/2). Para t = 170 e n = 10⁹, h ≤ 3,6: no máximo 4 níveis (4 leituras de disco), contra cerca de 30 numa AVL. O caso melhor é a árvore com todos os nós cheios, de altura ≈ log_2t n; na prática os nós ficam em torno de 70% cheios (para chaves inseridas em ordem aleatória), e a altura fica entre os dois extremos, sempre O(log_t n).

• Busca: uma leitura por nível, no máximo h + 1. Dentro do nó, com varredura linear, o custo de CPU é O(t) por nó, ou O(t · log_t n) no total; com busca binária no nó cai para O(log₂ t) por nó, o que dá O(log n) no total, igual à AVL (a vantagem da B-Tree não está na CPU, e sim no número de leituras de disco).
• Inserção: desce h leituras até a folha e insere. Um split custa O(t) (copiar metade das chaves) e cria dois nós pela metade: a mesma folha só voltará a estourar depois de pelo menos t novas inserções nela. Por isso, em média, quase toda inserção termina na folha, sem dividir nada. No pior caso, o split sobe por todos os h níveis (como no caso 3), o que custa O(t · log_t n) em CPU.
• Remoção: também desce até uma folha (h leituras) e conserta no caminho de volta. Uma fusão só se propaga quando o irmão e o pai estão no mínimo; no caso comum, a folha tem folga (caso 2) ou o empréstimo resolve (caso 4). O pior caso (como o do passo 20) percorre os h níveis, com custo O(t · log_t n) em CPU.
• Espaço: como todo nó (menos a raiz) tem pelo menos metade das chaves possíveis, o espaço desperdiçado é no máximo cerca de metade.

1.8 Estrutura e funções em C (TAD simples)

Uma forma simples de representar a B-Tree em C: cada nó guarda um vetor de chaves, um vetor de filhos (ignorado se for folha) e um contador de quantas chaves estão em uso. O grau mínimo t fixa os tamanhos máximos: até 2t−1 chaves e 2t filhos por nó.

#define T 2   /* grau mínimo da árvore */

typedef struct NodoB {
    int  n;                       /* número de chaves em uso */
    int  chaves[2*T - 1];          /* chaves em ordem crescente */
    struct NodoB *filhos[2*T];      /* filhos (não usados se for folha) */
    int  folha;                    /* 1 se for folha, 0 caso contrário */
} NodoB;

NodoB *criarNodoB(int folha);                  /* cria um nó vazio (folha ou interno) */
NodoB *buscarB(NodoB *raiz, int chave);           /* devolve o nó onde a chave está, ou NULL */
NodoB *inserirB(NodoB *raiz, int chave);          /* insere a chave; devolve a (nova) raiz */
NodoB *removerB(NodoB *raiz, int chave);          /* remove a chave; devolve a (nova) raiz */
void   destruirB(NodoB *raiz);                   /* libera todos os nós */

main de demonstração:

int main(void) {
    NodoB *raiz = criarNodoB(1);                 /* raiz começa como folha vazia */

    int chaves[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    for (int i = 0; i < 9; i++)
        raiz = inserirB(raiz, chaves[i]);

    printf("buscarB(70) = %s\n", buscarB(raiz, 70) ? "achou" : "não achou");  /* achou */
    printf("buscarB(75) = %s\n", buscarB(raiz, 75) ? "achou" : "não achou");  /* não achou */

    raiz = removerB(raiz, 60);
    destruirB(raiz);
    return 0;
}

2. B+-Tree (Árvore B+)

2.1 A diferença fundamental

Na B-Tree, os dados (valores dos registros) podem estar em qualquer nó — interno ou folha. Na B+-Tree, há uma separação rigorosa:

Por que isso é melhor para bancos de dados?

• Nós internos mais densos: sem dados, os nós internos cabem mais chaves por bloco → árvore mais larga → altura menor → menos leituras de disco.
• Consultas por intervalo eficientes: para buscar todos os registros com chave entre A e B, navegamos até a folha com A e escaneamos a lista encadeada de folhas até passar B. Isso é O(log_t n + k), onde k é o número de resultados. Na B-Tree comum, cada resultado poderia estar num nó interno diferente, exigindo várias subidas e descidas na árvore.
• Varredura sequencial: percorrer todos os registros em ordem = percorrer a lista encadeada de folhas, sem tocar nos nós internos.

2.2 Estrutura e exemplo usado na seção

Mantemos t = 2. Os nós internos têm de 1 a 3 chaves de navegação (os separadores) e de 2 a 4 filhos. As folhas têm de t a 2t−1 chaves (2 ou 3): assim, uma folha que estoura (4 chaves) se divide em duas folhas de exatamente 2. Um nó interno com separadores s₁ < s₂ < ... leva ao filho i as chaves k com s_i ≤ k < s_i+1: uma chave igual a um separador vai para a direita. As setas ↔ entre as folhas são a lista encadeada.

Exemplo usado em toda a seção: uma B+-Tree de 5 nós com as mesmas chaves 10, 20, ..., 90 (raiz interna e 4 folhas). Nos desenhos, nós internos em cinza e folhas em azul.

Observe que 30, 50 e 70 aparecem na raiz e nas folhas. Isso é intencional: na B+-Tree, as chaves dos nós internos são cópias que servem apenas como separadores. Todos os dados reais estão nas folhas. Por serem só placas de sinalização, um separador pode continuar na árvore mesmo depois de a chave ter sido removida da folha (veja a remoção).

Verde = caminho percorrido (verde forte = encontrado); vermelho = chave a remover, ou nó com problema (estourado ou abaixo do mínimo, tracejado); amarelo = nó novo ou alterado; amarelo forte = chave inserida, copiada ou que mudou de lugar.

2.3 Inserção

Inserção em uma B+-Tree:

1. Localizar a folha onde a nova chave deve ser inserida (chave igual a um separador vai para a direita).
2. Inserir a chave na posição correta, mantendo a ordenação.
3. Se a folha ultrapassar o máximo de chaves (2t−1), realizar um split: duas folhas com t chaves cada.
4. Copiar a menor chave da folha da direita para o nó pai (ela continua na folha, porque o dado só existe lá).
5. Se o pai também ultrapassar o máximo, dividir o nó interno: a chave do meio sobe, sem cópia. Repetir até a raiz, podendo criar uma nova raiz.

Ideia principal: inserir na folha e dividir quando necessário; na divisão de folha a chave é copiada para o pai, e na divisão de nó interno ela é promovida. Os casos:

Caso 1 — A folha tem espaço

Caso 2 — A folha estoura e o pai tem espaço

Divide-se a folha em duas e copia-se a menor chave da direita para o pai. (Se a folha for a raiz, a cópia forma uma nova raiz.)

Caso 3 — A divisão se propaga: o pai também estoura

O nó interno que estoura (4 separadores) é dividido: a 2.ª chave sobe (sem cópia) e as outras ficam repartidas. Se for a raiz, nasce uma nova raiz e a altura aumenta em 1.

Caso 4 — A chave já existe

2.4 Busca

Busca em uma B+-Tree:

1. Começar pela raiz.
2. Em cada nó interno, comparar a chave com os separadores e descer pelo filho certo (chave igual a um separador vai para a direita).
3. Repetir até chegar a uma folha: a busca sempre desce até ela, mesmo que a chave apareça como separador.
4. Procurar a chave na folha: se estiver lá, foi encontrada; senão, não existe.

Ideia principal: os dados só ficam nas folhas, então toda busca percorre o mesmo número de nós. Os casos:

Caso 1 — A chave é igual a um separador

A busca não termina no nó interno: segue pelo filho da direita e encontra a chave na folha.

Caso 2 — A chave está numa folha (e não é separador)

Caso 3 — Não encontrada

A folha em que a chave deveria estar não a contém.

Busca por intervalo

É aqui que a B+-Tree brilha. Desce-se uma única vez até a folha que contém (ou conteria) o início do intervalo e, daí em diante, percorre-se a lista encadeada de folhas coletando as chaves até passar do fim, sem voltar aos nós internos.

Compare com uma ABP balanceada: cada um dos k resultados custaria uma nova busca, O(k log n); e numa B-Tree comum os k resultados podem estar em nós internos e folhas misturados, exigindo subidas e descidas.

2.5 Remoção

Remoção em uma B+-Tree: toda chave está numa folha, então a remoção sempre começa nela (não há troca por predecessor ou sucessor). Os separadores dos nós internos não precisam ser apagados, pois continuam sendo guias válidos. Depois de remover da folha, existem três situações:

1. Remoção simples: a folha continua com pelo menos t chaves; nada mais a fazer.
2. Empréstimo (redistribuição): a folha ficou com poucas chaves e um irmão adjacente tem folga; ele empresta uma chave e o separador do pai é atualizado.
3. Fusão (merge): nenhum irmão pode emprestar; juntam-se as duas folhas e o separador do pai é descartado. O pai perde uma chave e pode ficar com poucas, repetindo o problema um nível acima (nos nós internos, empréstimo e fusão funcionam como na B-Tree: o separador passa pelo pai ou desce).

Se o problema chegar à raiz e ela ficar vazia, seu único filho vira a nova raiz (a altura diminui).

Ideia principal: manter todos os nós dentro dos limites de ocupação e preservar o balanceamento da árvore, com os dados sempre nas folhas. Os casos:

Caso 1 — A chave não existe

Caso 2 — A folha tem folga

A folha tem mais que t chaves: remove-se a chave. Mesmo que ela seja um separador, o separador permanece no nó interno.

Caso 3 — A folha fica abaixo do mínimo e um irmão pode emprestar

A folha recebe a chave do irmão mais próxima dela e o separador do pai é atualizado para a nova menor chave da folha da direita.

Caso 4 — A folha fica abaixo do mínimo, nenhum irmão pode emprestar e o pai tem folga

Fundem-se as duas folhas (cabem: 2 + 1 ≤ 3) e o separador do pai que as dividia é descartado (diferente da B-Tree, em que a chave desce).

Caso 5 — A fusão se propaga: o pai também fica abaixo do mínimo

O nó interno que perdeu o separador fica sem chaves. Ele pede emprestado ao irmão (5a, por rotação pelo pai) ou se funde com o irmão, com o separador do avô descendo (5b). Se a raiz esvaziar, a árvore perde um nível.

2.6 Exemplo completo: todos os casos em sequência

Exemplos retráteis: os exemplos desta aula ficam recolhidos (clique em "Ver exemplo" ou no título do passo). Expandir todos | Recolher todos

Uma sequência de operações sobre uma única B+-Tree (t = 2), partindo da árvore vazia. Cada passo indica o caso que exemplifica; no conjunto, os passos cobrem todos os casos, exceto o 5a da remoção (visto na seção anterior). Nos desenhos, cada passo mostra a árvore após a operação (nas remoções, antes e depois). Ao fim do passo 9 temos a árvore base de 5 nós.

Verde = caminho percorrido (verde forte = encontrado); vermelho = chave a remover, ou nó com problema (estourado ou abaixo do mínimo, tracejado); amarelo = nó novo ou alterado; amarelo forte = chave inserida, copiada ou que mudou de lugar.

2.7 Complexidade

n = número de chaves; t = grau mínimo; k = número de resultados de uma busca por intervalo. Como na B-Tree, o custo principal é medido em leituras de disco (um nó por leitura).

Por que a busca custa sempre a mesma coisa?

Intuição: como os dados só ficam nas folhas e todas as folhas estão na mesma profundidade, toda busca percorre exatamente h + 1 nós, achando a chave ou não. Na B-Tree uma busca pode parar antes, num nó interno; na B+-Tree isso nunca acontece, mas em compensação os nós internos são mais densos (sem dados, cabem mais separadores por bloco), o que deixa a árvore mais larga e mais baixa: com blocos de 4KB, chaves de 4 bytes e ponteiros de 8 bytes, cada nó interno comporta cerca de 340 filhos, e 4 níveis alcançam bilhões de chaves. A altura segue h ≤ log_t n (mesma dedução da B-Tree: cada nível multiplica o número de nós por pelo menos t).

Intervalo: o custo é a descida, O(log_t n), mais a leitura das folhas que contêm os k resultados. Como cada folha guarda de t a 2t−1 chaves, são no máximo ⌈k/t⌉ + 1 folhas: no total, O(log_t n + k/t) leituras (e O(k) comparações), contra O(k · log_t n) da B-Tree.

Inserção e remoção: descem até uma folha e consertam no caminho de volta. Como na B-Tree, a divisão de uma folha deixa duas folhas pela metade, então a mesma folha só volta a estourar depois de várias inserções: em média, quase sempre basta escrever na folha. No pior caso (todos os nós cheios na inserção, todos no mínimo na remoção), a correção sobe por todos os h níveis.

Comparação resumida com a B-Tree e com a AVL (n = 10⁹, t = 170):

Note que a busca por intervalo é onde a B+-Tree brilha: O(log_t n + k) versus O(k · log_t n) da B-Tree. Para k = 100.000 resultados, a diferença é absurda.

2.8 Estrutura e funções em C (TAD simples)

A diferença para a B-Tree aparece em dois pontos da struct: as chaves de um nó interno são só separadores (não guardam dado associado), e toda folha tem um ponteiro prox para a folha seguinte, formando a lista encadeada que liga todas as folhas da esquerda para a direita.

#define T 2   /* grau mínimo da árvore */

typedef struct NodoBMais {
    int  n;                          /* número de chaves em uso */
    int  chaves[2*T - 1];             /* separadores (interno) ou chaves reais (folha) */
    struct NodoBMais *filhos[2*T];     /* filhos (não usados se for folha) */
    int  folha;                       /* 1 se for folha, 0 caso contrário */
    struct NodoBMais *prox;           /* próxima folha, da esquerda p/ direita (só em folhas) */
} NodoBMais;

NodoBMais *criarNodoBMais(int folha);            /* cria um nó vazio (folha ou interno) */
NodoBMais *buscarBMais(NodoBMais *raiz, int chave); /* devolve a folha onde a chave está, ou NULL */
NodoBMais *inserirBMais(NodoBMais *raiz, int chave);/* insere a chave; devolve a (nova) raiz */
NodoBMais *removerBMais(NodoBMais *raiz, int chave);/* remove a chave; devolve a (nova) raiz */
void       destruirBMais(NodoBMais *raiz);               /* libera todos os nós */

main de demonstração:

int main(void) {
    NodoBMais *raiz = criarNodoBMais(1);         /* raiz começa como folha vazia */

    int chaves[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    for (int i = 0; i < 9; i++)
        raiz = inserirBMais(raiz, chaves[i]);

    printf("buscarBMais(70) = %s\n", buscarBMais(raiz, 70) ? "achou" : "não achou");  /* achou */

    /* busca por intervalo: desce até a 1ª folha e segue os ponteiros prox */
    NodoBMais *f = buscarBMais(raiz, 30);
    while (f != NULL) {
        /* imprimiria aqui as chaves de f, em ordem, até o fim do intervalo */
        f = f->prox;
    }

    raiz = removerBMais(raiz, 60);
    destruirBMais(raiz);
    return 0;
}

3. Aplicações em Sistemas Reais

3.1 Sistemas de arquivos

• ext4 (Linux): usa B-Trees para indexar blocos de dados de arquivos grandes e para o diretório HTree (uma variante de B-Tree hash).
• NTFS (Windows): o MFT (Master File Table) usa B+-Trees para indexar arquivos por nome.
• HFS+ / APFS (macOS): catálogo de arquivos implementado como B-Tree.
• Btrfs: um sistema de arquivos inteiramente construído sobre B-Trees copy-on-write.

3.2 Bancos de dados

• MySQL InnoDB: todos os índices (primário e secundários) são B+-Trees. A tabela em si é organizada como uma B+-Tree com os dados nas folhas (chamada de clustered index).
• PostgreSQL: o tipo de índice padrão é B+-Tree. É o que se cria com CREATE INDEX sem especificar tipo.
• SQLite: a estrutura de dados central é uma B-Tree (com variante B+ para índices).
• Oracle, SQL Server: também usam B+-Trees para índices.

3.3 Por que não AVL em banco de dados?

3.4 Comparação B-Tree vs B+-Tree

Resumo

• B-Trees e B+-Trees foram projetadas para o modelo de acesso a disco: cada nó = um bloco = uma leitura.
• O grau mínimo t define o fator de ramificação: nós têm entre t−1 e 2t−1 chaves. Com t grande, a altura é minúscula.
• A altura garantida O(log_t n) implica O(log_t n) leituras de disco por operação — tipicamente 3 a 5 para bilhões de registros.
• A B-Tree mantém todas as folhas na mesma profundidade via divisões (inserção) e empréstimos e fusões (remoção) — balanceamento perfeito.
• Cada operação tem poucos casos: inserção (folha com espaço, split, split em cascata), remoção (folha com folga, empréstimo, fusão, fusão em cascata) e busca (achar, não achar).
• A B+-Tree separa navegação (nós internos) de dados (folhas) e encadeia as folhas, tornando buscas por intervalo dramaticamente mais eficientes.
• MySQL InnoDB, PostgreSQL, ext4, NTFS e a maioria dos sistemas de armazenamento modernos usam B+-Trees como estrutura de índice central.

Exercícios

1. Uma B-Tree tem grau mínimo t=3. Qual o número mínimo e máximo de chaves por nó não-raiz? E de filhos?

2. Por que uma B-Tree garante que todas as folhas estão na mesma profundidade? Qual invariante assegura isso?

3. Insira as chaves 5, 15, 25, 35, 45 em ordem numa B-Tree vazia de grau t=2. Mostre a árvore após cada inserção, incluindo splits.

4. Qual é a altura máxima de uma B-Tree de grau t com n chaves? Expresse como fórmula e calcule para t=100 e n=10⁹.

5. Qual é a principal diferença entre B-Tree e B+-Tree em termos de onde os dados ficam armazenados? Qual suporta melhor buscas por intervalo, e por quê?

6. Na B+-Tree, por que as chaves aparecem tanto nos nós internos quanto nas folhas? Isso representa um problema de redundância?

7. Um banco de dados tem 50 milhões de registros. Um índice B+-Tree com t=200 é usado. Quantas leituras de disco uma busca exata demora aproximadamente? Compare com uma AVL balanceada.

8. Por que sistemas de arquivos e bancos de dados usam B-Trees em vez de AVL, mesmo ela garantindo O(log n)?

9. Na B-Tree de 5 nós desta aula (t=2, raiz [20, 40, 60], folhas [10], [30], [50] e [70, 80, 90]), remova, nesta ordem, as chaves 80, 60 e 10. Mostre a árvore após cada remoção e diga qual caso da seção 1.5 foi aplicado.

10. Na B+-Tree de 5 nós desta aula (raiz [30, 50, 70], folhas [10, 20], [30, 40], [50, 60] e [70, 80, 90]), insira a chave 85 e, em seguida, remova a chave 10. Mostre a árvore após cada operação, indicando os casos aplicados (seções 2.3 e 2.5).

Gabaritos

Após inserir 5:       [5]

Após inserir 15:      [5, 15]

Após inserir 25:      [5, 15, 25]       (raiz com 3 chaves = 2t-1, ok mas cheia)

Após inserir 35:
  35 entra em [5, 15, 25] e a raiz estoura: [5, 15, 25, 35] (4 chaves). Sobe a 2ª chave (15), que forma a nova raiz:
      [15]
      /  \
    [5]  [25]
  O 35 fica na folha da direita:
      [15]
      /  \
    [5]  [25, 35]

Após inserir 45:
  Raiz [15], 45 > 15 → filho [25, 35], 45 > 35 → inserir em [25,35] → [25,35,45] (cheio, mas é folha e cabe 3 chaves).
      [15]
      /  \
    [5]  [25, 35, 45]

Árvore inicial:  [20, 40, 60]  com folhas  [10] [30] [50] [70, 80, 90]

Remover 80  (caso 2: a chave está numa folha com folga)
  [70, 80, 90] vira [70, 90] (2 chaves, mais que o mínimo).
  [20, 40, 60]  com folhas  [10] [30] [50] [70, 90]

Remover 60  (caso 3: a chave está num nó interno)
  Predecessor: 50, numa folha no mínimo. Sucessor: 70, numa folha com folga.
  Troca 60 por 70 e remove 70 da folha, que vira [90].
  [20, 40, 70]  com folhas  [10] [30] [50] [90]

Remover 10  (caso 5: fusão, com o pai folgado)
  A folha [10] fica vazia; seu único irmão, [30], está no mínimo.
  Funde [ ] + 20 (desce da raiz) + [30] = [20, 30]. A raiz perde uma chave.
  [40, 70]  com folhas  [20, 30] [50] [90]

Árvore inicial:  raiz [30, 50, 70]  com folhas  [10, 20] [30, 40] [50, 60] [70, 80, 90]

Inserir 85  (inserção, caso 3: a divisão se propaga)
  85 vai para [70, 80, 90], que estoura: [70, 80] e [85, 90]; 85 é copiado para a raiz.
  A raiz [30, 50, 70, 85] estoura: 50 sobe e forma a nova raiz.
                        [50]
                 /               \
             [30]              [70, 85]
            /    \            /    |    \
      [10,20]  [30,40]  [50,60]  [70,80]  [85,90]

Remover 10  (remoção, caso 5a: a fusão se propaga e o pai empresta)
  [10, 20] vira [20], abaixo do mínimo (2); o irmão [30, 40] está no mínimo.
  Funde as folhas em [20, 30, 40] e descarta o separador 30; o nó [30] fica vazio.
  O irmão [70, 85] tem folga: por rotação, 50 desce da raiz e 70 sobe para a raiz.
                        [70]
                 /               \
             [50]                [85]
            /    \              /    \
  [20,30,40]  [50,60]     [70,80]  [85,90]