Algoritmo de remoção no caso 3 na árvore B
No Caso 3, a remoção de uma chave causa uma violação na ocupação mínima de uma página folha.
Para corrigir essa situação sem comprometer o balanceamento da árvore, usamos a técnica de redistribuição de chaves com uma página irmã que tem chaves sobrando.
Problema
Após remover uma chave de uma folha (Caso 1), a quantidade de chaves na página fica menor do que o mínimo permitido:
- Para uma árvore B de ordem
, o mínimo permitido é chaves.
Nesse caso, verifica-se se uma página irmã (nó no mesmo nível e com o mesmo pai) pode ceder uma chave.
Caso uma página irmã tenha mais chaves do que o mínimo, redistribuímos as chaves para corrigir o problema.
Passo a Passo
1. Identificar a página irmã que pode ceder uma chave
Procure uma página irmã que tenha mais do que o número mínimo de chaves.
Verifique se ela pode ceder uma chave sem violar as regras da árvore.
2. Atualizar as chaves do nó pai
A chave separadora do pai (que divide os intervalos das páginas filhas) será alterada.
- Uma chave da página irmã sobe para o pai.
- A chave separadora original desce para a página que precisa de mais chaves.
3. Redistribuir as chaves entre as páginas
A página com menos chaves recebe a chave que desceu do pai.
A página irmã reduz sua quantidade de chaves, mantendo a ordem.