Este trabalho não é meu...

Á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 entre duas 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 alternativas para 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, o que 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, a pesquisa 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

6 29

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, o algoritmo 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