Please enable JavaScript.
Coggle requires JavaScript to display documents.
Arquivos de registro Primários - Coggle Diagram
Arquivos de registro Primários
Hashing
2 - Oferece acesso muito rápido aos registros (sob certas condições)
4 - Operações básicas
Busca
condição de pesquisa precisa ser uma igualdade em um campo denominado campo de hash
comumente só precisa de um acesso único de bloco para recuperar o registtro
Oferece acesso mais o rápido possível para se recuperar um registro qualquer dado o valor de seu campo de hash
1 - Denominado Arquivo de hash
OBS
na maior parte dos casos o campo hash é também um campo chave do arquivo denominado
chave de hash
hashing também é utilizado como estrutura de pesquisa interna quando um grupo de registro é acessado exclusivamente pelo uso do valor de um campo
3 - oferece uma função "h" denominada função de hash ou função de randomização
função é aplicada ao valor do campo de hash de um registro
gera endereçõ do bloco de disco em que o registro será arqmazenado
Hashing Interno (para arquivos internos)
função comum
h(k) = K mod M
Objetivo de uma boa função de hashing é distribuir os registros de maneira uniforme pelo espaço de endereços de modo a dinamização as colisões enquanto não deixam muitos locais não usados (espaço desperdiçado)
Estudos mostraram que é melhor manter uma tabela de hash entre 70 e 90 por cento cheia, com isso evitando desperdício e muitas colisões
Quando a função hash com Mod é utilizada, comumente é melhor escolher um número primo de endereços possíveis, pois ocorre melhor distribuição dos endereços de hash.
Obs
: outras funções por exemplo podem exigir que M (locais) seja uma potencia de 2.
onde:
intervalo de índice do array vai de 0 a M-1 (M Slots)
endereços correspondem aos índices de array
função hash transforma o valor de campo de hash em um inteiro entre 0 e M-1
função h(K) retorna o resto de um valor de capo de hash inteiro k após a divisão por M
esse valor é usado para o endereço de registro
Hashing externo (para arquivos de disco)
2 - espaço de endereços de destino é definido por meio de Buckets (cada um mantem vários registros)
1 - bucket
bloco de disco ou um cluster de blocos de disco contíguos
3 - função de hash mapeia uma chave em um número de bucket relativo (ao invés de atribuir a um endereço absoluto)
4- Tabela mantida no cabecalho converte o número do bucket par o endereço de bloco do disco correspondente (físico)
5 - problema de colisão é menos sério com buckets pois independente de quantos registros cabem, eles podem ser redefinidos por hashing ao mesmo bucket sem causar pbolemas
INCLUIR FIGURAS 17.9 e 17.10
6 - Operações básicas
Busca por um registro dado um valor de algum campo diferente do campo de hash é tao dispendiosa quanto num arquivo desordenado.
Exclusão
processo
remoção do registor do seu bucket
caso possua cadeia overflow
pode-se mover um dos registro de overflow par o bucket substituir o registro excluido (aproveitamento de espaço)
se o registro excluido ja estiver em overflow o removemos da lista liga
modificação
depende de
condição de pesquisa
comparação de igualdade no campo hash
localizacao eficiente
não igualdade
busca linear
campo hash
não
pode ser modificado e regravação pode ocorrer no mesmo bucket
sim
registro pode ser movido para outro bucket
exclusão do registro antigo
inserção do registro modificado
hashing estático vs extensível
Expansão com hashing extensĩvel
valor de "d" pode ser aumentado ou diminuido de um a cada vez que ocorre "estouro" ou "redução"
reduza pela metade o numero de entradas no array
ocorre se d>d' para todos os buckets (apos ocorrencia de exclusões)
aumenta 2 vezes (dobra)
Estouro: caso um bucket cuja projundidade local d' seja igual a profundidade global d,
divisão do bucker
nova inserção causa overflow (novo bit de divisão é relacionado ao bucket)
exexmplo: overflow no bucket com valores iniciando com 01
com ocorrencia do estouro dois novos buckets serão criados
2 more items...
novos valores iniciados em 01 serão direcionados para um destes dois buckets
profundidade de d' aumentou de 1 valor
Operações
busca
maioria das recuperações exige dois acessos de bloco
um para o diretorio
outro para o bucket
Principais vantagens
1 - desempenho do arquivo não degrada enquanto arquivo cresce (ao contrario do hashing estático, onde as colisões aumentam e o encadeamento corresponde a um aumento médio de acesso por chave)
2 - Nenhum espaçõ é alocado para crescimento futuro (ocorrendo de maneira dinâmica conforme necessidade)
3 - tamanho máximo do diretório é de 2K (onde k é o número de bits no valor de hash)
4 - divisão causa apenas uma pequena reorganização
desvantagem
diretório precisa ser pesquisado antes do acesso aos buckets resultando em 2 acessos
penalidade considerada pequena
Esquema é tido como bastante desejável para arquivos dinâmicos
Hashing dinâmico foi utilizado de modo precusor ao extensĩvel
ver figura 17.12
Hashing Linear
objetivo:
permitir que um aquivo de hash explanda e encolha seu número de bucketes dinamicamente sem precisar de um diretório
criação de buckets de forma linear
novas colisões levam a registros de overflow dividindo buckets na órdem linear
funções
função(k) = K mod M
função i+1(k) = K mod2M
função i+2 (k) = K mod 4M e assim por diante
Incluir - Figura 17,11
estático
overflow
quando um bucket está cheio até sua capacidade e um novo registro a ser inserido tem um hash para esse bucket
um ponteiro é mantido em cada bucket para uma lista ligad de registros de overflow
os ponteiros ligados na lista devem ser ponteiros de registro que incluem
posição de registro relativa ao bloco
endereco de bloco
Heap (aquivos de registro desordenados)
1 - Ordenados na ordem em que são inseridos (final do arquivo)
organização denominada heap ou pilha
????(pergunta)
o postgres utiliza esse formato como padrão?
2 - Utilizações comuns
utilizada com caminhos de acesso adicionais (como os índices secundários)
Armazenar registro de dados para uso futuro
3 -
inserção de registros é muito eficiente
processo de inserção
1 - ultimo bloco de disco do arquivo é copiado para buffer
2 -novo registro é acrescentado
3 - bloco é regravado no disco
endereço do último bloco é mantido no cabeçalho do arquivo
4 -
processo de busca
processo dispendioso
Envolve pesquisa linear por bloco no arquivo
quando na busca apenas um único registro satisfizer os critérios de pesquisa
custo b/2 (metade dos blocos)
resultará em média na busca de metade dos blocos de arquivo
quando vários registros satisfizerem a condição de pesquisa
programa deve ler e pesquisar todos os blocos do arquivo
processo de exclusão
Possiblidades
Exclusão do registro no bloco sem reaproveitamento de espaço (desperdício de espaço nos blocos)
3 - regravar o blloco no disco
Problema
isso deixa espaço livre no bloco do disco
exclusão de muitos registros = espaço desperdiçado
1 - Encontrar o bloco e copiálo para o buffer
2 - excluir registro do buffer
técnica do bit extra (marcador de exclusão)
b) valor diferente no marcador indica registro válido
a) macador de exclusão possui valor predefinido
programas de pesquisa consideram apenas valores válidos
Usar espaço dos registros excluídos para inserir novos registros
exige manutençao extra para controle/informações sobre os locais vazios
as técnicas exigem reorganização ou manutençao periódica para retomar espaço não utilizado pelos registros excluidos
processo de reorganização
1- blocos de arquivos são acessados de maneira consecutiva
2 - registro são compactaos pela remoção de registros excluidos
3 - blocos são preenchidos até sua capacidade mais uma vez
Classificados (aquivos de registro ordenados)
1 - Ordenação com base nos valores de um determinado campo (denominado campo de ordenação)
2 - Arquivo ordenado ou sequencial
3 - Se campo de ordenação for campo chave (com garantia de identificador exclusivo), campo é denominado chave de ordenação
Algoritmo Exemplo - Registros Classificados
https://colab.research.google.com/drive/1b7qYjMDQSu4fyzcyzINA0VmK1gA5MO_F?authuser=1#scrollTo=UM7AmIQR8nJq
4 - Vantagens
a) Leitura dos registros na órdem dos valores da chave é eficiente
b) encontrar o próximo registro com base no atual na ordem da chave normalmente não irá requerer acesso de blocos adicionais (pois provavelmente estará neste mesmo bloco, a não ser que seja o final do bloco)
c) Uso de uma condição de pesquisa com base num valor campo-chave de ordenação possibilita acesso mais rápido quando pesquisa binária é utilizada
d) arquivos ordenados normalmente são armazenados de modo contíguo para minimizar o tempo de busca.
e) pesquisa binária pode ser feita nos blocos ao invés dos registros.
ex: B blocos numerados de 1 até b; os registros ordenados por valor crescente do campo chave
estamos buscando pelo registro de campo chave = K
supondo endereços de disco dos blocos disponíveis no cabecalhoh do arquivo
pesquisa binária acesssa log2(b) blocos não importando se o registro foi localizado ou não
melhoria em relação as pesquisas lineares
media nas pesquisas lineares é de (b/2) quando registro é encontrado e b/1 quando registro não é encontrado (ou até mesmo para múltiplos registros a serem encontrados)
f) critérios de pesquisa envolvendo condições >, >=, < e <= no campo de ordenação são muito eicientes, pois todos registros que satisfazem condição são contíguos no arquivo
6 - Incluir Figura 17.7 (blocos de um arquivo ordenado)
Não traz vantagens, nem prejuízo (Independe)
5 - ordenação não oferece vantagens para acesso aleatório ou ordenado dos registros nos valores de outros campos não ordenados do arquivo
Operações básicas
Busca
Otimizada /eficiente para campos ordenados /chave de ordenação
blocos podem ser lidos consecutivamente
pode usar buffering duplo
Indiferente (sem vantages) para outros campos não ordenados
processo (ver algoritmo)
Inserção
operação dispendiosa
deve gerenciar ordenação
processo
a) encontrar posição correta
b) criar espaõ no aquivo para inserir registro na posição adequada
Em arquivos muito grandes pode ocasionar em grande processamento pois na média metade dos blocos podem ser movidos, ocasionando leitura de metade dos blocos e regravação destes
Processos alternativos
Opção mais eficiente (porém paliativa)
problema reaparece quando espaços vazios são preenchidos/utilizados
Manter espaçõ não usado em cada bloco para novos registros
criação de arquivo não ordenado temporário
denominado arquivo de overflow ou transação (arquivo principal é denominado mestre)
novos registros são inclusos no final do arquivo de overflow
Em alguns momentos arquivo de overflow é classificado e mesclado ao arquivo mestre durante reorganização do arquivo
Benefício: Inserção eficiente
Problema: maior complexidade no algoritmo de pesquisa
arquivo overflow precisa de pesquisa linear caso pesquisa binária não localize registro no arquivo principal
Exclusão
operação dispendiosa
deve gerenciar ordenação
processo
processo menos grave quando utilizados os marcadores de exclusão e reorganização periódica.
Atualização
processo
busca do registro
caso envolva o campo-chave comumente busca binária
caso não envolva campo-chave será busca linear
mudança
campo não ordenado
alter registro e grava no mesmo local físico (Considerando registros de tamanho fixo)
campo ordenado
registro pode alterar posição no arquivo
requer
exclusão do registsro antigo
inserção do registro modificado
OBS:
arquivos ordenados são usados comumente com caminhos adicionais denominados índices primários resultando em um aquivo sequencial indexado
melhora o tempo de acesso aleatório ao campo-chave de ordenação
se o atributo de ordenação não for uma chave o arquivo é denominado de arquivo agrupado.
Comparativo de tempo de acesso
Media de blocos para acessar um registro específico
Heap
varredura sequencial (pesquisa linear)
b/2
Ordenado
Varredura sequencial (pesquisa linear)
b/2
pesquisa binária
log2(b)
