Hashing em DBMS: técnicas de hash estáticas e dinâmicas
Fiona Brown
O que é hash no SGBD?
No SGBD, hashing é uma técnica para pesquisar diretamente a localização dos dados desejados no disco sem usar estrutura de índice. O método hash é usado para indexar e recuperar itens em um banco de dados, pois é mais rápido pesquisar aquele item específico usando a chave hash mais curta em vez de usar 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 no local da memória onde esses registros estão armazenados, conhecida como bloco de dados ou balde de dados.
Por que precisamos de Hashing?
Aqui estão as situações no SGBD em que você precisa aplicar o método Hashing:
- Para uma estrutura de banco de dados enorme, é difícil pesquisar todos os valores do índice em todos os seus níveis e então você precisa chegar ao bloco de dados de destino para obter os dados desejados.
- O método hash é usado para indexar e recuperar itens em um banco de dados, pois é mais rápido pesquisar aquele item específico usando a chave hash mais curta em vez de usar seu valor original.
- Hashing é um método ideal para calcular a localização direta de um registro de dados no disco sem usar estrutura de índice.
- É também uma técnica útil para implementar dicionários.
Terminologias importantes em hash
Aqui estão terminologias importantes que são usadas em Hashing:
- Balde de dados – Os buckets de dados são locais de memória onde os registros são armazenados. Também é conhecido como Unidade de Armazenamento.
- Chave: UMA Chave do SGBD é um atributo ou conjunto de atributos que ajuda a identificar uma linha (tupla) em uma relação (tabela). Isso permite que você encontre o relacionamento entre duas tabelas.
- Função hash: Uma função hash, é uma função de mapeamento que mapeia todo o conjunto de chaves de pesquisa para o endereço onde os registros reais são colocados.
- Sondagem Linear – A sondagem linear é um intervalo fixo entre sondagens. Neste método, o próximo bloco de dados disponível é usado para inserir o novo registro, em vez de sobrescrever o registro mais antigo.
- Sondagem quadrática– Ajuda você a determinar o novo endereço do bucket. Ele ajuda você a adicionar intervalo entre testes adicionando a saída consecutiva do polinômio quadrático ao valor inicial dado pelo cálculo original.
- Índice de hash – É um endereço do bloco de dados. Uma função hash pode ser uma função matemática simples ou até mesmo uma função matemática complexa.
- Double Hashing -Double hashing é um método de programação de computador usado em tabelas hash para resolver problemas de colisão.
- Estouro de balde: A condição de estouro de balde é chamada de colisão. Este é um estágio fatal para qualquer estática funcionar.
Tipos de técnicas de hash
Existem principalmente dois tipos de métodos/técnicas de hashing SQL:
- Hashing estático
- Hashing dinâmico
hash estático
No hash estático, o endereço do depósito de dados resultante permanecerá sempre o mesmo.
Portanto, se você gerar um endereço para dizer ID_Aluno = 10 usando função hash mod(3), o endereço do bucket resultante será sempre 1. Portanto, você não verá nenhuma alteração no endereço do bucket.
Portanto, neste método de hash estático, o número de depósitos de dados na memória sempre permanece constante.
Funções hash estáticas
- Inserindo um registro: quando um novo registro precisa ser inserido na tabela, você pode gerar um endereço para o novo registro usando sua chave hash. Quando o endereço é gerado, o registro é automaticamente armazenado naquele local.
- Busca: quando você precisar recuperar o registro, a mesma função hash deve ser útil para recuperar o endereço do bucket onde os dados devem ser armazenados.
- Apagar um registro: Usando a função hash, você pode primeiro buscar o registro que deseja excluir. Então você pode remover os registros desse endereço na memória.
O hash estático é ainda dividido em
- Hash aberto
- Fechar hash.
Hashing aberto
No método de hash aberto, em vez de substituir o antigo, o próximo bloco de dados disponível é usado para inserir o novo registro. Este 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 já está ocupado por algum outro valor. É por isso que o sistema procura o próximo depósito de dados 501 e atribui A2 a ele.
Fechar hash
No método de hash fechado, quando os buckets estão cheios, um novo bucket é alocado para o mesmo hash e o resultado é vinculado após o anterior.
Hashing dinâmico
O hash dinâmico oferece um mecanismo no qual os intervalos de dados são adicionados e removidos dinamicamente e sob demanda. Neste hash, a função hash ajuda você a criar um grande número de valores.
Diferença entre indexação ordenada e hash
Abaixo estão as principais diferenças entre indexação e hash
| parâmetros | Indexação de pedidos | Hashing |
|---|---|---|
| Armazenamento de endereço | Os endereços na memória são classificados de acordo com um valor-chave denominado chave primária | Os endereços são sempre gerados usando uma função hash no valor da chave. |
| Desempenho | Pode diminuir quando os dados aumentam no arquivo hash. Pois armazena os dados de forma ordenada quando há alguma operação (inserir/excluir/atualizar) realizada que diminua seu desempenho. | O desempenho do hash será melhor quando houver adição e exclusão constante de dados. No entanto, quando o banco de dados é enorme, a organização do arquivo hash e sua manutenção serão mais caras. |
| use para | Preferido para recuperação de dados por intervalo - o que significa que sempre que houver dados de recuperação para um intervalo específico, este método é uma opção ideal. | Este é um método ideal quando você deseja recuperar um registro específico com base na chave de pesquisa. No entanto, ele só terá um bom desempenho quando a função hash estiver na chave de pesquisa. |
| Gerenciamento de memória | Haverá muitos blocos de dados não utilizados devido à operação de exclusão/atualização. Esses blocos de dados não podem ser liberados para reutilização. É por isso que a manutenção regular da memória é necessária. | Nos métodos de hash estáticos e dinâmicos, a memória é sempre gerenciada. O estouro de balde também é tratado perfeitamente para estender o hash estático. |
O que é colisão?
Colisão de hash é um estado em que os hashes resultantes de dois ou mais dados no conjunto de dados mapeiam erroneamente o mesmo local no tabela de hash.
Como lidar com a colisão de hash?
Existem duas técnicas que você pode usar para evitar uma colisão de hash:
- Refazendo: Este método invoca uma função hash secundária, que é aplicada continuamente até que um slot vazio seja encontrado, onde um registro deve ser colocado.
- Encadeamento: o método de encadeamento cria uma lista vinculada de itens cuja chave tem hash para o mesmo valor. Este método requer um campo de link extra para cada posição da tabela.
Resumo
- In DBMS, hashing é uma técnica para pesquisar diretamente a localização dos dados desejados no disco sem usar estrutura de índice.
- O método hash é usado para indexar e recuperar itens em um banco de dados, pois é mais rápido pesquisar aquele item específico usando a chave hash mais curta em vez de usar seu valor original.
- Balde de dados, chave, função hash, sondagem linear, sondagem quadrática, índice hash, Double Hashing e Bucket Overflow são terminologias importantes usadas em hash
- Dois tipos de métodos de hash são 1) hash estático 2) hash dinâmico
- No hash estático, o endereço do depósito de dados resultante permanecerá sempre o mesmo.
- O hash dinâmico oferece um mecanismo no qual os intervalos de dados são adicionados e removidos dinamicamente e sob demanda.
- Na ordem, os endereços de indexação na memória são classificados de acordo com um valor crítico, enquanto no hash os endereços são sempre gerados usando uma função hash no valor da chave.
- Colisão de hash é um estado em que os hashes resultantes de dois ou mais dados no conjunto de dados mapeiam erroneamente o mesmo local na tabela de hash.
- Rehashing e encadeamento são dois métodos que ajudam a evitar colisões de hash.
