Algoritmo de inserção na árvore B §

---

A inserção em uma árvore B segue algumas regras importantes para garantir que a estrutura permaneça balanceada e respeite os limites do número de chaves por página.

Passo a Passo §

1. Localizar a folha onde o elemento será inserido §

A inserção sempre ocorre em uma folha, então percorra a árvore como em uma busca para encontrar a posição correta.

2. Verificar se há espaço na página §

Se a página (nó) ainda não estiver cheia (menos que chaves), insira a nova chave na posição correta, mantendo a ordem crescente.

Caso a página esteja cheia ( chaves), será necessário um processo de cisão (split).

3. Dividir a página se necessário §

Quando a página está cheia, as chaves são redistribuídas:

Divida a página em duas novas páginas.

• A chave do meio sobe para a página pai.
• Redistribua as chaves restantes entre as duas novas páginas.

4. Repetir no nível superior, se necessário §

Se a página pai também estiver cheia após receber a chave do meio, o processo de cisão continua de forma recursiva até alcançar a raiz.

Caso a raiz precise ser dividida, cria-se uma nova raiz, aumentando a altura da árvore.

Exemplo §

Imagine uma árvore B de ordem 4 (), onde cada página pode ter no máximo 3 chaves.

Árvore inicial (vazia):

[]

Inserindo as chaves: 10, 20, 30:

[10 | 20 | 30]

Inserindo a chave 40 (página cheia, precisa de cisão):

• A página está cheia.
• Dividimos:
  • A chave do meio (20) sobe para o nível superior (nova raiz).
  • As chaves restantes são distribuídas em duas páginas:

       [20]
       /   \
    [10]  [30 | 40]

Inserindo a chave 5:

• Localizamos a folha .
• Após a inserção, a página fica assim:

	       [20]
	       /   \
    [5 | 10]  [30 | 40]

Inserindo a chave 25:

• Localizamos a folha .
• Após a inserção, como há espaço, fica:

	       [20]
	       /   \
    [5 | 10]  [25 | 30 | 40]

Referências §

---

Aula 6 - Árvore B