Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Árvores B+

Apresentação para a disciplina de Programação II - IFSul 2013
by

Wilian Chaves

on 20 January 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Árvores B+

1 Localizar a folha dentro da qual a chave deve ser inserida;
Caso 1 : A chave X aparece apenas em um nó folha.
A chave X é simplesmente removida e a folha é reorganizada.
Duas folhas são chamadas irmãos adjacentes se têm o mesmo pai e são apontadas por ponteiros adjacentes.
Árvores B+
Wilian Chaves
Apresentação e estrutura
Características
Definição
Estrutura
Algoritmos - Busca e inserção
Operações de busca
Operação de inserção
Inserção
Inserção
Algoritmos - remoção
Remoção
Remoção
Remoção com concatenação
IFsul-Programação II
Os nós internos de uma árvore B+ formam um
conjunto de índices
.
Referências a dados (chaves) são feitas somente a partir das
folhas
Folhas são ligadas, oferecendo um caminho seqüencial para percorrer as chaves
Folhas armazenam chaves, um ponteiro
para a próxima folha e um
contador de chaves
Cada nó não folha tem entre n/2 e n filhos
Utilização
Bancos de Dados, como SQL Server e Oracle.
Sistemas de arquivos como o NTFS para o Windows, ReiserFS para Unix, o XFS para IRIX e Linux, e o JFS2 para AIX, OS/2 e Linux.
Vantagens
Forma de uma árvore balanceada na qual todo caminho da raiz até uma folha tem o mesmo tamanho.
Não é necessário manter nenhum ponteiro de registro em nós não - folha.
Nós internos armazenam chaves, ponteiros e um contador de chaves
Todas as folhas aparecem no mesmo nível;
Um nó não folha com k filhos contém k - 1 chaves
Menos operações de E/S são necessárias durante a busca
Exemplo de árvore B+ ordem 3
Não é necessário subir e descer na árvore para acessar sequencialmente os registros.
Desvantagens
Sobrecarrega o desempenho na inserção e exclusão – aceitável para arquivos modificados frequentemente pois evita o custo da reorganização do arquivo.
Aumenta o espaço adicional – torna-se também aceitável por causa dos benefícios de desempenho que a estrutura oferece.
Como não há mudança na estrutura durante a busca, basta fazer as comparações do valor buscado com o índice, até chegar na folha onde está o dado.
2 Localizar a posição de inserção dentro da folha ;
3 Inserir a chave;
4 Se, após a inserção, a folha estiver completa, realizar a cisão da página.
Exemplo usando a sequência
80 – 50 – 98 – 90 – 60 – 65 – 70 – 55 – 64.
Inclusão do 60 implica em estouro do nó 50|80 e provoca o encaminhamento do 60 para o nó ascendente (índice) e a cisão da folha.
A inserção de 55 causa o estouro da primeira folha, sua cisão em duas e a cópia de 55 para o índice
Inserção
Inserção
A inserção de 64 provoca o estouro do nó 65||70 e o encaminhamento de 65 ao nó ascendente que, por sua vez, implica no estouro do nó 55||60||70||80 e consequente encaminhamento de 65 ao nível ascendente, com crescimento da estrutura.
Inserção
Caso 2 : A chave X aparece também em nós internos (índice)
A chave X é removida; A folha é reorganizada;
A chave X
não
é removida dos nós internos.
Quando uma chave é retirada de um nó
folha, o número de chaves restantes pode
ser menor que n/2. O que fazer?
Tratamentos:
• Concatenação
• Redistribuição
Elas podem ser concatenadas se são irmãos adjacentes e, juntas, possuem menos de n-1 chaves.
A concatenação agrupa as chaves de duas folhas em uma só
No nó pai deixa de existir uma entrada: aquela da chave que se encontra entre os ponteiros para cada uma das folhas concatenadas. Essa chave é simplesmente removida do nó pai.
Remoção com concatenação
Como foi retirada uma chave do nó pai, caso ele passe a ter menos de (n-1)/2 chaves, o processo se repete - ou seja, a concatenação é um processo propagável;
Se a propagação atingir a raiz, a
árvore diminuirá de altura.
Remoção com Redistribuição
Se uma folha e seu irmão adjacente possuem em conjunto n-1 ou mais chaves, estas podem ser equilibradamente distribuídas:
1 Concatena-se os dois irmãos
2 Efetua-se a cisão da página resultante
Remoção com redistribuiçaõ
A inserção de 70 causa o estouro da folha, cisão e encaminhamento do 70 ao nó superior
Referências
http://en.wikipedia.org/wiki/B%2B_tree
http://marciobueno.com/arquivos/ensino/ed2/ED2_04_Arvore_B+.pdf
http://www.othonbatista.com/arquivos/unifacs/estrutura-dados-2/aulas/aula-arvore-b+.pdf
Muito Obrigado!
Full transcript