Algoritmos/Estruturas de dados/Arvore B+

Árvore B+

A Árvore B+ é uma estrutura de dados em que todas as chaves estão armazenadas nas folhas. Cada folha aponta para a próxima folha, o que permite uma facilidade na leitura sequencial. Sua estrutura se assemelha bastante com a Árvore B possuindo as mesmas características de ocupação da árvore, níveis das folhas e números de filhos.

Inclusão na Árvore B+:

• mesmas regras da Árvore B
• caso ocorra divisão da página, a chave deve ser mantida na folha e copiada para cima (divide se a página ao meio e sobe o menor valor criado da nova página da direita)

Remoção da Árvore B+:

• mesmas regras da Árvore B
• as chaves removidas das folhas não precisam ser removidas das demais páginas (nó pai)

Vamos ver um exemplo de inserção em uma Árvore B+ de ordem 5, dos números:

22, 89, 49, 31, 25, 37, 85, 39, 90, 68, 46, 53, 69, 29, 40

Inserção dos números 22, 89, 49, 31 e 25 na árvore B+

Inserção dos números 37, 85 e 39 na árvore B+

Inserção dos números 90 e 68 na árvore B+

Inserção dos números 46, 53 e 69 na árvore B+

Inserção do número 40 na árvore B+