Métodos de Acesso
Indice estruturado por Hash
AULA 15
Profa. Sandra de Amo
Programa de Pós-Graduação em CC - UFU
Sistemas de Banco de Dados - 2012-2
Plano Geral

Vantagens e Limitações

Hash Estático

Hash Extensível

Hash Linear

Comparação entre Hash Extensível e Linear
Vantagens e Limitações





Hash : excelente para seleção por igualdade na chave .
Não suporta seleção range (>, < )
B-Trees suportam seleção range e são quase tão boas quanto
Hash para igualdade.
Muitos SGBDs só implementam índices estruturados por BTrees
Técnica de indexação Hash é muito útil na implementação do
operador Junção, que inclu diversas seleções por igualdade
 Diferença de custo entre B-Tree e Hash é significativa
neste caso.
Hash Estático
0
h(chave) mod N
1
chave
…
…
2
h
h = função hash
N-1
Páginas Primárias dos Buckets
Entradas do tipo <chave, * >
…
Páginas de Overflow
Busca
h(x) = x
< 14, * >
0
h(14) mod 6 = 2
1
14
h
…
N=6
…
….
2 >
<14,*
3
4
5
…
Inserção
Inserindo < 7, * >
0
…
h(7) mod 6 = 1
< 7, * >
1
7
2
h
Cheia
3
4
5
…
Supressão
Suprimindo < 25, * >
0
…
h(25) mod 6 = 1
< 25, * >
1
25
2
h
3
4
5
…
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.
Desvantagens do Hash Estático

Número de buckets é fixo

Se arquivo encolhe muito, o espaço é
desperdiçado, já que os buckets são fixos.

Crescimento do arquivo produz longas
cadeias de páginas de overflow, prejudicando
performance da busca.
Alternativas

Alternativa 1 :




Periodicamente, modificar a função hash e reestruturar
todo o arquivo de modo a evitar páginas de overflow.
« Rehash » toma muito tempo
Indice não pode ser utilizado durante o processo de
« rehash ».
Alternativa 2 : Hash dinâmicos


Extensível
Linear
Hash 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.
Notação

Para procurar, inserir ou suprimir entrada k*

Aplicar h(k)

h(k) identifica um bucket

Duas chaves k1 e k2 podem ter h(k1) = h(k2)
Exemplo
Profundidade Global
Profundidade Local
2
4*
12* 32*
1*
5*
16*
Bucket A
2
2
00
21*
Bucket B
01
2
Bucket C
10*
10
2
15* 7*
11
Diretório dos
Ponteiros
19*
Páginas do Indice
Bucket D
Exemplo – inserção
2
Inserindo 13*
4*
12* 32*
1*
5*
16*
2
2
00
21* 13*
01
2
10*
10
2
15* 7*
11
Diretório
19*
Páginas do Indice
Exemplo – inserção
2
Inserindo 20*
4*
12* 32*
1*
5*
16*
2
2
00
21* 13*
01
2
10*
10
2
15* 7*
11
Diretório
19*
2
4*
12* 20*
Exemplo – Inserção
Global
Local
3
Inserindo 20*
32* 16*
Bucket A1
21* 13*
Bucket C
32
000
00
001
2
1*
010
01
011
5*
2
10*
100
10
101
Bucket C
2
110
11
111
15* 7*
Diretório
19*
Bucket D
12* 20*
Bucket A2
3
4*
Exercicio: Busca 22*, 21*, 8*
Global
Local
3
32* 16*
Bucket A1
21* 13*
Bucket C
3
000
2
001
1*
5*
010
011
2
10*
100
101
Bucket C
2
110
15* 7*
19*
Bucket D
12* 20*
Bucket A2
111
Diretório
3
4*
Análise

Se o diretório couber na memória


Seleção com igualdade : 1 I/0
Se o diretório tiver que ser armazenado em
disco

Seleção com igualdade : 2 I/0
Hash 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


Next = bucket que deve ser dividido, se necessário


Inicializado com 0
Nm = número de buckets na rodada m



Inicializado com 0
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 b
Bucket Next
a ser dividido
m = número de buckets
da rodada k
Buckets existentes
no inicio da rodada k
Bucket b + m
Imagens dos buckets divididos
Inserção de 43*
h1
h0
Nivel = 0 , N = 4 = 22
Next = 0
000
00
h0(43) = 3 (11)
32* 44* 36*
Next = 1
001
01
9*
010
10
14* 18* 10* 30*
011
11
31* 35* 7*
00
Esta informação não é
armazenada !
25* 5*
11*
44* 36*
Páginas Primárias
43*
Busca de 18*
h1
000
h0
00
Nivel = 0 , N = 4 = 22
h0(18) = 2 (10)
32*
Next = 1
001
01
9*
2 > Next
25* 5*
010
10
14* 18* 10* 30*
011
11
31* 35* 7*
100
00
44* 36*
11*
Bucket 2 não foi
dividido ainda
43*
Busca de 32* e 44*
h1
h0
000
00
Nivel = 0 , N = 4 = 22
h0(32) = 00
h0(44) = 00
32*
Next = 1
001
01
9*
0 < Next
25* 5*
Bucket 0 já foi
dividido ainda
010
10
14* 18* 10* 30*
011
11
31* 35* 7*
100
00
11*
43*
h1(32) = 000
44* 36*
Bucket 0 + 4
h1(44) = 100
Inserção de 37*
h0(37) = 01
000
00
32*
Next = 1
001
01
9*
25* 5*
010
10
14* 18* 10* 30*
011
11
31* 35* 7*
100
00
44* 36*
37*
11*
43*
Inserção de 29*
000
00
h0(29) = 01
32*
Next =1
01
9*
010
10
14* 18* 10* 30*
011
11
31* 35* 7*
100
00
44* 36*
101
01
5*
001
25* 5*
37* 29*
37*
11*
Next =2
43*
Incremento de Nível
Nivel = 1
Next =0
000
00
32*
001
01
9*
010
10
66* 18* 10* 34*
011
11
43*
31* 35* 7*
11* 11*
100
00
44* 36*
101
01
5*
110
10
14* 30* 22*
111
11
31* 7*
h0(50) = 10
25*
37* 29*
h1(50) = 010
50*
Next =3
43*