DBMS - Hashing

Per una struttura di database enorme, può essere quasi impossibile cercare tutti i valori dell'indice attraverso tutto il suo livello e quindi raggiungere il blocco dati di destinazione per recuperare i dati desiderati. L'hashing è una tecnica efficace per calcolare la posizione diretta di un record di dati sul disco senza utilizzare la struttura dell'indice.

L'hashing utilizza funzioni hash con chiavi di ricerca come parametri per generare l'indirizzo di un record di dati.

Organizzazione hash

  • Bucket- Un file hash memorizza i dati in formato bucket. Il secchio è considerato un'unità di archiviazione. Un bucket in genere archivia un blocco disco completo, che a sua volta può archiviare uno o più record.

  • Hash Function - Una funzione hash, h, è una funzione di mappatura che mappa tutto l'insieme di chiavi di ricerca Kall'indirizzo in cui sono collocati i record effettivi. È una funzione che va dalle chiavi di ricerca agli indirizzi dei bucket.

Hashing statico

Nell'hashing statico, quando viene fornito un valore di chiave di ricerca, la funzione hash calcola sempre lo stesso indirizzo. Ad esempio, se viene utilizzata la funzione hash mod-4, genererà solo 5 valori. L'indirizzo di uscita deve essere sempre lo stesso per quella funzione. Il numero di secchi forniti rimane sempre invariato.

Operazione

  • Insertion - Quando è necessario immettere un record utilizzando hash statico, la funzione hash h calcola l'indirizzo del bucket per la chiave di ricerca K, dove verrà archiviato il record.

    Indirizzo bucket = h (K)

  • Search - Quando un record deve essere recuperato, la stessa funzione hash può essere utilizzata per recuperare l'indirizzo del bucket in cui sono archiviati i dati.

  • Delete - Questa è semplicemente una ricerca seguita da un'operazione di cancellazione.

Benna troppo piena

La condizione di trabocco del secchio è nota come collision. Questo è uno stato fatale per qualsiasi funzione hash statica. In questo caso, è possibile utilizzare il concatenamento del trabocco.

  • Overflow Chaining- Quando i bucket sono pieni, viene allocato un nuovo bucket per lo stesso risultato hash e viene collegato dopo quello precedente. Questo meccanismo è chiamatoClosed Hashing.

  • Linear Probing- Quando una funzione hash genera un indirizzo in cui sono già archiviati i dati, viene allocato il successivo bucket libero. Questo meccanismo è chiamatoOpen Hashing.

Hashing dinamico

Il problema con l'hashing statico è che non si espande o si restringe dinamicamente man mano che la dimensione del database aumenta o si riduce. L'hashing dinamico fornisce un meccanismo in cui i bucket di dati vengono aggiunti e rimossi in modo dinamico e su richiesta. L'hashing dinamico è anche noto comeextended hashing.

La funzione hash, nell'hashing dinamico, è progettata per produrre un gran numero di valori e solo pochi vengono utilizzati inizialmente.

Organizzazione

Il prefisso di un intero valore hash viene considerato come indice hash. Solo una parte del valore hash viene utilizzata per calcolare gli indirizzi dei bucket. Ogni indice hash ha un valore di profondità per indicare quanti bit vengono utilizzati per calcolare una funzione hash. Questi bit possono indirizzare 2n bucket. Quando tutti questi bit sono consumati, ovvero quando tutti i secchi sono pieni, il valore della profondità viene aumentato linearmente e vengono allocati due volte i secchi.

Operazione

  • Querying - Guarda il valore della profondità dell'indice hash e usa quei bit per calcolare l'indirizzo del bucket.

  • Update - Eseguire una query come sopra e aggiornare i dati.

  • Deletion - Eseguire una query per individuare i dati desiderati ed eliminare gli stessi.

  • Insertion - Calcola l'indirizzo del bucket

    • Se il secchio è già pieno.
      • Aggiungi altri secchi.
      • Aggiungi bit aggiuntivi al valore hash.
      • Ricalcola la funzione hash.
    • Altro
      • Aggiungi dati al bucket,
    • Se tutti i secchi sono pieni, eseguire i rimedi dell'hashing statico.

L'hashing non è favorevole quando i dati sono organizzati in un certo ordine e le query richiedono un intervallo di dati. Quando i dati sono discreti e casuali, l'hash ha le prestazioni migliori.

Gli algoritmi di hash hanno un'elevata complessità rispetto all'indicizzazione. Tutte le operazioni di hash vengono eseguite a tempo costante.