ArmazenamentoFísicoHashing-2

Prévia do material em texto

Armazenamento, Armazenamento, 
Estrutura de Arquivos e 
Hashing
Armazenamento, Armazenamento, 
Estrutura de Arquivos e 
Classificação das mídias de 
armazenamento físico
 Velocidade com a qual os dados podem ser 
acessadosacessados
 Custo por unidade de dados
 Confiabilidade
 Dados perdidos na falha de potência ou falha do sistema
 Falha física do dispositivo de armazenamento
 Pode diferenciar o tipo de armazenamento em:
Armazenamento volátil: perde o conteúdo quando a  Armazenamento volátil: perde o conteúdo quando a 
potência é desligada
 Armazenamento não-volátil
 O Conteúdo persiste mesmo quando a potência é desligada.
 Inclui armazenamento secundário (discos) ou armazenamento on
line; e o terciário ou offline (fitas).
Classificação das mídias de 
armazenamento físico
Velocidade com a qual os dados podem ser 
Custo por unidade de dados
Dados perdidos na falha de potência ou falha do sistema
Falha física do dispositivo de armazenamento
Pode diferenciar o tipo de armazenamento em:
perde o conteúdo quando a perde o conteúdo quando a 
volátil:
O Conteúdo persiste mesmo quando a potência é desligada.
Inclui armazenamento secundário (discos) ou armazenamento on-
line; e o terciário ou offline (fitas).
Mídias de Armazen
 Cache – A mais rápida e custosa forma de 
armazenamento; volátil; gerenciada pelo hardware 
do sistema computacional.do sistema computacional.
 Memória principal:
 Acesso rápido (10s a 100s nanosegundos; 1 nanosegundo
= 10–9 segundos)
 geralmente muito pequena (ou muito cara) para armazenar 
todo o banco de dados
 capacidades da ordem de Gigabytes (8 a 16 GB 
256 GB – servidores)256 GB – servidores)
 Capacidades têm aumentado e custos por byte têm diminuído 
constantemente e rapidamente (em aproximadamente um 
fator de 2 cada 2 a 3 anos)
 Volátil — conteúdo da memória principal normalmente se 
perde se houver falta de energia ou uma falha do sistema.
namento Físico
A mais rápida e custosa forma de 
armazenamento; volátil; gerenciada pelo hardware 
do sistema computacional.do sistema computacional.
Acesso rápido (10s a 100s nanosegundos; 1 nanosegundo
geralmente muito pequena (ou muito cara) para armazenar 
capacidades da ordem de Gigabytes (8 a 16 GB – Laptops; 
Capacidades têm aumentado e custos por byte têm diminuído 
constantemente e rapidamente (em aproximadamente um 
fator de 2 cada 2 a 3 anos)
conteúdo da memória principal normalmente se 
perde se houver falta de energia ou uma falha do sistema.
Mídias de armazena
 Memória Flash
 Dados sobrevivem à falta de energia
Dados podem ser escritos em um lugar uma vez, mas o lugar 
pode ser apagado e escrito de novopode ser apagado e escrito de novo
 Pode suportar um número limitado de ciclos de apagamento (de 10K a 
1M).
 Para escrever sobre a memória que já foi escrita tem que ser apagado a
cela inteira de memória
 Leituras são aproximadamente tão
principal
 Mas as escritas são lentas (pouco
lentolento
 O custo por unidade de armazena
ao da memória principal
 Amplamente usado em sistemas e
digitais.
 É um tipo de EEPROM (Electricall
Only Memory)
amento físico (Cont.)
Dados sobrevivem à falta de energia
Dados podem ser escritos em um lugar uma vez, mas o lugar 
pode ser apagado e escrito de novopode ser apagado e escrito de novo
Pode suportar um número limitado de ciclos de apagamento (de 10K a 
Para escrever sobre a memória que já foi escrita tem que ser apagado a
o rápidas quanto da memória 
os microssegundos), apagar é mais 
namento é aproximadamente similar 
embutidos em portáteis ou câmeras 
lly Erasable Programmable Read-
Mídias de armazena
 Discos Magnéticos
 Os dados são armazenados em discos, e são lidos/gravados 
magneticamente
 Principal meio para armazenamento de dados on Principal meio para armazenamento de dados on
prazo; normalmente armazena todo o banco de dados.
 Os dados devem ser movidos
para serem acessados, e os
no disco
 Acesso muito mais lento que o da memória principal
 Acesso direto – é possível ler dados do disco em qualquer 
ordem, ao contrário da fita magnética.
 O tamanho dos discos magnéticos pode alcançar hoje em dia  O tamanho dos discos magnéticos pode alcançar hoje em dia 
capacidades maiores a 400 GB
 Muito maior capacidade e menor custo/byte que as memórias principal 
e flash
 Crescimento constante e rápido com os avanços tecnológicos (fator 
de 2 a 3 cada 2 anos)
 Sobrevive a falhas de energia e falhas do sistema
 Falhas de disco podem destruir dados, mas são raras
amento físico (Cont.)
Os dados são armazenados em discos, e são lidos/gravados 
Principal meio para armazenamento de dados on-line a longo Principal meio para armazenamento de dados on-line a longo 
prazo; normalmente armazena todo o banco de dados.
movidos do disco para a memória principal
os modificados são gravados de volta
Acesso muito mais lento que o da memória principal
é possível ler dados do disco em qualquer 
ordem, ao contrário da fita magnética.
O tamanho dos discos magnéticos pode alcançar hoje em dia O tamanho dos discos magnéticos pode alcançar hoje em dia 
capacidades maiores a 400 GB
Muito maior capacidade e menor custo/byte que as memórias principal 
Crescimento constante e rápido com os avanços tecnológicos (fator 
Sobrevive a falhas de energia e falhas do sistema
Falhas de disco podem destruir dados, mas são raras
Mídias de armazena
 Armazenamento óptico
 Os dados não-voláteis, são lidos da forma ótica usando um 
laser
 CD-ROM (700 MB) e DVD (4.7 a 17 GB) as formas mais 
populares
 Write-one, read-many (WORM) discos óticos são usados 
para armazenamento histórico (CD
 Versões para múltiplas gravações també são disponíveis 
(CD-RW, DVD-RW, DVD+RW, e DVD
 Leituras e gravações são mais lentas que com discos 
magnéticosmagnéticos
 Sistemas de Juke-box, com grandes números de discos 
removíveis, poucos drives, e um mecanismo para carga e 
descarga automática de discos disponíveis para o 
armazenamento de grandes volumes de dados.
amento físico (Cont.)
voláteis, são lidos da forma ótica usando um 
ROM (700 MB) e DVD (4.7 a 17 GB) as formas mais 
many (WORM) discos óticos são usados 
para armazenamento histórico (CD-R, DVD-R, DVD+R)
Versões para múltiplas gravações també são disponíveis 
RW, DVD+RW, e DVD-RAM)
Leituras e gravações são mais lentas que com discos 
, com grandes números de discos 
removíveis, poucos drives, e um mecanismo para carga e 
descarga automática de discos disponíveis para o 
armazenamento de grandes volumes de dados.
Mídias de armazena
 Armazenamento em fita
 não-volátil, usado principalmente para backup 
(recuperação de falhas de disco), e para 
armazenamento e arquivo
 Acesso seqüencial – muito mais lento que os discos
 Capacidade muito grande (40 a 300 GB)
 Fitas podem ser removidas da unidade (drive) 
custos de armazenamento muito mais baratos que 
disco, porém as unidades são mais custosas
 Bibliotecas de fitas (jukeboxes) disponíveis para o 
armazenamento de quantidades massívas de dadosarmazenamento de quantidades massívas de dados
 Centos de terabytes (1 terabyte = 10
petabyte (1 petabyte = 10
amento físico (Cont.)
Armazenamento em fita
volátil, usado principalmente para backup 
(recuperação de falhas de disco), e para 
armazenamento e arquivo
muito mais lento que os discos
Capacidade muito grande (40 a 300 GB)
Fitas podem ser removidas da unidade (drive) 
custos de armazenamento muito mais baratos que 
disco, porém as unidades são mais custosas
Bibliotecas de fitas (jukeboxes) disponíveis para o 
armazenamento de quantidades massívas de dadosarmazenamento de quantidades massívas de dados
Centos de terabytes (1 terabyte = 109 bytes) até um 
petabyte (1 petabyte = 1012 bytes)
Fonte: Elmasri e Navathee, 2016 7ª. Edição.
Hierarquia de AArmazenamento
Hierarquia de Arma
 Armazenamento principal
armazenamento mais rápido mas volátil (cache, 
memória principal).memória principal).
 Armazenamento secundário
hierarquia,não-volátil, tempo de acesso 
moderadamente rápido
 Também chamado armazenamento on
 Ex: memória flash, discos magnéticos
 Armazenamento terciário Armazenamento terciário
hierarquia, não-volátil, tempo de acesso lento
 Também chamado armazenamento off
 Ex: fita magnética, armazenamento ótico
azenamento (Cont.)
Armazenamento principal: O médio de 
armazenamento mais rápido mas volátil (cache, 
Armazenamento secundário: próximo nível na 
volátil, tempo de acesso 
armazenamento on-line
Ex: memória flash, discos magnéticos
Armazenamento terciário: nível mais baixo na Armazenamento terciário: nível mais baixo na 
volátil, tempo de acesso lento
armazenamento off-line
Ex: fita magnética, armazenamento ótico
Mecanismo de disco
PS: Diagrama é esquemático, e simplifica
o duro magnético
a estrutura de unidades disco reais 
Bancos de Dados –
 Bancos de Dados armazenam grandes 
quantidades de dados por períodos longos 
de tempo em meios de armazenamento 
secundário;
 Estruturas de dados em memória principal 
armazenam quantidades limitadas de dados 
por curtos períodos de tempo;por curtos períodos de tempo;
 Fitas são usadas para 
Nível Físico
Bancos de Dados armazenam grandes 
quantidades de dados por períodos longos 
de tempo em meios de armazenamento 
Estruturas de dados em memória principal 
armazenam quantidades limitadas de dados 
por curtos períodos de tempo;por curtos períodos de tempo;
Fitas são usadas para backup
Bancos de Dados –
 Técnicas usadas para armazenamento e 
manipulação de grandes quantidades de dados manipulação de grandes quantidades de dados 
armazenados em memória secundária;
 Técnicas eficientes para discos ópticos são 
diferentes;
 Um SGBD provê geralmente várias opções para 
organização física dos dados.
 Projeto Físico de Banco de Dados: Projeto Físico de Banco de Dados: 
determinar o melhor tipo de organização dos dados, 
dentre todas as possíveis, para uma determinada 
aplicação;
Nível Físico
Técnicas usadas para armazenamento e 
manipulação de grandes quantidades de dados manipulação de grandes quantidades de dados 
armazenados em memória secundária;
Técnicas eficientes para discos ópticos são 
Um SGBD provê geralmente várias opções para 
organização física dos dados.
Projeto Físico de Banco de Dados: Busca Projeto Físico de Banco de Dados: Busca 
determinar o melhor tipo de organização dos dados, 
dentre todas as possíveis, para uma determinada 
Arquivos e
 Sistema Operacional / Sistema de Arquivos: 
Fornece ao SGBD os serviços básicos 
manipulação de arquivos. O SGBD utiliza 
estes serviços para prover outras facilidades 
(nível lógico).
 Registros:
Campos ou ítens; Campos ou ítens;
 Tipo/Formato de Registros;
 Tipo de dados de cada campo.
e Registros
Sistema Operacional / Sistema de Arquivos: 
Fornece ao SGBD os serviços básicos 
manipulação de arquivos. O SGBD utiliza 
estes serviços para prover outras facilidades 
Tipo/Formato de Registros;
Tipo de dados de cada campo.
Arquivos e
 Arquivos: Seqüências de registros
 Tamanho fixo: Todos os registros possuem o 
mesmo tamanho exatamente;
 Tamanho variável:
 Um ou mais campos têm tamanho variável;
 Campos com múltiplos valores (campos repetidos);
 Campos opcionais;
 Registros de tipos diferentes;
e Registros
Arquivos: Seqüências de registros
Tamanho fixo: Todos os registros possuem o 
mesmo tamanho exatamente;
Um ou mais campos têm tamanho variável;
Campos com múltiplos valores (campos repetidos);
Registros de tipos diferentes;
Regisstros
Arquivos e
 Blocos: Unidades de transferência da 
memória secundária para memória principal;memória secundária para memória principal;
 Alocação de registros de um arquivo são 
feitas em blocos do disco;
 Modos de alocação: registros nem sempre 
cabem perfeitamente em um bloco;
 Fator de Bloco Fator de Bloco
 Alocação espalhada X 
espalhada
e Registros
Blocos: Unidades de transferência da 
memória secundária para memória principal;memória secundária para memória principal;
Alocação de registros de um arquivo são 
feitas em blocos do disco;
Modos de alocação: registros nem sempre 
cabem perfeitamente em um bloco;
X Alocação não 
Blocos de
Não espalhada: os registros
Espalhada: os registros pode
Registros
devem estar em um só bloco
em estar distribuídos em dois blocos
Organização de Arquivos
 Registros Desordenado
 Registros Ordenados
 Organização por Hash
quivos
dos
hing
Arquivos de Registr
 Busca de registros é li
 Inserção é feita no fina
 Remoção é lógica: ma
 Reorganização periód
 Ordenação externa;
 Arquivo Relativo :
 Registros de tamanho f
 Alocação não espalhad
 Fácil localização de reg
ros Não Ordenados
inear;
al do arquivo;
arca de remoção
dica;
fixo;
hada e contígua;
gistros;
Arquivos de Regi
 Registros ordenados de acordo como um campo de 
ordenação;ordenação;
 Chaves de Ordenação : ordenação baseada em 
um campo chave;
 Busca de registros pelo campo de ordenação é 
eficiente: busca binária;
 Inserção: arquivo auxiliar (arquivo de 
transação/overflow)
 Remoção: marcação para remoção física;
 Reorganização periódica;
istros Ordenados
Registros ordenados de acordo como um campo de 
: ordenação baseada em 
Busca de registros pelo campo de ordenação é 
Inserção: arquivo auxiliar (arquivo de 
Remoção: marcação para remoção física;
Reorganização periódica;
Arquivos OOrdenados
Organização por Ha
 Função de endereçamento
Determina a posição
ser inserido;
 Campo de Hashing : Usado como argumento 
da função;
 Objetivo : Melhorar o acesso com critério de 
busca;busca;
ashing
endereçamento ou de Hashing :
onde um registro deve
Campo de Hashing : Usado como argumento 
Objetivo : Melhorar o acesso com critério de 
Organização por Ha
 Hashing Interno:
 Usado em memória principal;
 Cada registro ocupa uma posição em um arranjo;
 A função de Hashing retorna a posição do registro 
baseada no valor do campo de Hashing;
 Tratamento de Colisões
Endereçamento Aberto; Endereçamento Aberto;
 Encadeamento;
 Hashing Múltiplo;
ashing
Usado em memória principal;
Cada registro ocupa uma posição em um arranjo;
A função de Hashing retorna a posição do registro 
baseada no valor do campo de Hashing;
Tratamento de Colisões
Endereçamento Aberto;Endereçamento Aberto;
Organização por Haashing
Organização por Ha
 Hashing Externo:
Função de Hashing retorna o número de um  Função de Hashing retorna o número de um 
número de uma posição no arranjo;
 Um bucket pode conter um ou mais blocos do arquivo;
 Uma tabela associa o nr. do bucket ao endereço do primeiro (ou 
único) bloco do bucket;
 Registros com diferentes valores da chave de busca podem ser 
mapeados ao mesmo bucket; assim todo o bucket tem que ser 
pesquisado seqüencialmente para localizar um registro.pesquisado seqüencialmente para localizar um registro.
 Podem haver m registros por bucket;
 Colisão ocorre quando o m + 1
ashing
Função de Hashing retorna o número de um bucket, ao invés do Função de Hashing retorna o número de um bucket, ao invés do 
número de uma posição no arranjo;
Um bucket pode conter um ou mais blocos do arquivo;
Uma tabela associa o nr. do bucket ao endereço do primeiro (ou 
Registros com diferentes valores da chave de busca podem ser 
mapeados ao mesmo bucket; assim todo o bucket tem que ser 
pesquisado seqüencialmente para localizar um registro.pesquisado seqüencialmente para localizar um registro.
registros por bucket;
+ 1-ésimo registro deve ser inserido;
Hashing Externo
Exemplo de uma organização
arquivo de Hash
Uma organização de arquivo de Hash de Contas, usando o nome_agência 
como chave (Veja figura no próximo slide.)
Existem 10 buckets,
A representação binária do I-ésimo caracter do alfabeto é assumida 
como o inteiro i.
A função de hash retorna a suma das representações binárias dos 
caracteres módulo 10caracteres módulo 10
 Ex. h(Perryridge) = 5 h(Round Hill) = 3
de uma organização deUma organização de arquivo de Hash de Contas, usando o nome_agência 
como chave (Veja figura no próximo slide.)
ésimo caracter do alfabeto é assumida 
A função de hash retorna a suma das representações binárias dos 
h(Round Hill) = 3 h(Brighton) = 3
Exemplo de uma organiza
Uma organização de arquivo de Hash de Contas, usando o 
nome_agência como chave (veja slide anterior para detalhes).
ação de arquivo de Hash
Uma organização de arquivo de Hash de Contas, usando o 
nome_agência como chave (veja slide anterior para detalhes).
Funções
 A pior função mapeia todos os valores das chaves de busca 
para o mesmo bucket; isto faz o tempo de acesso 
proporcional ao número de valores das chaves de busca no proporcional ao número de valores das chaves de busca no 
arquivo.
 Uma função de hash ideal é uniforme
é atribuído o mesmo número de valores das chaves de 
busca do conjunto de todos os possíveis valores.
 Uma função de hash ideal é aleatória
terá quase o mesmo número de valores atribuídos a ele, 
independente da distribuição real dos valores da chave de 
busca no arquivo.busca no arquivo.
 Funções de hash típicas fazem cálculos baseados na 
representação interna da chave de busca.
 Por exemplo, para uma chave de busca cadeia de caracteres, a 
representação binária de todos os caracteres na cadeia poderiam ser 
somados e a soma módulo o número de buckets poderia ser retornado. 
de Hash
A pior função mapeia todos os valores das chaves de busca 
para o mesmo bucket; isto faz o tempo de acesso 
proporcional ao número de valores das chaves de busca no proporcional ao número de valores das chaves de busca no 
uniforme, isto é, a cada bucket 
atribuído o mesmo número de valores das chaves de 
busca do conjunto de todos os possíveis valores.
aleatória, assim cada bucket 
terá quase o mesmo número de valores atribuídos a ele, 
independente da distribuição real dos valores da chave de 
Funções de hash típicas fazem cálculos baseados na 
representação interna da chave de busca.
Por exemplo, para uma chave de busca cadeia de caracteres, a 
representação binária de todos os caracteres na cadeia poderiam ser 
somados e a soma módulo o número de buckets poderia ser retornado. 
Tratamento de Ove
 Um Overflow de Buckets pode ocorrer devido a
 Insuficiente número de buckets
 Distorção na distribuição de registros.
ocorrer por dois motivos:
 vários registros podem ter a mesma chave de busca
 A função de hash escolhida produz uma distribuição não 
uniforme das chaves de busca
 Embora a probabilidade
pode ser reduzido, elepode ser reduzido, ele
ele é tratado usando buckets
erflows de Buckets
Um Overflow de Buckets pode ocorrer devido a
Insuficiente número de buckets
Distorção na distribuição de registros. Isto pode 
vários registros podem ter a mesma chave de busca
A função de hash escolhida produz uma distribuição não 
uniforme das chaves de busca
probabilidade do overflow de buckets
não pode ser eliminado;não pode ser eliminado;
buckets de overflow.
Organização por ha
 Tratamento de Overflow por Encadeamento
 Manter buckets de overflow; Manter buckets de overflow;
 Encadear registros que devem permanecer a um mesmo bucket;
 O esquema acima é chamado de 
 Uma alternativa, chamada de hashing aberto
overflow, não é adequada para aplicações de bancos de dados.
 Remoção de Registros : Consiste em ”apaga
usado overflow deve ser usado tratamento especial;
 Problemas :
 Recuperação de vários registros em uma determinada ordem; Recuperação de vários registros em uma determinada ordem;
 Má utilização do espaço de endereçamento dos buckets;
 Tamanho fixo do arquivo;
 Modificação do valor do campo usado como argumento da função 
Hashing.
ashing
Tratamento de Overflow por Encadeamento
Encadear registros que devem permanecer a um mesmo bucket;
O esquema acima é chamado de hashing fechado.
hashing aberto, que não usa buckets de 
overflow, não é adequada para aplicações de bancos de dados.
Remoção de Registros : Consiste em ”apaga-los” do bucket. Se for 
usado overflow deve ser usado tratamento especial;
Recuperação de vários registros em uma determinada ordem;Recuperação de vários registros em uma determinada ordem;
Má utilização do espaço de endereçamento dos buckets;
Modificação do valor do campo usado como argumento da função 
Encadeeamento
Índices de
 Hashing pode ser usado não só para a organização de arquivos, 
mas também para a criação de estruturas de índices.
 Um índice de hash organiza as chaves de busca, com seus 
ponteiros de registros associados, numa estrutura de arquivo hash.ponteiros de registros associados, numa estrutura de arquivo hash.
 Falando estritamente, os índices de hash são sempre índices 
secundários
 Um índice de hash não é necessário com uma estrutura de índice 
agrupado, pois, se um arquivo já estiver organizado por hashing, não 
será necessária uma estrutura de índice de hash separada.
 Entretanto, como a organização de arquivo de hash oferece o mesmo 
acesso direto que a indexação, fazemos de conta que um arquivo 
organizado por hashing também possui um índice de hash agrupado organizado por hashing também possui um índice de hash agrupado 
sobre ele.
de Hash
não só para a organização de arquivos, 
mas também para a criação de estruturas de índices.
organiza as chaves de busca, com seus 
ponteiros de registros associados, numa estrutura de arquivo hash.ponteiros de registros associados, numa estrutura de arquivo hash.
Falando estritamente, os índices de hash são sempre índices 
Um índice de hash não é necessário com uma estrutura de índice 
agrupado, pois, se um arquivo já estiver organizado por hashing, não 
será necessária uma estrutura de índice de hash separada.
Entretanto, como a organização de arquivo de hash oferece o mesmo 
acesso direto que a indexação, fazemos de conta que um arquivo 
organizado por hashing também possui um índice de hash agrupado organizado por hashing também possui um índice de hash agrupado 
Exemplo de índice dede Hash
Deficiências do H
 No hashing estático, a função h mapeia valores da chave de busca 
a um conjunto fixo B de endereços de bucket.
 Bancos de dados crescem com o tempo. Se o número inicial de buckets 
é muito pequeno, o desempenho degradará devido a muitos overflows.
 Se o tamanho do arquivo em algum ponto no futuro é antecipado e o 
número de buckets atribuído de acordo com isso, uma quantidade 
significante de espaço será desperdiçado inicialmente.
 Se o banco de dados diminui, de novo o espaço será desperdiçado.
 Uma opção é a re-organização periódica do arquivo com uma nova 
função de hash, mas isto é muito custoso.
 Estes problemas podem ser evitados usando técnicas que permitem 
o número de buckets ser modificado dinamicamente.
Hashing Estático
mapeia valores da chave de busca 
de endereços de bucket.
Bancos de dados crescem com o tempo. Se o número inicial de buckets 
é muito pequeno, o desempenho degradará devido a muitos overflows.
Se o tamanho do arquivo em algum ponto no futuro é antecipado e o 
número de buckets atribuído de acordo com isso, uma quantidade 
significante de espaço será desperdiçado inicialmente.
Se o banco de dados diminui, de novo o espaço será desperdiçado.
organização periódica do arquivo com uma nova 
função de hash, mas isto é muito custoso.
Estes problemas podem ser evitados usando técnicas que permitem 
o número de buckets ser modificado dinamicamente.
Hashing D
 Bom para bancos de dados que crescem e diminuem no tamanho
 Permite que função de hash seja modificada dinamicamente
 Aproveitam que o resultado de uma função de hashing é um inteiro não 
negativo e pode ser representado como um número binário.negativo e pode ser representado como um número binário.
 Hashing Extensível – uma forma de hashing dinâmico
 Função de Hash gera valores por um intervalo relativamente grande 
inteiros binários de b-bit, com b = 32 (profundidade global).
 Em qualquer instante é usado somente um prefixoda função de hash para 
indexar na tabela de endereços de buckets
 Seja o tamanho do prefixo i bits, 0  i 
 O tamanho da tabela de endereços de Bucket = 2
 O valor de i cresce e diminui na medida que o tamanho do banco de dados 
cresce e diminui.
 Entradas múltiplas na tabela de endereços de bucket podem apontar a um 
bucket.
 Assim, o número real de buckets é < 2
 O número de buckets também muda dinamicamente devido à junção e 
divisão de buckets.
Dinâmico
Bom para bancos de dados que crescem e diminuem no tamanho
Permite que função de hash seja modificada dinamicamente
Aproveitam que o resultado de uma função de hashing é um inteiro não 
negativo e pode ser representado como um número binário.negativo e pode ser representado como um número binário.
uma forma de hashing dinâmico
Função de Hash gera valores por um intervalo relativamente grande — a saber, 
= 32 (profundidade global).
Em qualquer instante é usado somente um prefixo da função de hash para 
indexar na tabela de endereços de buckets
i  32.
O tamanho da tabela de endereços de Bucket = 2i. Inicialmente i = 0
cresce e diminui na medida que o tamanho do banco de dados 
Entradas múltiplas na tabela de endereços de bucket podem apontar a um 
Assim, o número real de buckets é < 2i
O número de buckets também muda dinamicamente devido à junção e 
Uso da Estrutura de
 Cada bucket j armazena um valor ij; 
mesmo bucket têm os mesmos valores nos primeiros mesmo bucket têm os mesmos valores nos primeiros 
 Para localizar o bucket contendo a chave de busca 
1. Calcular h(Kj) = X
2. Use os primeiros i bits de ordem maior de 
de endereços de bucket, e segue o ponteiro de bucket na entrada da tabela
 Para inserir um registro com valor de chave de busca 
 Segue o mesmo procedimento para buscar e localizar o bucket, digamos 
 Se houver espaço no bucket j insere o registro nele.
Senão o bucket deve ser dividido e os registros atuais e o novo devem ser  Senão o bucket deve ser dividido e os registros atuais e o novo devem ser 
redistribuídos (próximo slide.)
 Buckets de Overflow usados em alguns casos (veremos brevemente)
de Hash Extensível
; todas as entradas que apontam ao 
mesmo bucket têm os mesmos valores nos primeiros ij bits.mesmo bucket têm os mesmos valores nos primeiros ij bits.
Para localizar o bucket contendo a chave de busca Kj:
bits de ordem maior de X como um desplazamento na tabela 
de endereços de bucket, e segue o ponteiro de bucket na entrada da tabela
Para inserir um registro com valor de chave de busca Kj
Segue o mesmo procedimento para buscar e localizar o bucket, digamos j.
insere o registro nele.
Senão o bucket deve ser dividido e os registros atuais e o novo devem ser Senão o bucket deve ser dividido e os registros atuais e o novo devem ser 
Buckets de Overflow usados em alguns casos (veremos brevemente)
Estrutura Geral do
Nesta estrutura, i2 = i3 = i, enquanto 
(veja próximo slide para detalhes)
Hash Extensível
, enquanto i1 = i – 1 
(veja próximo slide para detalhes)
Atualizações na Estrutura de Hash 
Extensível
Para dividir um bucket j quando inserimos um registro com valor da chave de 
Se i > i (mais de um ponteiro para o bucket Se i > ij (mais de um ponteiro para o bucket 
 Atribuir um novo bucket z, e colocar 
 Fazer a segunda metade dos endereços de bucket das entradas da tabela que 
apontavam a j para apontar a z
 Remover e inserir de novo cada registro no bucket 
 Recalcular o novo bucket para Kj e inserir o registro no bucket (divisões 
adicionais são necessárias se o bucket ainda está cheio)
Se i = ij (somente um ponteiro para o bucket 
 incrementar i e dobrar o tamanho da tabela de endereço de buckets.
 Trocar cada entrada da tabela por duas entradas que apontem ao mesmo 
bucket.
 Recalcular nova entrada na tabela de endereços de buckets para 
> ij assim usar o primeiro caso acima.
Atualizações na Estrutura de Hash 
Extensível
quando inserimos um registro com valor da chave de Kj:
(mais de um ponteiro para o bucket j)(mais de um ponteiro para o bucket j)
, e colocar ij e iz para ser o velho ij + 1.
Fazer a segunda metade dos endereços de bucket das entradas da tabela que 
Remover e inserir de novo cada registro no bucket j.
e inserir o registro no bucket (divisões 
adicionais são necessárias se o bucket ainda está cheio)
(somente um ponteiro para o bucket j)
e dobrar o tamanho da tabela de endereço de buckets.
Trocar cada entrada da tabela por duas entradas que apontem ao mesmo 
Recalcular nova entrada na tabela de endereços de buckets para Kj Agora i
Atualizações na Estrutura de Hash 
Extensível (Cont.)
 Quando inserimos um valor, se o bucket continua cheio após várias 
divisões (isto é, i alcança algum limite divisões (isto é, i alcança algum limite 
lugar de dividir a tabela de entradas de buckets ainda mais.
 Para remover uma chave,
 Achar ela no bucket e remover ela.
 O bucket pode ser removido se ele ficar vazio (com atualizações apropriadas na 
tabela de endereços de bucket).
 A união de buckets pode ser feita (pode se unir somente com um bucket que 
tenha o mesmo valor de ij e igual prefixo i
 A diminuição do tamanho da tabela de endereços de bucket também é possívelA diminuição do tamanho da tabela de endereços de bucket também é possível
 PS: esta diminuição é uma operação custosa e deveria ser feita somente se 
o número de buckets ficar muito menor que o tamanho fa tabela
Atualizações na Estrutura de Hash 
Extensível (Cont.)
Quando inserimos um valor, se o bucket continua cheio após várias 
alcança algum limite b) criar um bucket de overflow no alcança algum limite b) criar um bucket de overflow no 
lugar de dividir a tabela de entradas de buckets ainda mais.
O bucket pode ser removido se ele ficar vazio (com atualizações apropriadas na 
A união de buckets pode ser feita (pode se unir somente com um bucket que 
e igual prefixo ij –1, se ele existir)
A diminuição do tamanho da tabela de endereços de bucket também é possívelA diminuição do tamanho da tabela de endereços de bucket também é possível
PS: esta diminuição é uma operação custosa e deveria ser feita somente se 
o número de buckets ficar muito menor que o tamanho fa tabela
Uso da Estrutura de Hash Extensível: 
Exemplo
Estrututra de Hash inicial, ta
Uso da Estrutura de Hash Extensível: 
Exemplo
amanho do bucket = 2
Exemplo (Cont.)
 Estrutura de Hash depois da inserção de um registro Brighton e dois 
DowntownDowntown
Estrutura de Hash depois da inserção de um registro Brighton e dois 
Exemplo (Cont.)
 Estrutura de Hash depois da inseerção do registro Mianus
Exemplo (Cont.)
Estrutura de Hash após inserçãão de três registros Perryridge
Exemplo (Cont.)
 Estrutura de Hash structure após inserção dos registros Redwood e 
Round HillRound Hill
Estrutura de Hash structure após inserção dos registros Redwood e 
Hashing extensível v
 Benefícios do hashing extensível :
 Desempenho do Hash não degrada com o crescimento do 
arquivo
 Mínimo overhead de espaço
 Desvantagens do hashing extensível
Nível extra de indireção para achar os registros desejados
A tabela de endereços de bucket pode ficar muito grande (maior 
que a memória)
 Precisa de uma estrutura em árvore para achar o registro desejado 
na estrutura!
Mudar o tamanho da tabela de endereços de buckets é uma 
operação custosa
Hashing Linear é um mecanismo alternativo que evita 
estas desvantagens ao custo possível de mais buckets 
de overflows
vs. Outros Esquemas
Benefícios do hashing extensível :
Desempenho do Hash não degrada com o crescimento do 
Desvantagens do hashing extensível
Nível extra de indireção para achar os registros desejados
A tabela de endereços de bucket pode ficar muito grande (maior 
Precisa de uma estrutura em árvore para achar o registro desejado 
Mudar o tamanho da tabela de endereços de buckets é uma 
é um mecanismo alternativo que evita 
estas desvantagens ao custo possível de mais buckets 
HashingDDinâmico
Organização por ha
 Hashing Linear
 Permitir que um arquivo de
número de buckets dinamicamentenúmero de buckets dinamicamente
diretório.
 São alocados inicialmente
endereçados por uma função
inicial;
 Quando um “Limite Máximo” de ocupação do arquivo é 
alcançado, um novo bucket 
chaves para dividir o número de chaves com o bucket 0;
 A divisão de chaves é feita com base em uma nova função A divisão de chaves é feita com base em uma nova função
 h1 = K mod 2M, que será usada para tratar colisões no 
bucket 0;
 O bucket M é encadeado ao bucket 
 Quando a taxa de ocupação torna
buckets seguintes (1, 2, 3, ... ) vão sofrendo overflow;
ashing
de hash expanda e encolha seu
dinamicamente sem precisar de umdinamicamente sem precisar de um
M buckets (0, 1, ... , M - 1),
função h0 = K mod M chamada
Quando um “Limite Máximo” de ocupação do arquivo é 
alcançado, um novo bucket M é criado para dividir as 
chaves para dividir o número de chaves com o bucket 0;
A divisão de chaves é feita com base em uma nova funçãoA divisão de chaves é feita com base em uma nova função
, que será usada para tratar colisões no 
encadeado ao bucket M - 1;
Quando a taxa de ocupação torna-se novamente crítica, os 
buckets seguintes (1, 2, 3, ... ) vão sofrendo overflow;