Arquivos Estruturados por
Hashing– Custos I/O
AULA 6
Profa. Sandra de Amo
GBC053 – BCC
Estudaremos nesta aula
 Estimativa de custos de I/O para operações
de:





Scan em arquivos hashed (agrupados)
Inserção de tuplas em arquivos agrupados
Remoção de tuplas em arquivos agrupados
Busca em arquivos agrupados pelo atributo- chave de busca
Busca em arquivos agrupados por atributos diferentes do
atributo-chave de busca
Arquivos agrupados por um atributo X
 Arquivo A é organizado em subarquivos S1,…, Sn, cada subarquivo
contendo 1 página não completamente utilizada (20% livre).
 Subarquivo também é chamado de “Bucket”.
 Assim, se o arquivo original contém M páginas, o arquivo estruturado
de forma hash (distribuído nos subarquivos) conterá M*1.25 páginas.
 Função hash H(valor-atributo) = n responsável por distribuir os
registros
 Um registro (…,v,….) pertence ao subarquivo Sk se H(v) = k.
Atributo X que é a chave do agrupamento (Hashing)
Arquivos agrupados por um atributo X
 As páginas do arquivo contém diretório de slots como os
arquivos heap.
 Este diretório é utilizado para localizar a posição na página
onde se encontra um registro com rid dado.
 A inserção de um novo registro não é feita utilizando o
diretório de páginas, pois a página onde será inserido o
registro é a única página do subarquivo Sk, onde k = H(v), v =
valor do atributo X do registro a ser inserido.
 A remoção de um registro é feita exatamente como no caso
de arquivo heap.
Lembrando:

Páginas do arquivo são agrupadas por buckets (subarquivos)
S1

S2
S3
S4 ….
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
Exemplo: inserção de um registro
Suponha H(n) = n mod 3
Página do Subarquivo S2
Diretório de slots da página
(500,165) (450,50)
Registros:
Rid (2,1) : (...., 5, ....)
Rid (2,2) : (...., 17,....)
Rid (2,3) : (...., 32, ....)
Rid (2,4) : (...., 44,....)
Rid (2,5) : (....,20,....)
(250,200) (100,150) (0,100)
5
665
Passos para a inserção de um
registro
Suponha que se quer inserir o registro
(...., 14 ,....) de tamanho 300
1.
2.
Calcula-se H(14) = 14 mod 3 = 2, para determinar a página onde
deverá ser inserido. No caso esta página será a única página do
subarquivo S2 (página 2).
Busca no diretório de slots o endereço do espaço vazio. Determina
se há espaço vazio endereço do inicio do espaço vazio suficiente para
o registro ser inserido nesta página.
3.
Em caso positivo: A inserção será feita neste endereço.
4.
Em caso negativo: Uma nova página é criada no subarquivo S2
1.
Cria-se um diretório de páginas para gerenciar o subarquivo S2 que
agora já contém 2 páginas, cada uma delas com um número de bytes
livres.
Qual o rid do novo registro ?
Verifica no diretório de slots se há algum slot com
conteúdo (-1,_). Se houver, este será o slot
associado ao novo registro.
2. Se não houver: cria-se um novo slot que será
associado ao novo registro.
3. Atualiza o diretório de slots.
1.
Situação após a inserção.
Novo registro de tamanho 300 é inserido aqui !
Espaço livre de 35 bytes
Página do Subarquivo S2
Diretório de slots da página
(665,300) (500,165) (450,50) (250,200) (100,150) (0,100)
Registros:
Slot 6 Slot 5 Slot 4
Slot 3 Slot 2 Slot 1
Rid (2,1) : (...., 5, ....)
Rid (2,2) : (...., 17,....)
Rid (2,3) : (...., 32, ....)
Rid (2,4) : (...., 44,....)
Rid (2,5) : (...., 20,....)
Novo registro
Rid (2,6) : (...., 14,....)
6
965
O que acontece quando não há espaço suficiente
na única página do subarquivo S2 para o novo
registro ?
 Cria-se uma nova página p de overflow no
subarquivo S2
 Insere-se ponteiro na página 2 para esta nova página
p e ponteiro de p para a página 2.
 Subarquivo S2 é agora um arquivo de 2 páginas,
todas com seu diretório de slots.
 Um diretório de páginas é criado para gerenciar as
páginas do subarquivo (heap) S2.
“Degeneração” da estrutura Hash
 Quando os subarquivos contém muitas páginas de
overflow, a estrutura começa a perder sua utilidade
na aceleração das buscas pelo atributo chave do
Hash.
 Buscas pelo atributo chave do Hash se tornam
praticamente buscas em arquivo Heap (menores).
Degeneração da estrutura hash…

Páginas do arquivo são agrupadas por subarquivos ou buckets
Subarquivo 1 (bucket 1)

Subarquivo 2 (Bucket 2)
Subarquivo 3 (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.
ESTIMATIVAS DE CUSTOS
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 da relação


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 da relação
 Supõe-se sempre que a estrutura hash não começou a se
degerar. Logo, cada bucket tem uma única página
 Todos os registros com A = a estão em um único bucket.

Custo = H + 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 (supondo somente 1 registro ou que todos
os registros estão em uma única página)





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 + RC + D
Resumo - Hash
Scan
1.25B
(D+RC)
1.25BD
Sel =
Sel =
chave
Nchave
H+D+
RC/2
H + D + RC 1.25B(D+RC)
D
D
Sel <>
1.25BD
Insert Delete
sel
2D
H +2D+
C
Sel + XD
Sel+XD
Só I/O
X = N. Pag. com registros removidos
“CHAVE” = Chave da relaçã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
D
BD
1.25BD
2D
2D
2D+Sel
Sel+X
X = N. Pag. com registros removidos
“CHAVE” = Chave da relação