Aula 7_Arvore B-estrela

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Árvores B*
Lívia N. Andrade
Introdução
Nas árvores B, no pior caso, 50% do espaço de armazenamento não é utilizado (espaço desperdiçado).
Yao (1978) realizou análises e simulações que indicaram que, depois de uma grande sequência de inserções e remoções aleatórias, uma árvore B estará aproximadamente 69% ocupada. 
Após isso, as modificações nesse percentual de ocupação são muito pequenas.
Desperdício de espaço de armazenamento pode ser grande se o tamanho das páginas for também grande.
Mesmo com esse percentual, o desperdício de espaço de armazenamento...
2
Introdução
A árvore B* melhora o percentual de ocupação de espaço de armazenamento das árvore B.
Isso, porque nas árvore B* as páginas, exceto a raiz, devem permanecer preenchidas.
 
23
Uma maneira de melhorar esse percentual de ocupação são as árvores B*
3
Árvores B* - Características
A frequência de divisões nas páginas da árvore B* é diminuída, porque quando uma página folha está totalmente preenchida, tenta-se inserir o item de dados em uma página vizinha.
Se a página vizinha também estiver totalmente preenchida, então as duas páginas folha se tornam três páginas folhas.
Os registros das duas páginas são distribuídos homogeneamente em três páginas.
Dois registros adequados passam a compor a página pai dessas páginas.
Este processo é valido para todas as páginas da árvore B*
4
Exemplo 1 - Árvores B*
25
10 20 21 
Insira a chave 50 na árvore B* abaixo.
28 30 40 
Página folha tem espaço para armazenar a chave
Este processo é valido para todas as páginas da árvore B*
5
Exemplo 1 - Árvores B*
25
10 20 21 
Insira a chave 50 na árvore B* abaixo.
28 30 40 50 
25
10 20 21 
28 30 40 
Este processo é valido para todas as páginas da árvore B*
6
Exemplo 2 - Árvores B*
25
10 20 21 
Insira a chave 60 na árvore B* abaixo.
28 30 40 50 
Página folha está totalmente preenchida, porém a página vizinha tem espaço para receber um elemento.
Este processo é valido para todas as páginas da árvore B*
7
Exemplo 2 - Árvores B*
25
10 20 21 
Insira a chave 60 na árvore B* abaixo.
28 30 40 50 
Este processo é valido para todas as páginas da árvore B*
8
Exemplo 2 - Árvores B*
25
10 20 21 
Insira a chave 60 na árvore B* abaixo.
28 30 40 50 
28
10 20 21 25 
30 40 50 60
Este processo é valido para todas as páginas da árvore B*
9
Exemplo 3 - Árvores B*
28
10 20 21 25
Insira a chave 70 na árvore B* abaixo.
30 40 50 60
Página vizinha totalmente preenchida!!!
As duas páginas se tornam três páginas folhas
Este processo é valido para todas as páginas da árvore B*
10
Exemplo 3 - Árvores B*
28
10 20 21 25
Insira a chave 70 na árvore B* abaixo.
30 40 50 60
28
10 20 21 25 
30 40 50 60
70
A distribuição dos registros nas páginas folha depende da implementação.
Este processo é valido para todas as páginas da árvore B*
11
Exemplo 3 - Árvores B*
28
10 20 21 25
Insira a chave 70 na árvore B* abaixo.
30 40 50 60
25 50
10 20 21 
60 70
28 30 40 
Páginas com 3 registros
Este processo é valido para todas as páginas da árvore B*
12
Exemplo 3 - Árvores B*
28
10 20 21 25
Insira a chave 70 na árvore B* abaixo.
30 40 50 60
25 40
10 20 21 
50 60 70
28 30 
Páginas com 3 registros
Este processo é valido para todas as páginas da árvore B*
13
Árvores B* - Características
Considere uma remoção em uma página i de uma árvore B*:
Se a página i ficar com menos que de ocupação, então tenta-se mover um registro de até duas páginas vizinhas de i.
Se ambos os vizinhos de i também ficarem com menos que de ocupação, se cada um deles perder um item de dados, então três páginas são consideradas para que se tornem duas páginas, se houver quantidade de itens de registros para que isso ocorra.
23
23
14
Exemplo 4 - Árvores B*
Remover a chave 60 na árvore B* abaixo.
28
10 20 21 25
30 40 50 60
Este processo é valido para todas as páginas da árvore B*
15
Exemplo 4 - Árvores B*
Remover a chave 60 na árvore B* abaixo.
28
10 20 21 25
30 40 50 60
28
10 20 21 25
30 40 50 
Este processo é valido para todas as páginas da árvore B*
16
Exemplo 5 - Árvores B*
Remover a chave 50 na árvore B* abaixo.
28
10 20 21 25
30 40 50 
Este processo é valido para todas as páginas da árvore B*
17
Exemplo 5 - Árvores B*
Remover a chave 50 na árvore B* abaixo.
28
10 20 21 25
30 40 50 
28
10 20 21 25
30 40 
Página ficou com menos de de ocupação
23
Este processo é valido para todas as páginas da árvore B*
18
Exemplo 5 - Árvores B*
A árvore é rearranjada
28
10 20 21 25
30 40 
Porém, a página vizinha tinha mais chaves que o mínimo exigido.
25
10 20 21 
28 30 40
Este processo é valido para todas as páginas da árvore B*
19
Exemplo 6 - Árvores B*
Remover a chave 70 na árvore B* abaixo.
25 50
10 20 21 
60 70
28 30 40 
25 50
10 20 21 
60
28 30 40 
Página ficou com menos de de ocupação
23
Este processo é valido para todas as páginas da árvore B*
20
Exemplo 6 - Árvores B*
As páginas vizinhas tinham o mínimo permitido, e com esta quantidade era possível transformar as três páginas em duas páginas
28
10 20 21 25 
30 40 50 60 
25 50
10 20 21 
60
28 30 40 
Este processo é valido para todas as páginas da árvore B*
21
Comparação
Situações
Árvore B
Árvore B*
Ocupação mínimadas páginas
Inserção em uma página totalmente preenchida
Apágina é divida em duas páginas
Tenta-se inserir uma chave napáginavizinha. Se a página vizinha estiver cheia, então as duas páginas são transformadasem três páginas
Ocupação médias das páginas
69%
81%
Remoção de uma chave, tornando o número de chaves menor do que o mínimo permitido na página
Se a página vizinha tiver mais chaves que o mínimo exigido, ela empresta uma chave para a página que está com menos. Senão, as duas páginas são transformadasem uma
Se a página vizinha tiver mais chaves que o mínimo exigido, ela empresta uma chave para a página que está com menos, isso pode ser feito com a página vizinha da página vizinha. Se astrespáginas estiveremcom apenas ominimoexigido, são transformadas em duas páginas.
23
12
22
Operações em Árvore B*
Pesquisa
Inserção
Remoção
23
Exercício de Inserção
Inserir as seguintes chaves em um árvore B* de ordem 2: 
20, 10, 40, 50, 30, 55, 3, 11, 4, 28, 36, 33, 52, 17, 25, 13, 45, 9, 43, 8 e 48.
10 20 30 45
33 36 40 43
25 28
11 13 17
 3 4 8 9
48 50 52 55
24
Exercício de Exclusão 
Remover as chaves 50, 33, 45, 3, 11, 28, 10, 55, 48, 36, 25, 40.
10 20 33 45
36 40 43
25 28 30
11 13 17
 3 4 8 9
48 50 52 55
25
Referências Utilizadas
Livro:
	
ZIVIANI, Nivio, Projeto de algoritmos com implementação em Pascal e C, 3a. edição, Editora Thomson, 2011
Notas de aula da disciplina, disponível no Moodle.
26