Este trabalho não é meu...

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (505 palavras )
  • Download(s) : 0
  • Publicado : 24 de novembro de 2011
Ler documento completo
Amostra do texto
Árvores B* e B+

Prof. Flávio Humberto Cabral Nunes

Conteúdo
1. 2.

Árvores B* Árvores B+
Capítulo: 8 (APOSTILA).

Árvores B*
Um árvore B* possui as mesmas propriedades de uma árvore B,mais a seguinte propriedade:


Cada página da árvore deve conter no mínimo 2/3 de chaves

Árvores B*
Para conseguir isto, o algoritmo deve executar sempre a redistribuição de chaves entreduas páginas irmãs até ambas ficarem cheias. Somente neste caso haverá uma divisão de páginas. Mas, ao invés de duas, três páginas com 2/3 chaves serão geradas

Árvores B+
Existem várias alternativaspara implementação da árvore B original Uma delas é a árvore B+ Em uma árvore B+, todos os registros são armazenados no último nível (páginas folhas) Os níveis acima do último nível constituem umíndice cuja organização é a organização de uma árvore B

Árvores B+
Separação lógica entre o índice e os registros que constituem o arquivo

Índice
Árvore B

Acesso Sequencial

...

Registros Árvores B+
No índice só aparecem as chaves, sem nenhuma informação associada Nas páginas folhas estão todos os registros do arquivo As páginas folha são conectadas da esquerda para a direita, oque permite um acesso sequencial mais eficiente do que o acesso via índice.

Busca
A busca começa na raiz da árvore e continua até uma página folha Como todos os registros residem nas folhas, apesquisa não pára se a chave procurada for encontrada em uma página do índice


Neste caso, o apontador à direita é seguido até que uma página folha seja encontrada

Busca
Registro: 60 45

629

60 75

145

9 18 19 22

29 33

50 52

60 65 70

75 80

Inserção
Igual à operação de inserção para árvores B A única diferença é que, quando uma folha é dividida em duas, oalgoritmo promove uma cópia da chave que pertence ao registro do meio para a página pai no nível anterior, retendo o registro do meio na página folha da direita

Inserção
Registro: 17 45

6 29

60...
tracking img