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

Trabalho Árvores B* e B+

No description
by

william gomes

on 10 June 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Trabalho Árvores B* e B+

Trabalho Arvores B* e B+
Relembrando
Conceitos
E o que difere da Árvore B?
Mais sobre árvore B+
O que é Árvore?

Altura da Árvore
Grade
Bloco
Ordem
Árvore Multipla
Onde iremos utilizar e tirar o máximo de seu proveito?
Árvores B*
Variante de Árvore B;
Possui um processo de subdivisão;
Proposta por Knuth em 1973;
cada nó contém, no mínimo, 2/3 do número máximo de chaves;
Posterga o split;

Árvore B*
Possui o mínimo de chave;
Se adia a subdivisão, até que 2 chaves estejam cheias;
Na sequencia, se realiza a divisão de 2 em três chaves(Na árvore B, é feita de 1/2, aqui, de 2/3).
Problemas
Mudança na taxa de ocupação:
Particionamento da raiz, pode trazer um problema:
Se raiz não possui nó irmão
Soluções
Dividir a raiz usando a divisão convencional (1-to-2 split);
Ou permitir que a raiz seja maior
Árvores B+
Nada mais é que uma variação da estrutura básica da árvore B.
A árvore B+ foi proposta por Knuth e grande parte da literatura sobre ela é encontrada em forma de artigos. Possível assim, organizar um arquivo de maneira que o processamento sequencial e aleatório de chaves.
Características
Todas as chaves são mantidas em folhas;
As chaves são repetidas em nós não-folha formando assim um índice;
As folhas são ligadas oferecendo um caminho sequencial para recorrer as chaves;
Vantagens
-Mantem eficiência da busca e da inserção da arvore B;
-Aumenta a eficiência da localização do próximo registro na arvore de um ponto a outro;
- Mecanismo para percorrer seqüencialmente o arquivo de registros de dados sem que seja necessário visitar toda a árvore.
- Evita armazenagem redundante;
Desvantagens
-Nós não folha maiores e dificulta o gerenciamento de índices;
-Inserção de registros pode provocar overflow em um bloco;
-Remoção de registros pode provocar
underflow em um bloco;
Soluções
Podemos dividir o bloco, em um processo análogo ao realizado em árvores-B;
Concatenar o bloco com o seu antecessor ou sucessor na seqüência lógica
Redistribuir os registros, movendo-os entre blocos logicamente adjacentes
Mas, para que serve árvore-B?
Exercício
Busca
A busca começa na raiz da árvore e continua até uma página folha. Dessa forma quando buscamos uma chave k, percorremos a árvore de cima para baixo carregando as páginas, selecionamos a página apontada pelo ponteiro e caso uma cópia de k esteja numa página interna devemos carregar a página à direita de k. Encontrado uma página folha o algoritmo deve buscar k nesta e responder se ela se encontra ou não.
Inserção
O primeiro caso Página folha incompleta: Apenas inserimos a chave de maneira a manter a ordenação
das chaves.
A segunda Página folha completa: A página folha em questão deve sofrer uma operação de split. Tal
operação cria uma nova página em arquivo dividindo
as chaves entre a nova página e a anterior.

Mais simples do que a remoção de uma árvore B.
O registro a ser removido reside sempre em uma
página folha, o que torna sua remoção simples.
Não há necessidade de utilização do procedimento
para localizar a chave antecessora.
Remoção
-Mantem eficiência da busca e da inserção
da árvore B;
-Aumenta a eficiência da localização do próximo registro na arvore de um ponto a outro;
-Não e necessário manter nenhum ponteiro de registro em nós não-folha.
-Podemos utilizar uma Árvore B+ em muitos Bancos de Dados como o SQL Server e Oracle;

Considere o conjunto de chaves 1, 2, 3, 4, 5,
6, 7, 8, 9, 10, 11, 12, 13. Faça a inserção numa
Árvore-B+ de modo que a árvore resultante
tenha três níveis.
Exercício:
Link's e Bibliografia
http://www.dcc.fc.up.pt/~michel/BD0304/Slides6.pdf
http://www.ic.unicamp.br/~zanoni/mo637/aulas/arvoresB.pdf
http://marciobueno.com/arquivos/ensino/ed2/ED2_04_Arvore_B+.pdf
http://pt.wikipedia.org/wiki/%C3%81rvore_B%2B
www.cin.ufpe.br/~tg/2001-1/mctn.doc
Estrutura de Dados e Algoritmos em C++, Drozdek, Adam
ISBN: 85-2210-295-3
"As arvores morrem de pé!"
(Ditado popular).
Está é uma árvore B*? Por que?
Full transcript