Hashing em DBMS: técnicas de hash estáticas e dinâmicas
Fiona Brown
⚡ Resumo Inteligente
Em um SGBD (Sistema de Gerenciamento de Banco de Dados), o hashing é uma técnica que calcula a localização em disco de um registro diretamente a partir de sua chave, sem percorrer um índice. Uma função hash mapeia chaves de busca para buckets de dados, e o hashing estático ou dinâmico gerencia como esses buckets crescem.
O que é hash no SGBD?
Em SGBDs (Sistemas de Gerenciamento de Banco de Dados), o hashing é uma técnica para buscar diretamente a localização dos dados desejados no disco sem usar uma estrutura de índice. O método de hashing é usado para indexar e recuperar itens em um banco de dados, pois é mais rápido buscar um item específico usando a chave hash mais curta em vez de seu valor original. Os dados são armazenados na forma de blocos de dados cujo endereço é gerado pela aplicação de uma função hash; o local de memória onde esses registros são armazenados é conhecido como endereço. bloco de dados ou balde de dados.
Por que precisamos de hash?
Aqui estão as situações em um SGBD onde você precisa aplicar o método de hashing:
- Em uma estrutura de banco de dados enorme, é difícil pesquisar todos os valores de índice em todos os seus níveis e, em seguida, alcançar o bloco de dados de destino para obter os dados desejados.
- O hashing é usado para indexar e recuperar itens em um banco de dados, pois é mais rápido pesquisar um item específico usando a chave hash mais curta do que o valor original.
- O hashing é um método ideal para calcular a localização direta de um registro de dados no disco sem usar uma estrutura de índice.
- É também uma técnica útil para implementar dicionários.
Terminologias importantes em hash
Aqui estão alguns termos importantes usados em hashing:
- Recipiente de dados: Os buckets de dados são locais de memória onde os registros são armazenados. Também são conhecidos como unidades de armazenamento.
- Chave: a Chave do SGBD É um atributo ou conjunto de atributos que ajuda a identificar uma linha (tupla) em uma relação (tabela).
- Função hash: um mapaping Função que mapeia todo o conjunto de chaves de pesquisa para o endereço onde os registros reais estão localizados.
- Sondagem Linear: um intervalo fixo entre as sondagens. Nesse método, o próximo bloco de dados disponível é usado para inserir o novo registro, em vez de sobrescrever o registro anterior.
- Sondagem quadrática: Ajuda a determinar o novo endereço do bucket adicionando a saída consecutiva de um polinômio quadrático ao valor inicial fornecido pelo cálculo original.
- Índice hash: O endereço do bloco de dados. Uma função hash pode ser uma função matemática simples ou complexa.
- Double Hash: Um método usado em tabelas hash para resolver colisões aplicando uma segunda função hash.
- Transbordamento do balde: A condição de estouro do bucket é chamada de colisão. Este é um estágio fatal para qualquer função hash estática.
Tipos de técnicas de hash
Existem principalmente dois tipos de técnicas de hashing em SGBD:
- Hashing estático
- Hashing dinâmico
A principal diferença entre os dois reside no fato de o número de baldes ser fixo ou não, como explicam as duas seções seguintes.
Hashing estático
Na computação hash estática, o endereço do bucket de dados resultante permanecerá sempre o mesmo.
Portanto, se você gerar um endereço para, digamos, ID_Aluno = 10 usando a função de hash mod(3), o endereço do bucket resultante será sempre 1Portanto, você não verá nenhuma alteração no endereço do bucket.
Portanto, no método de hash estático, o número de buckets de dados na memória permanece sempre constante.
Funções hash estáticas
- Inserindo um registro: Quando um novo registro precisa ser inserido na tabela, você gera um endereço para ele usando sua chave hash. Uma vez gerado o endereço, o registro é armazenado nesse local.
- Procurando: Quando você precisa recuperar o registro, a mesma função hash é usada para recuperar o endereço do bucket onde os dados estão armazenados.
- Excluir um registro: Ao usar a função hash, primeiro você busca o registro que deseja excluir e, em seguida, remove o registro desse endereço na memória.
O hash estático se divide ainda em:
- Hash aberto
- Hash fechado
Hashing aberto
No método de hashing aberto, em vez de sobrescrever o registro mais antigo, o próximo bloco de dados disponível é usado para inserir o novo registro. Esse método também é conhecido como sondagem linear.
Por exemplo, A2 é um novo registro que você deseja inserir. A função hash gera o endereço 222, mas ele já está ocupado por outro valor. É por isso que o sistema procura o próximo bucket de dados, 501, e atribui A2 a ele.
Hash fechado
No método de hash fechado, quando os buckets estão cheios, um novo bucket é alocado para o mesmo hash e o resultado é encadeado após o anterior.
Hashing dinâmico
O hashing dinâmico oferece um mecanismo no qual blocos de dados são adicionados e removidos dinamicamente e sob demanda. Nesse método de hashing, a função hash ajuda a criar um grande número de valores, e a estrutura cresce ou diminui conforme os dados são inseridos. Isso o torna ideal para tabelas cujo tamanho não pode ser previsto, onde o hashing estático desperdiçaria espaço ou causaria estouro de capacidade.
Diferença entre indexação ordenada e hashing
Abaixo estão as principais diferenças entre indexação e hashing:
| Parâmetros Técnicos | Indexação ordenada | Hashing |
|---|---|---|
| Armazenamento de endereço | Os endereços na memória são classificados de acordo com um valor de chave chamado chave primária. | Os endereços são sempre gerados usando uma função hash no valor da chave. |
| Desempenho | Pode diminuir à medida que os dados aumentam, porque os dados são armazenados ordenados e cada inserção, exclusão ou atualização os reordena. | O desempenho é melhor com adição e exclusão constantes de dados. Para um banco de dados muito grande, a manutenção do arquivo hash torna-se mais dispendiosa. |
| use para | Preferencial para recuperação de intervalo, onde os dados são recuperados para um intervalo específico. | Ideal para recuperar um registro específico com base na chave de pesquisa, e funciona bem apenas quando a função hash é aplicada à chave de pesquisa. |
| Gerenciamento de memória | Muitos blocos de dados não utilizados surgem de operações de exclusão e atualização e não podem ser liberados para reutilização, sendo necessária, portanto, manutenção regular. | Tanto no hashing estático quanto no dinâmico, o gerenciamento de memória é constante e o estouro do bucket é tratado para ampliar a funcionalidade do hashing estático. |
Resumindo, escolha a ordem. indexação para consultas de intervalo e hashing para pesquisas de correspondência exata na chave.
O que é colisão?
Uma colisão de hash é uma situação em que os hashes resultantes de dois ou mais itens no conjunto de dados são mapeados incorretamente para o mesmo local. tabela de hash.
Como lidar com uma colisão de hash
Existem duas técnicas que você pode usar para evitar uma colisão de hash:
- Repetindo: Este método invoca uma função hash secundária, que é aplicada continuamente até que um espaço vazio seja encontrado onde um registro possa ser inserido.
- Encadeamento: O método de encadeamento cria uma lista ligada de itens cujas chaves têm o mesmo valor de hash. Esse método requer um campo de ligação adicional em cada posição da tabela.
