Upload
internet
View
105
Download
0
Embed Size (px)
Citation preview
Revisão Prova 2Métodos de Acesso – Parte 2
AULA 21 Profa. Sandra de Amo
GBC053 – BCC
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*