Hashing in DBMS: Statische und dynamische Hashing-Techniken
Fiona Braun
⚡ Intelligente Zusammenfassung
Hashing in Datenbankmanagementsystemen (DBMS) ist eine Technik, die den Speicherort eines Datensatzes auf der Festplatte direkt aus seinem Schlüssel berechnet, ohne einen Index zu durchlaufen. Eine Hash-Funktion ordnet Suchschlüssel Daten-Buckets zu, und statisches oder dynamisches Hashing steuert, wie diese Buckets wachsen.
Was ist Hashing im DBMS?
In Datenbankmanagementsystemen (DBMS) ist Hashing eine Technik, um die Position gewünschter Daten auf der Festplatte direkt zu finden, ohne eine Indexstruktur zu verwenden. Das Hashing-Verfahren dient zum Indizieren und Abrufen von Elementen in einer Datenbank, da die Suche nach einem bestimmten Element mithilfe des kürzeren Hash-Schlüssels schneller ist als mit dem ursprünglichen Wert. Daten werden in Form von Datenblöcken gespeichert, deren Adresse durch Anwendung einer Hash-Funktion generiert wird; der Speicherort, an dem diese Datensätze gespeichert sind, wird als Adresse bezeichnet. Datenblock oder Daten-Bucket.
Warum brauchen wir Hashing?
Hier sind die Situationen in einem DBMS, in denen Sie die Hash-Methode anwenden müssen:
- Bei einer riesigen Datenbankstruktur ist es schwierig, alle Indexwerte über alle Ebenen hinweg zu durchsuchen und dann den Zieldatenblock zu erreichen, um die gewünschten Daten zu erhalten.
- Hashing wird verwendet, um Elemente in einer Datenbank zu indizieren und abzurufen, da die Suche nach einem bestimmten Element mit dem kürzeren Hash-Schlüssel schneller ist als mit dem ursprünglichen Wert.
- Hashing ist eine ideale Methode, um die direkte Position eines Datensatzes auf der Festplatte zu berechnen, ohne eine Indexstruktur zu verwenden.
- Es ist auch eine hilfreiche Technik für die Implementierung von Wörterbüchern.
Wichtige Terminologien beim Hashing
Hier sind wichtige Begriffe, die beim Hashing verwendet werden:
- Daten-Bucket: Daten-Buckets sind Speicherbereiche, in denen Datensätze gespeichert werden. Sie werden auch als Speichereinheit bezeichnet.
- Schlüssel: a DBMS-Schlüssel ist ein Attribut oder eine Menge von Attributen, die Ihnen helfen, eine Zeile (ein Tupel) in einer Relation (Tabelle) zu identifizieren.
- Hash-Funktion: eine Karteping Funktion, die alle Suchschlüssel der Adresse zuordnet, an der die tatsächlichen Datensätze gespeichert sind.
- Lineare Sondierung: Ein festes Intervall zwischen den Messungen. Bei dieser Methode wird der nächste verfügbare Datenblock verwendet, um den neuen Datensatz einzufügen, anstatt den älteren Datensatz zu überschreiben.
- Quadratische Sondierung: hilft dabei, die neue Bucket-Adresse zu bestimmen, indem die aufeinanderfolgenden Ausgaben eines quadratischen Polynoms zum Startwert der ursprünglichen Berechnung addiert werden.
- Hash-Index: Die Adresse des Datenblocks. Eine Hash-Funktion kann eine einfache oder eine komplexe mathematische Funktion sein.
- Double Hashing: Eine Methode, die in Hashtabellen verwendet wird, um Kollisionen durch Anwendung einer zweiten Hashfunktion aufzulösen.
- Eimerüberlauf: Der Zustand des Bucket-Überlaufs wird als Kollision bezeichnet. Dies ist ein kritischer Zustand für jede statische Hash-Funktion.
Arten von Hashing-Techniken
In Datenbankmanagementsystemen (DBMS) gibt es im Wesentlichen zwei Arten von Hash-Verfahren:
- Statisches Hashing
- Dynamisches Hashing
Die beiden unterscheiden sich hauptsächlich darin, ob die Anzahl der Eimer festgelegt ist, wie in den nächsten beiden Abschnitten erläutert wird.
Statisches Hashing
Bei statischem Hashing bleibt die resultierende Daten-Bucket-Adresse immer gleich.
Wenn Sie also beispielsweise eine Adresse generieren, Studenten_ID = 10 unter Verwendung der Hash-Funktion mod(3), lautet die resultierende Bucket-Adresse immer 1Sie werden also keine Änderung an der Bucket-Adresse feststellen.
Daher bleibt bei der statischen Hash-Methode die Anzahl der Daten-Buckets im Speicher immer konstant.
Statische Hash-Funktionen
- Einfügen eines Datensatzes: Wenn ein neuer Datensatz in die Tabelle eingefügt werden soll, wird mithilfe seines Hash-Schlüssels eine Adresse dafür generiert. Sobald die Adresse generiert ist, wird der Datensatz an dieser Stelle gespeichert.
- Suchen: Wenn Sie den Datensatz abrufen müssen, wird dieselbe Hash-Funktion verwendet, um die Adresse des Buckets abzurufen, in dem die Daten gespeichert sind.
- Einen Datensatz löschen: Bei Verwendung der Hash-Funktion wird zuerst der zu löschende Datensatz abgerufen und anschließend von der entsprechenden Speicheradresse entfernt.
Statisches Hashing wird weiter unterteilt in:
- Offenes Hashing
- Geschlossenes Hashing
Öffnen Sie Hashing
Beim Open-Hashing-Verfahren wird der ältere Datensatz nicht überschrieben, sondern der nächste verfügbare Datenblock verwendet, um den neuen Datensatz zu erstellen. Dieses Verfahren ist auch als lineares Sondieren bekannt.
Beispielsweise ist A2 ein neuer Datensatz, den Sie einfügen möchten. Die Hash-Funktion generiert die Adresse 222, die jedoch bereits von einem anderen Wert belegt ist. Daher sucht das System den nächsten Daten-Bucket, 501, und weist ihm A2 zu.
Geschlossenes Hashing
Bei der Closed-Hashing-Methode wird, wenn die Buckets voll sind, ein neuer Bucket für denselben Hash zugewiesen und das Ergebnis an das vorherige angehängt.
Dynamisches Hashing
Dynamisches Hashing bietet einen Mechanismus, mit dem Datenblöcke dynamisch und bedarfsgesteuert hinzugefügt und entfernt werden können. Bei dieser Hash-Methode erzeugt die Hash-Funktion eine große Anzahl von Werten, und die Struktur passt sich der Datenmenge an. Dadurch eignet sie sich besonders für Tabellen, deren Größe nicht vorhersehbar ist, da statisches Hashing hier entweder Speicherplatz verschwenden oder zu einem Überlauf führen würde.
Unterschied zwischen geordneter Indizierung und Hashing
Nachfolgend die wichtigsten Unterschiede zwischen Indizierung und Hashing:
| Kenngrößen | Geordnete Indizierung | Hashing |
|---|---|---|
| Speicherung der Adresse | Die Adressen im Speicher werden nach einem Schlüsselwert, dem sogenannten Primärschlüssel, sortiert. | Adressen werden immer mithilfe einer Hash-Funktion für den Schlüsselwert generiert. |
| Leistung | Sie kann mit zunehmender Datenmenge abnehmen, da die Daten sortiert gespeichert werden und jede Einfügung, Löschung oder Aktualisierung die Reihenfolge ändert. | Die beste Performance wird durch das ständige Hinzufügen und Löschen von Daten erzielt. Bei einer sehr großen Datenbank wird die Pflege der Hash-Datei jedoch aufwändiger. |
| Verwenden für | Bevorzugt für den Bereichsabruf, bei dem Daten für einen bestimmten Bereich abgerufen werden. | Ideal zum Abrufen eines bestimmten Datensatzes anhand des Suchschlüssels, funktioniert aber nur dann gut, wenn die Hash-Funktion auf dem Suchschlüssel basiert. |
| Speicherverwaltung | Bei Lösch- und Aktualisierungsvorgängen entstehen viele ungenutzte Datenblöcke, die nicht zur Wiederverwendung freigegeben werden können, weshalb eine regelmäßige Wartung erforderlich ist. | Bei statischem und dynamischem Hashing wird der Speicher stets verwaltet und ein Bucket-Überlauf wird behandelt, um das statische Hashing zu erweitern. |
Kurz gesagt, wählen Sie die Reihenfolge. Indizierung für Bereichsabfragen und Hashing für exakte Übereinstimmungssuchen auf dem Schlüssel.
Was ist Kollision?
Eine Hash-Kollision ist ein Zustand, in dem die resultierenden Hashes von zwei oder mehr Elementen im Datensatz fälschlicherweise demselben Eintrag zugeordnet werden. Hash-tabelle.
Wie man mit einer Hash-Kollision umgeht
Es gibt zwei Techniken, mit denen Sie eine Hash-Kollision vermeiden können:
- Wiederholung: Bei dieser Methode wird eine sekundäre Hash-Funktion aufgerufen, die so lange angewendet wird, bis ein leerer Speicherplatz gefunden wird, in dem ein Datensatz platziert werden kann.
- Verkettung: Die Verkettungsmethode erstellt eine verkettete Liste von Elementen, deren Schlüssel denselben Hashwert ergeben. Diese Methode erfordert an jeder Tabellenposition ein zusätzliches Link-Feld.
