Arvore B+

Árvore B+

Árvore B+
• Estrutura de dados mais usada para a criação de índices
• Estrutura de dados que se ajusta facilmente a inserção e deleção de elementos
• É uma árvore balanceada
• Os nós folhas (dados) são ligados ordenadamente via uma lista duplamente ligada Principais características
• Ocupação de pelo menos 50%
• Nós folhas com m+1 ponteiros (exceto a raiz)
• Exemplo:

Busca: 5* e 15*

• 5 encontrado na árvore
• 15 não encontrado

Inserção
•

Passos:
1. Encontrar a folha em que o dado deva ser inserido
2. Se a folha não estiver cheia, adicionar o dado na folha. Senão, é necessário dividir a folha em duas partes. •

A operação de inserção pode resultar em aumento de largura da árvore (novos nós fulhas criados) ou aumento de altura.

Inserção: 8*

Redistribuição entre folhas
• Inserir o número 8:

Redistribuição entre folhas irmãs • Se uma folha está cheia, pode-se adicionar em uma das folhas irmãs (tem que ter o mesmo pai!). • Ajuste no pai, recursivamente, pode ser necessário. Remoção: 19* e 20*
Redistribuição

Remoção: 24
Junção não folha

Remoção: 24*
Junção na folha

Remoção – Junção na folha Criando índices
• Criar índices com base na inserção de dados na árvore B+ é muito custoso.
• Existe um algoritmo chamado “Bulk Loading”
• Os passos para a criação do índice são:
1 – Ordene os dados
2 – Crie uma entrada vazia para a raíz da árvore.
3 – Adicione o primeiro bloco na raiz da árvore

Criando índice
4 – Faça isso até completar o nó raíz

Criando índice
5 - Assim que completar o nó raíz é necessário fazer a divisão (split)

Criando índice
6 - Depois do split, a inserção continua sempre com o nó mais a direita.

Criando índice