View
105
Download
0
Category
Preview:
Citation preview
Revisão Prova 2Métodos de Acesso:
BTree e Hash
AULA 20 Profa. Sandra de Amo
GBC053 – BCC2013-1
Discussão
Implementação dos operadores de SQL Técnicas usando Ordenação (Externa !)
Projeção – Junção - Conjuntos Técnicas usando Particionamento
Projeção – Junção – Conjuntos Técnicas usando Indice
Seleção Junção
REVISÃO – BTREE
Inserção: se nó onde deveria ocorrer a inserção já está cheio Variante 1 : Se nó está cheio divida e ajuste os nós
ancestrais. Variante 2 : Testa primeiro se pode redistrisbuir
num nó vizinho. Em caso negativo, divide.
Ideal Nós intermediários: sempre dividir, não redistribuir Nós Folha: procure redistribuir entre os vizinhos
Se tiver espaço no vizinho direito, redistribua. Caso contrário, verifica se tem espaço no
vizinho esquerdo, e redistribua Caso contrário: divida a folha cheia.
Inserção : Testando vizinho à direita
13 17 24 30
7*5* 14*16* 19*20* 22* 24*27*29* 33*34* 39*38*
Inserindo 6*
6*
14* 16*2* 3*
CHEIA !!
Inserção : Testando vizinho à direita
13 17 24 30
7*5* 14*16* 19*20* 22* 24*27*29* 33*34* 39*38*
Inserindo 6*
14*16*2* 3*
7*5*2* 3* 6*
Inserção : Testando vizinho à direita
13 17 24 30
5* 14*16* 19*20* 22* 24*27*29* 33*34* 39*38*
Inserindo 6*
14*16*2* 3*
7*5*2* 3* 6*
7*
7*
6*
Inserção : Testando vizinho à esquerda
8 17 24 30
7*5* 14*16* 19*20* 22* 24*27*29* 33*34* 39*38*
Inserindo 35*
8* 14* 16*2* 3*
33*34* 39*38*35*
Inserção : Testando vizinho à esquerda
8 17 24
7*5* 14*16* 19*20* 22* 24*27*29* 33* 35* 39*38*
Inserindo 35*
8* 14* 16*2* 3* 34*
34
Inserção : Vizinhos estão cheios Divisão da Folha
13 17 24 30
2* 3* 7*5* 13*14* 19*20* 22* 24*27*29* 33*34* 39*38*
Inserindo 8*
Cheia !
7* 8*55*
Cheia !
15*16*
2* 3* 7*5* 8*
Divisão de nós intermediários
13 17 24 305
2* 3* 7*5* 13*14* 19*20* 22* 24*27*29* 33*34* 39*38*7* 8*55* 15*16*
Divisão de nó intermediário
13 24 305
17
2* 3* 7*5* 14*16* 19*20* 22* 24*27*29* 33*34* 39*38*7* 8*55*
Deleção
Se ocupação não fica abaixo do mínimo, deleta, não altera ponteiros, nem nós ancestrais
Se ocupação fica abaixo do mínimo Tenta redistribuição com nó vizinho, se
possível Caso contrário junta com vizinho à direita
ou à esquerda (caso for o último nó).
Exemplo: Deleção
2* 3* 14*16* 19* 20*22* 24* 27* 29* 33*34* 39*38*
Removendo 19*
7* 8*5*
5 13 24 30
17
Deleção: Redistribuição nas folhas Com nó direito
Removendo 20*
5 13 24 30
17
2* 3* 14*16* 20* 22* 24* 27* 29* 33*34* 39*38*7* 8*5*
Deleção: Redistribuição nas folhas Com nó direito
Removendo 20*
5 13 27 30
17
2* 3* 14*16* 24* 27* 29* 33*34* 39*38*7* 8*5*
24
22*
Deleção: Redistribuição nas folhas Com nó esquerdo
Removendo 33*
5 13 30
17
2* 3* 14*16* 22* 24* 27* 29* 33*7* 8*5*
24
35*
Deleção: Redistribuição nas folhas Com nó esquerdo
Removendo 33*
5 13 30
17
2* 3* 14*16* 22* 24* 27*7* 8*5*
24
35*29*
29
Discussão
Distribuição nas folhas vizinhas não acarreta mudança - redução de ocupação dos nós pais
Portanto: Nós pais não ficam abaixo da ocupação mínima Não precisam ser juntados nem redistribuídos entre
seus vizinhos Não há redução da altura da árvore Modificações não se propagam para nós acima do nó-
pai
Deleção: Juntando FolhasCom nó à direita
2* 3* 14* 15* 22* 33*34* 39*38*
Removendo 24*
7* 8*5*
5 13 30
17
24*
27
27*29*22* 27* 29*
Não dá para redistribuir os vizinhosTamanho do vizinho direito = dVizinho à esquerda tem pai diferente
JUNTA COM O VIZINHO DA DIREITA
16*
40
Deleção: Juntando FolhasCom nó à direita
33*34* 39*38*
Removendo 24*
5 13 30
17
24*
27
27*22* 27* 29*
27
Quase vazia ! Não dá para distribuircom vizinho
30
2* 3* 14* 15*7* 8*5* 16*
17 40
Junção de nós intermediários
2* 3* 14* 16* 33*34* 39*38*7* 8*5*
30
24*
27
27*22* 27* 29*
305 13 30 3027305 13 30
Removendo 24* 1717 40
Deleção: Juntando FolhasCom nó à esquerda
2* 3* 14* 16* 49*50*
Removendo 16*
7*5*
5 13 60
45
45*46*
47
63* 65*
Deleção: Juntando FolhasCom nó à esquerda
2* 3* 14* 16* 49*50*
Removendo 16*
7*5*
5 13 60
45
45*46*
47
63* 65*
Deleção: Juntando FolhasCom nó à esquerda
2* 3* 14* 49*50*
Removendo 16*
7*5*
5 13 60
45
45*46*
47
63* 65*
Deleção: Juntando FolhasCom nó à esquerda
2* 3* 49*50*
Removendo 16*
7*5*
5 13 60
45
45*46*
47
63* 65*7* 14*5*
Deleção: Juntando FolhasCom nó à esquerda
2* 3* 49*50*
Removendo 16*
7*5*
5 60
45
45*46*
47
63* 65*14*
Devem ser juntadas
Deleção: Juntando FolhasCom nó à esquerda
2* 3* 49*50*
Removendo 16*
7*5*
5
45
45*46* 63* 65*14*
47 60
Redistribuição em nós intermediários
13 1755 13 27 30
22
17 20
2* 3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 24* 29*27* 33* 34* 38* 39*
Removendo 24* : Não existe possibilidade de juntar nós intermediários
Redistribuição em nós intermediários
13 1755 13 30
22
17 20
2* 3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 29*27* 33* 34* 38* 39*
Quase vazia
Redistribuição em nós intermediários
13 1755 13 30
22
17 20
2* 3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 29*27* 33* 34* 38* 39*
Redistribuição em nós intermediários
13 1755 13 13 17520 3017
22
3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 29*27* 33* 34* 38* 39*
REVISÃO – BULK LOADING
Exemplo
3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44*
Páginas restantes a alocar
Ordem da b-tree = 1
Exemplo
3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44*
Ordem da b-tree = 16* 10*
Páginas restantes a alocar
Exemplo
3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44*
6* 10* 12*
Precisa dividir
20*
Exemplo
3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44*
6* 12*10* 20*
Páginas restantes a alocar
Exemplo
3* 4* 6* 9* 10* 11* 12* 13* 22* 31* 35* 36* 38* 41* 44*
6* 12*
10*
20*
20*
23*
23*
Precisa dividir
35*
Exemplo
3* 4* 6* 9* 10* 11* 12* 13* 22* 31* 35* 36* 38* 41* 44*
6* 12*
10*
20*
23*
23*
20*
35*
Páginas restantes a alocar
Exemplo
3* 4* 6* 9* 10* 11* 12* 13* 22* 31* 35* 36* 38* 41* 44*
6* 12*
10*
20*
23*
23*
20*
35* 38* 44*
Precisa dividir
Exemplo
3* 4* 6* 9* 10* 11* 12* 13* 22* 31* 35* 36* 38* 41* 44*
6* 12*
10*
20*
23*
23*
20*
38* 44*
35*
Precisa dividir
Exemplo
3* 4* 6* 9* 10* 11* 12* 13* 22* 31* 35* 36* 38* 41* 44*
6* 12*
10*
20*
23*
23*
38* 44*
35*
20*
Exemplo:Entrada: Arquivo de indice de 9 páginas com 4 registros em cada uma. d = 2, k = 0, x = 1Saída: (3, <B0,B1,B2>) B0 = 18 páginas (folhas em amarelo) contendo 2 (= d + k) registros em cada uma B1 = Nível 1 da Btree = 5 páginas (azuis) de 3 (= d + x) registros cada (exceto a última) B2 = Nível 2 da Btree (raiz) = 1 página com 4 registros
Exemplo:Entrada: Arquivo de indice de 9 páginas com 4 registros em cada uma. d = 2, k = 0, x = 1Saída: (3, <B0,B1,B2>) B0 = 18 páginas (folhas em amarelo) contendo 2 (= d + k) registros em cada uma B1 = Nível 1 da Btree = 5 páginas (azuis) de 3 (= d + x) registros cada (exceto a última) B2 = Nível 2 da Btree (raiz) = 1 página com 4 registros
REVISÃO – HASH
Hash Estático
Função Hash não se altera Caso um bucket fique cheio cria-se páginas
de overflow para este bucket que ficou cheio.
Alguns buckets podem concentrar muito mais páginas que outros buckets.
Inserção
0
1
2
5
h
h(7) mod 6 = 1
7
…
…Inserindo < 7, * >
4
3
< 7, * >
Cheia
Supressão
0
1
2
5
h
h(25) mod 6 = 1
25
…
…Suprimindo < 25, * >
4
3
< 25, * >
Função Hash
Componente importante da técnica hash
Deve distribuir valores das chaves de maneira uniforme nos buckets.
Número de buckets = N = parâmetro
h(x) = a*x + b , a, b : parâmetros de ajuste
Custos
Páginas primárias do índice podem ser armazenadas em páginas de disco sucessivas.
Caso não haja overflow Busca no índice requer 1 I/O Inserção e Supressão requerem 2 I/O
Custo pode ser alto se existem muitas páginas de overflow.
Estratégia : criar inicialmente os buckets deixando 20% de área livre em cada um.
Hash (dinâmico) Extensível
Solução 1 : quando algum bucket ficar cheio Dobrar o número de buckets Distribuir as entradas nos novos buckets Defeito : o arquivo todo deve ser lido e reorganizado
e o dobro de páginas devem ser escritas. Espaço em alguns buckets é alocado bem antes de
sua utilização efetiva. Solução 2 : utilizar um diretório de ponteiros para
os buckets. Dobrar o número de entradas no diretório Separar somente os buckets que ficaram cheios.
Exemplo
00
01
10
11
2
Diretório dos Ponteiros
Profundidade Global
4* 12* 32* 16*
2
1* 5* 21*
2
10*
2
15* 7* 19*
2
Bucket A
Bucket B
Bucket C
Bucket D
Páginas do Indice
Profundidade Local
Exemplo – inserção
00
01
10
11
2
Diretório
4* 12* 32* 16*
2
1* 5* 21*
2
10*
2
15* 7* 19*
2
Páginas do Indice
Inserindo 13*
13*
Exemplo – inserção
00
01
10
11
2
Diretório
4* 12* 32* 16*
2
1* 5* 21*
2
10*
2
15* 7* 19*
2
Inserindo 20*
13*
4* 12* 20*
2
32* 16*
2
Exemplo – Inserção
00
01
10
11
2
Diretório
1* 5* 21*
2
10*
2
15* 7* 19*
2
Inserindo 20*
13*
4* 12* 20*
3
32* 16*
3
000
001
010
011
100
101
110
111
3
GlobalLocal
Bucket A1
Bucket A2
Bucket D
Bucket C
Bucket C
Exercicio: Busca 22*, 21*, 8*
Diretório
1* 5* 21*
2
10*
2
15* 7* 19*
2
13*
4* 12* 20*
3
32* 16*
3
000
001
010
011
100
101
110
111
3
Global
Bucket A1
Bucket A2
Bucket D
Bucket C
Bucket C
Local
Hash (Dinâmico) Linear
Assim como o Hash Extensível, o Hash Linear é ideal para inserções e supressões;
Vantagem sobre extensível Lida muito bem com colisões Oferece muita flexibilidade
Cadeias de overflow podem tornar o hash linear inferior em performance ao hash extensivel
Parâmetros e Contadores
Nivel = indica a rodada atual Inicializado com 0
Next = bucket que deve ser dividido, se necessário Inicializado com 0
Nm = número de buckets na rodada m N0 = N Nm = N*2m
Somente o bucket com número Next é dividido. Usa-se páginas de overflow para os outros buckets,
se ficarem cheios. Após divisão, Next é incrementado.
Esquema Geral : rodada k
Bucket Nexta ser dividido
Imagens dos buckets divididos
Bucket b
Bucket b + m
Buckets existentesno inicio da rodada k
m = número de buckets da rodada k
32* 44* 36*
9* 25* 5*
14*
31* 35* 7*
18* 10* 30*
11*
Páginas Primárias
Nivel = 0 , N = 4 = 22
Next = 0h0h1
00
01
10
11
000
001
010
011
Esta informação não é armazenada !
Inserção de 43*
h0(43) = 3 (11)
43*
Next = 1
44* 36*00
32*
9* 25* 5*
14*
31* 35* 7*
18* 10* 30*
11*
Nivel = 0 , N = 4 = 22h0h1
00
01
10
11
000
001
010
011
Busca de 18*
h0(18) = 2 (10)
43*
Next = 1
44* 36*00
2 > Next
Bucket 2 não foi dividido ainda
100
32*
9* 25* 5*
14*
31* 35* 7*
18* 10* 30*
11*
Nivel = 0 , N = 4 = 22h0h1
00
01
10
11
000
001
010
011
Busca de 32* e 44*h0(32) = 00
43*
Next = 1
44* 36*00
0 < Next
Bucket 0 já foi dividido ainda
h0(44) = 00
h1(32) = 000
h1(44) = 100Bucket 0 + 4
100
Inserção de 37*
32*
9* 25* 5*
14*
31* 35* 7*
18* 10* 30*
11*
00
01
10
11
000
001
010
011 43*
Next = 1
44* 36*00100
h0(37) = 01
37*
Inserção de 29*32*
9* 25* 5*
14*
31* 35* 7*
18* 10* 30*
11*
00
01
10
11
000
001
010
011 43*
Next =1
44* 36*00100
h0(29) = 01
37*
5* 37* 29*01101
Next =2
Incremento de Nível32*
9* 25*
66*
31* 35* 7*
18* 10* 34*
11*
00
01
10
11
000
001
010
011 43*
44* 36*00100
h0(50) = 10
5* 37* 29*01101
14* 30* 22*10110
h1(50) = 010
50*Next =3
Next =0Nivel = 1
31*111 11 7*
43* 11*
Recommended