DBMS - Hashing

Para uma estrutura de banco de dados enorme, pode ser quase impossível pesquisar todos os valores de índice em todos os seus níveis e, em seguida, alcançar o bloco de dados de destino para recuperar os dados desejados. Hashing é uma técnica eficaz para calcular a localização direta de um registro de dados no disco sem usar a estrutura de índice.

O hash usa funções hash com chaves de pesquisa como parâmetros para gerar o endereço de um registro de dados.

Organização Hash

  • Bucket- Um arquivo hash armazena dados em formato de intervalo. Balde é considerado uma unidade de armazenamento. Um balde normalmente armazena um bloco de disco completo, que por sua vez pode armazenar um ou mais registros.

  • Hash Function - Uma função hash, h, é uma função de mapeamento que mapeia todo o conjunto de chaves de busca Kpara o endereço onde os registros reais são colocados. É uma função de chaves de pesquisa para endereços de bucket.

Hashing estático

No hashing estático, quando um valor de chave de pesquisa é fornecido, a função hash sempre calcula o mesmo endereço. Por exemplo, se a função hash mod-4 for usada, ela deve gerar apenas 5 valores. O endereço de saída deve ser sempre o mesmo para essa função. O número de baldes fornecidos permanece inalterado o tempo todo.

Operação

  • Insertion - Quando um registro precisa ser inserido usando hash estático, a função hash h calcula o endereço do intervalo para a chave de pesquisa K, onde o registro será armazenado.

    Endereço do intervalo = h (K)

  • Search - Quando um registro precisa ser recuperado, a mesma função hash pode ser usada para recuperar o endereço do depósito onde os dados estão armazenados.

  • Delete - Esta é simplesmente uma pesquisa seguida por uma operação de exclusão.

Estouro de balde

A condição de estouro do balde é conhecida como collision. Este é um estado fatal para qualquer função hash estática. Nesse caso, o encadeamento de estouro pode ser usado.

  • Overflow Chaining- Quando os depósitos estão cheios, um novo depósito é alocado para o mesmo resultado hash e é vinculado após o anterior. Este mecanismo é chamadoClosed Hashing.

  • Linear Probing- Quando uma função hash gera um endereço no qual os dados já estão armazenados, o próximo depósito livre é alocado para ela. Este mecanismo é chamadoOpen Hashing.

Hashing dinâmico

O problema com o hashing estático é que ele não se expande ou encolhe dinamicamente conforme o tamanho do banco de dados aumenta ou diminui. O hash dinâmico fornece um mecanismo no qual depósitos de dados são adicionados e removidos dinamicamente e sob demanda. Hashing dinâmico também é conhecido comoextended hashing.

A função de hash, em hash dinâmico, é feita para produzir um grande número de valores e apenas alguns são usados ​​inicialmente.

Organização

O prefixo de um valor hash inteiro é considerado um índice hash. Apenas uma parte do valor hash é usada para calcular endereços de bucket. Cada índice hash tem um valor de profundidade para indicar quantos bits são usados ​​para calcular uma função hash. Esses bits podem endereçar 2n buckets. Quando todos esses bits são consumidos - ou seja, quando todos os baldes estão cheios - o valor da profundidade é aumentado linearmente e duas vezes os baldes são alocados.

Operação

  • Querying - Observe o valor de profundidade do índice hash e use esses bits para calcular o endereço do balde.

  • Update - Execute uma consulta como acima e atualize os dados.

  • Deletion - Faça uma consulta para localizar os dados desejados e exclua os mesmos.

  • Insertion - Calcular o endereço do depósito

    • Se o balde já estiver cheio.
      • Adicione mais baldes.
      • Adicione bits adicionais ao valor de hash.
      • Recalcule a função hash.
    • Outro
      • Adicione dados ao intervalo,
    • Se todos os depósitos estiverem cheios, execute as soluções de hash estático.

O hash não é favorável quando os dados são organizados em alguma ordem e as consultas exigem uma variedade de dados. Quando os dados são discretos e aleatórios, o hash tem o melhor desempenho.

Os algoritmos de hash têm alta complexidade do que a indexação. Todas as operações de hash são feitas em tempo constante.