Organização de Arquivos
Cálculo de Custos de I/O
Arquivos Hashed
AULA 7 – Parte I
Profa. Sandra de Amo
GBC053 – BCC
Lembrando:

Páginas do arquivo são agrupadas por buckets
Bucket 1

Bucket 2
Bucket 3
Bucket é determinado aplicando-se uma função h ao campo de procura
Exemplo: estamos procurando todos os empregados de salário = 5000
Como encontrá-los rapidamente ?
Arquivo organizado por hash no campo Salário
Função hash: mod 3
Onde estão os registros dos empregados com salário = 5000 ?
5000 mod 3 = 2
Resposta: bucket 2
Resumindo:
 Páginas no arquivo são agrupadas por
buckets
 Bucket é determinado aplicando-se uma
função h ao campo de busca
 Insert : registro é inserido no bucket
apropriado
Importante :
 No caso de Arquivos Hashed,

“chave” = chave de busca na qual é aplicada
a função Hash.

Nada a ver com chave primária ou candidata.
Arquivos Hashed
 Hash Estático
 Procura de um registro satisfazendo uma condição no campo de
procura
 Aplica-se função hash no campo de procura
 Varre-se todas as páginas do bucket correspondente
 Processo demorado se o bucket contiver muitas páginas
 Hash Dinâmico
 Especifica-se um número máximo de páginas por bucket
 Inserção pode causar overflow num bucket
 Função hash é adaptada dinamicamente para evitar overflow
 Hipótese que faremos na estimativa de custos:
 não há overflow de páginas num bucket – cada bucket não
ultrapassa um número máximo de páginas.
Arquivos Hashed : SCAN
 Scan

Páginas são ocupadas em 80%
Assim: um arquivo de 100 páginas, caso for organizado em hash,
vai necessitar de 100/0.80 páginas para seu armazenamento =
= 125 páginas !!
Espaço livre é deixado nas páginas para evitar overflow no bucket

Custo = B(D+RC)/0.80 = 1.25*B(D+RC)


Bucket 1
Bucket 2
Bucket 3
Arquivos Hashed : Busca
Seleção A = a
A : atributo chave (chave do HASH )


Tempo para identificar a página contendo o
registro = H = tempo de cálculo da função
hash
Assumindo 1 única página no bucket
Custo = H + D + RC
Arquivos Hashed : Busca
Seleção A = a
A : atributo não é chave do HASH


Todo o arquivo deve ser procurado
Custo = 1.25B(D+RC)
Seleção A > a


Todo o arquivo deve ser procurado
Custo = 1.25B(D+RC)
Arquivos Hashed : Inserção/Deleção
 Inserção
 Página apropriada deve ser encontrada e modificada
 Custo = C + 2D + H
 Deleção
 Encontrar a página do registro a ser removido
 Remover o registro da página
 Shift nos demais registros
 Escrever a página modificada
 Custo = Sel + D + RC
Resumo - Hash
Scan
1.25B
(D+RC)
1.25BD
Sel =
Sel =
chave
Nchave
H+D+
RC
D
Sel <> Insert
Delete
sel
1.25B(D+
RC)
1.25B(D+
RC)
H+2D+ C
Sel +
D + RC
1.25BD
1.25BD
2D
Sel+D
Só I/O
Escolha de uma Boa Organização
Scan
Sel =
chave
Sel =
Sel <>
Insert
Delete
Nchave
Heap
BD
0.5BD
Ord
BD
Dlog2B Dlog2B Dlog2B Dlog2B Dlog2B
+ DB/2
+
+
BD
BD
Hash
1.25BD
D
BD
BD
1.25BD 1.25BD
2D
2D
2D+Sel
Sel+D