Algoritmos/Estruturas de dados/Arvore B+

Origem: Wikilivros, livros abertos por um mundo aberto.
Saltar para a navegação Saltar para a pesquisa

Árvore B+[editar | editar código-fonte]

A Árvore B+[1] é 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+:[2]

  • 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+:[2]

  • 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+

Bibliografia[editar | editar código-fonte]

[2] [1]

  1. 1,0 1,1 KUTOVA, Marcos. Algoritmos e Estrutura de Dados III (Apostila)
  2. 2,0 2,1 2,2 KUTOVA, Marcos. Vídeo-aulas disponiveís em Puc Minas Virtual, 2017