Hashing nei DBMS: tecniche di hashing statico e dinamico
Fiona Marrone
Cos'è l'hashing nel DBMS?
Nei DBMS, l'hashing è una tecnica per cercare direttamente la posizione dei dati desiderati sul disco senza utilizzare la struttura dell'indice. Il metodo hash viene utilizzato per indicizzare e recuperare elementi in un database poiché è più veloce cercare quell'elemento specifico utilizzando la chiave con hash più breve invece di utilizzare il suo valore originale. I dati vengono archiviati sotto forma di blocchi di dati il cui indirizzo viene generato applicando una funzione hash nella posizione di memoria in cui sono archiviati questi record, nota come blocco dati o bucket di dati.
Perché abbiamo bisogno dell'hashing?
Ecco le situazioni nel DBMS in cui è necessario applicare il metodo Hashing:
- Per una struttura di database enorme, è difficile cercare tutti i valori dell'indice in tutto il suo livello e quindi è necessario raggiungere il blocco dati di destinazione per ottenere i dati desiderati.
- Il metodo hash viene utilizzato per indicizzare e recuperare elementi in un database poiché è più veloce cercare quell'elemento specifico utilizzando la chiave con hash più breve invece di utilizzare il suo valore originale.
- L'hashing è un metodo ideale per calcolare la posizione diretta di un record di dati sul disco senza utilizzare la struttura dell'indice.
- È anche una tecnica utile per implementare i dizionari.
Terminologie importanti nell'hashing
Ecco le terminologie importanti utilizzate nell'hashing:
- Secchio di dati – I bucket di dati sono posizioni di memoria in cui vengono archiviati i record. È noto anche come unità di stoccaggio.
- Le: Un Chiave DBMS è un attributo o un insieme di attributi che aiuta a identificare una riga (tupla) in una relazione (tabella). Ciò consente di trovare la relazione tra due tabelle.
- Funzione hash: Una funzione hash è una funzione di mappatura che mappa tutto l'insieme di chiavi di ricerca all'indirizzo in cui sono posizionati i record effettivi.
- Sondaggio lineare – La tastatura lineare è un intervallo fisso tra le sonde. In questo metodo, il successivo blocco dati disponibile viene utilizzato per inserire il nuovo record, invece di sovrascrivere il record precedente.
- Sondaggio quadratico– Ti aiuta a determinare il nuovo indirizzo del bucket. Ti aiuta ad aggiungere l'intervallo tra le sonde aggiungendo l'output consecutivo del polinomio quadratico al valore iniziale fornito dal calcolo originale.
- Indice hash – È un indirizzo del blocco dati. Una funzione hash potrebbe essere una semplice funzione matematica o persino una funzione matematica complessa.
- Double hashing -Double l'hashing è un metodo di programmazione del computer utilizzato nelle tabelle hash per risolvere i problemi di collisione.
- Traboccamento del secchio: La condizione di traboccamento del secchio è detta collisione. Questa è una fase fatale per qualsiasi statica che deve funzionare.
Tipi di tecniche di hashing
Esistono principalmente due tipi di metodi/tecniche di hashing SQL:
- Hashing statico
- Hashing dinamico
Hashing statico
Nell'hashing statico, l'indirizzo del bucket di dati risultante rimarrà sempre lo stesso.
Pertanto, se generi un indirizzo per say ID_studente = 10 utilizzando la funzione di hashing mod(3), l'indirizzo del bucket risultante sarà sempre 1. Pertanto, non vedrai alcun cambiamento nell'indirizzo del bucket.
Pertanto, in questo metodo di hashing statico, il numero di bucket di dati in memoria rimane sempre costante.
Funzioni hash statiche
- Inserimento di un record: Quando è necessario inserire un nuovo record nella tabella, è possibile generare un indirizzo per il nuovo record utilizzando la sua chiave hash. Quando viene generato l'indirizzo, il record viene automaticamente archiviato in quella posizione.
- Ricerca: quando è necessario recuperare il record, la stessa funzione hash dovrebbe essere utile per recuperare l'indirizzo del bucket in cui devono essere archiviati i dati.
- Elimina un record: Utilizzando la funzione hash, puoi prima recuperare il record che desideri eliminare. Quindi puoi rimuovere i record per quell'indirizzo in memoria.
L'hashing statico è ulteriormente suddiviso in
- Hashing aperto
- Chiudi l'hashing.
Apri Hashing
Nel metodo di hashing aperto, invece di sovrascrivere quello precedente, viene utilizzato il successivo blocco di dati disponibile per inserire il nuovo record. Questo metodo è noto anche come sondaggio lineare.
Ad esempio, A2 è un nuovo record che desideri inserire. La funzione hash genera l'indirizzo 222. Ma è già occupato da qualche altro valore. Ecco perché il sistema cerca il successivo bucket di dati 501 e gli assegna A2.
Chiudi Hashing
Nel metodo di hashing chiuso, quando i bucket sono pieni, viene allocato un nuovo bucket per lo stesso hash e i risultati vengono collegati dopo quello precedente.
Hashing dinamico
L'hashing dinamico offre un meccanismo in cui i bucket di dati vengono aggiunti e rimossi in modo dinamico e su richiesta. In questo hashing, la funzione hash ti aiuta a creare un gran numero di valori.
Differenza tra indicizzazione ordinata e hashing
Di seguito sono riportate le principali differenze tra indicizzazione e hashing
| parametri | Indicizzazione degli ordini | hashing |
|---|---|---|
| Memorizzazione dell'indirizzo | Gli indirizzi nella memoria vengono ordinati in base a un valore chiave chiamato chiave primaria | Gli indirizzi vengono sempre generati utilizzando una funzione hash sul valore della chiave. |
| Cookie di prestazione | Può diminuire quando i dati aumentano nel file hash. Poiché memorizza i dati in una forma ordinata quando viene eseguita un'operazione (inserimento/eliminazione/aggiornamento) che ne diminuisce le prestazioni. | Le prestazioni dell'hashing saranno migliori in caso di aggiunta ed eliminazione costante di dati. Tuttavia, quando il database è enorme, l’organizzazione dei file hash e la sua manutenzione saranno più costose. |
| Utilizzare per | Preferito per il recupero di intervalli di dati, il che significa che ogni volta che sono presenti dati di recupero per un intervallo particolare, questo metodo è un'opzione ideale. | Questo è un metodo ideale quando desideri recuperare un particolare record in base alla chiave di ricerca. Tuttavia, funzionerà bene solo quando la funzione hash è sulla chiave di ricerca. |
| Gestione della memoria | Ci saranno molti blocchi di dati inutilizzati a causa dell'operazione di eliminazione/aggiornamento. Questi blocchi di dati non possono essere rilasciati per il riutilizzo. Ecco perché è necessaria una manutenzione regolare della memoria. | Nei metodi di hashing statico e dinamico la memoria viene sempre gestita. Anche l'overflow del bucket viene gestito perfettamente per estendere l'hashing statico. |
Cos'è la collisione?
La collisione di hash è uno stato in cui gli hash risultanti da due o più dati nel set di dati mappano erroneamente la stessa posizione nel tabella hash.
Come gestire la collisione di hashing?
Esistono due tecniche che è possibile utilizzare per evitare una collisione di hash:
- Ripassando: questo metodo richiama una funzione hash secondaria, che viene applicata continuamente finché non viene trovato uno slot vuoto, dove posizionare un record.
- chaining: il metodo di concatenamento crea un elenco collegato di elementi la cui chiave ha lo stesso valore. Questo metodo richiede un campo di collegamento aggiuntivo per ciascuna posizione della tabella.
Sommario
- In DBMS, l'hashing è una tecnica per cercare direttamente la posizione dei dati desiderati sul disco senza utilizzare la struttura dell'indice.
- Il metodo hash viene utilizzato per indicizzare e recuperare elementi in un database poiché è più veloce cercare quell'elemento specifico utilizzando la chiave con hash più breve invece di utilizzare il suo valore originale.
- Bucket dati, chiave, funzione hash, sondaggio lineare, sondaggio quadratico, indice hash, Double Hashing e Bucket Overflow sono terminologie importanti utilizzate nell'hashing
- Due tipi di metodi di hashing sono 1) hashing statico 2) hashing dinamico
- Nell'hashing statico, l'indirizzo del bucket di dati risultante rimarrà sempre lo stesso.
- L'hashing dinamico offre un meccanismo in cui i bucket di dati vengono aggiunti e rimossi in modo dinamico e su richiesta.
- Nell'ordine di indicizzazione gli indirizzi in memoria vengono ordinati in base ad un valore critico mentre nell'hashing gli indirizzi vengono sempre generati utilizzando una funzione hash sul valore della chiave.
- La collisione di hash è uno stato in cui gli hash risultanti da due o più dati nel set di dati mappano erroneamente la stessa posizione nella tabella hash.
- Il rehashing e il concatenamento sono due metodi che aiutano a evitare la collisione dell'hashing.
