Lineares und erweiterbares/dynamisches Hashing

Term Paper , 1998 , 16 Pages

Computer Science - Theory

Stellen Sie sich vor, Sie könnten Daten blitzschnell finden, egal wie groß Ihre Datenbank wird! Dieses Buch enthüllt die Geheimnisse fortschrittlicher Hashing-Techniken, die genau das ermöglichen. Vergessen Sie langsame Zugriffszeiten und ineffiziente Speicherverwaltung. Hier erfahren Sie, wie Sie mit linearem und dynamischem Hashing Ihre Datenbankperformance revolutionieren können. Entdecken Sie, wie diese intelligenten Algorithmen den Speicherbedarf dynamisch anpassen, Überläufe elegant behandeln und gleichzeitig eine beeindruckende Zugriffsgeschwindigkeit gewährleisten. Tauchen Sie ein in die Welt des linearen Hashings nach Litwin, lernen Sie die Vorteile kontrollierter Splits kennen und analysieren Sie detailliert die Leistungsfähigkeit verschiedener Ansätze. Verstehen Sie, wie dynamisches Hashing mit binären Hashbäumen komplexe Datenstrukturen meistert und auch bei wachsenden Datenmengen einen effizienten Zugriff ermöglicht. Anhand von anschaulichen Beispielen und detaillierten Analysen werden die komplexen Zusammenhänge verständlich aufbereitet. Egal, ob Sie Datenbankentwickler, Systemarchitekt oder Student der Informatik sind, dieses Buch bietet Ihnen das Rüstzeug, um Ihre Datenverwaltung auf ein neues Level zu heben. Optimieren Sie Ihre Datenbanken mit dynamischen Hashverfahren und profitieren Sie von maximaler Performance und minimalem Speicherverbrauch. Lassen Sie sich von den flexiblen Anpassungsmöglichkeiten und der beeindruckenden Effizienz dieser Methoden überzeugen. Verbessern Sie nachhaltig die Performance Ihrer Datenbankanwendungen durch den Einsatz von Linear Hashing und Dynamic Hashing und sichern Sie sich einen Wettbewerbsvorteil durch schnellere Zugriffszeiten und eine optimale Speicherausnutzung. Erfahren Sie alles über Hashfunktionen, Kollisionsbehandlung und die Implementierung dynamischer Tabellen für eine moderne Datenverwaltung. Dieses Buch ist Ihr Schlüssel zu einer effizienten und zukunftssicheren Datenbankarchitektur.

Inhaltsverzeichnis

1. Einleitung
   1. Hashing - Ein Überblick
   2. Probleme und Lösungsmöglichkeiten
2. Lineares Hashing
   1. Basisschema
   2. Bestimmung der Adresse eines Datums
   3. Variante - “Kontrollierte Splits”
   4. Leistungsanalyse
3. Dynamisches und erweiterbares Hashing
   1. Vorgehensweise des dynamischen Hashing
   2. Leistungsdaten
   3. Variante zur besseren Speicherauslastung
4. Zusammenfassung

1 Einleitung

Das Ziel eines jeden Datenbankprogramms ist ein möglichst schneller und ef­fizienter Zugriff auf den Hintergrundspeicher. Zwei Adressierungstechniken für Datensätze, die ein schnelles Auffinden von Daten ermöglichen sind Bäume (B- Bäume, Binärbäume, ...) und Hashing.

Hashing besitzt den Vorteil, daß es einfach und schnell ist, sofern eine gleichmäßige Verteilung der Datensätze auf dem Speicher gegeben ist. Im folgen­den soll ein kurzer Überblick über das konventionelle Hashing und seine Probleme gegeben werden. Der Hauptteil der Arbeit konzentriert sich auf die Erläuterung erweiterter Hashverfahren, die sich bei dynamischen Datenbanken als notwendig erweisen.

1.1 Hashing - Ein Überblick

Grundlegende Datenstrukturen sind Datensätze, die von einem Schlüssel (engl, key) indiziert werden. Mit Hilfe des Hashings können solche Datensätze bei sta­tischen Dateien generell mit nur einem Zugriff gefunden werden.

Beim Anlegen einer Datenbank wird zunächst der Plattenspeicher in verschie­dene Behälter (engl, buckets), bzw. Seiten unterteilt. Die Grundidee des Hashings ist eine Verteilung der Datensätze auf diese Behälter, wobei die Position des Da­tensatzes mit Hilfe der sog. Hashfunktion ermittelt wird. Dazu wird der Schlüssel in die Funktion eingesetzt, und man erhält als Ergebnis die Nummer des Ziel­behälters. Die Hashfunktion ist also eine Abbildung h von der Menge der Schlüssel S in eine Indexmenge I = [0..N-1], wobei N die Anzahl der Behälter ist.

Abbildung in dieser Leseprobe nicht enthalten

Ein Datensatz kann nun durch die Hashfunktion sofort wieder aufgefunden wer­den, indem sein Schlüssel in die Funktion eingesetzt wird. Die Funktion liefert den Index des Behälters, in dem sich der gesuchte Datensatz befindet.

1.2 Probleme und Lösungsmöglichkeiten

Die Tiefe der Behälter bestimmt die maximale Zahl von Datensätzen, die sie aufnehmen können. Sollen nun in einen Behälter mehr Datensätze geschrieben werden, muß auf sog. Uberlaufstrategien oder Kollisionsbehandlungen zurückge­griffen werden. Eine zunehmende Anzahl von Überläufen hat jedoch eine schlech­tere Performance zur Folge, da sich die Datensätze nicht mehr im ursprünglich berechneten Behälter befinden. Spätestens wenn auch noch der Füllgrad zu hoch, d.h. der anfangs zugewiesene Plattenspeicher knapp wird, muß der Speicherplatz vergrößert und demzufolge die Datenbank reorganisiert werden. Dazu benötigt man eine neue Hashfunktion (engl, rehashing).

Dies ist eine sehr aufwendige und kostspielige Vorgehensweise. Eine andere Möglichkeit wäre, die Datei von Beginn an so groß zu wählen, daß eine Reorga­nisation voraussichtlich nicht notwendig wird. Folglich würde jedoch eine Menge Speicher verschwendet werden.

Aus diesem Grund wurden verschiedene Hashingtechniken entwickelt, die es ermöglichen die Hashfunktion dynamisch zu verändern, um den erforderlichen Speicherplatz bei Bedarf einer Vergrößerung bzw. einer Verkleinerung der Daten­bank anzupassen.

Zwei dieser Methoden gehen auf Witold Litwin [Lit] und Per-Äke Larson [Lar] zurück: “Linear Hashing” und “Dynamic Hashing”. In beiden ist das Einfügen, Löschen und Wiederauffinden von Daten beinahe genauso einfach wie im konven­tionellen Hashing. Während Litwin ein lineares Wachstum des benötigten Spei­chers erreicht, und sich die Daten direkt adressieren lassen, benötigt Larson zum Zugriff eine Indexstruktur. Zunächst soll Litwin’s Schema näher betrachtet wer­den.

2 Lineares Hashing

2.1 Basisschema

Ausgangspunkt sind Datensätze, die durch einen Schlüssel indiziert sind. Am Beispiel aus Tabelle 1 wird dies deutlich. Gespeichert werden sollen die Namen verschiedener Studenten. Der Schlüssel ist hier die Matrikelnummer.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Studenten

Nehmen wir vereinfachend an, daß der Speicher ursprünglich aus drei Behältern besteht, die jeweils zwei Datensätze aufnehmen können. Die Hash­funktion h soll nun den jeweiligen Schlüssel к nach folgender Formel umrechnen:

Abbildung in dieser Leseprobe nicht enthalten

h ergibt also den Index eines dieser drei Behälter. Abbildung 1 zeigt die Behälter, nachdem die ersten fünf Datensätze eingefügt wurden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Zustand nach fünf Einfügungen

Beim Einfügen des sechsten Datensatzes entsteht ein Überlauf im Behälter 0 (29529 mod 3 = 0). Beim konventionellen Hashing würde an dieser Stelle je nach Kollisionsbehandlung der Datensatz in einem anderen Behälter gespeichert, oder ein Uberlaufbehälter angehängt werden. Stattdessen wird beim linearen Hashing eine Spaltung (engl, split) des Behälters durchgeführt. Dies wird mit Hilfe einer neuen Funktion, einer sog. “split function’1 realisiert. Diese Funktionen sind all­gemein wie folgt definiert: h₀ : S → [0..N— 1] sei die ursprüngliche Hashfunktion. Die Funktionen h₁, h₂, ··, h_i, .. sind Splitfunktionen, wenn gilt:

Abbildung in dieser Leseprobe nicht enthalten

(1)

Abbildung in dieser Leseprobe nicht enthalten

(2)

Abbildung in dieser Leseprobe nicht enthalten

(3)

Die Splitfunktion bildet also nach (1) in einen doppelt so großen Bereich ab. Im vorliegenden Fall soll h_i : k→ k mod 2ⁱ N als Splitfunktion verwendet werden. Die Bedingungen aus (2) bzw. (3) für h₁sind erfüllt, da für nichtnegative Integer x entweder x mod 6 = x mod 3 oder x mod 6 = x mod 3 + 3 gilt.

Ziel ist es zunächst nur diejenigen Datensätze aus dem vom Überlauf betrof­fenen Behälter neu zu organisieren und die anderen beizubehalten, so daß nur wenige Datensätze verschoben werden müssen, und die Datenbank dynamisch verändert werden kann. Demnach definiert man die neue Hashfunktion h folgen­dermaßen:

Abbildung in dieser Leseprobe nicht enthalten

Im Klartext heißt das, daß nur dann hi verwendet wird, wenn die Umrech­nung des Schlüssels 0 ergibt. Es muß also ein neuer Behälter (Nummer 3) angefügt
werden, und die Datensätze aus Behälter 0 werden mit Hilfe von h zufällig auf diese beiden verteilt. Abbildung 2 zeigt die Situation nach diesem Split und dem Einfügen des sechsten Datensatzes. Man kann immer noch die Position eines Da­tums direkt bestimmen, indem man den entsprechenden Schlüssel in die Funktion h einsetzt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Zustand nach dem ersten Split

Da die Kollisionen zufällig auftreten, führt das Spalten des Behälters, in dem der Überlauf stattfindet, jedoch zu komplizierten Funktionen, weil festgehalten werden muß, welche Behälter schon von einer Spaltung betroffen waren. Die Idee beim linearen Hashing ist, daß Splits in linear aufsteigender Reihenfolge durch­geführt, und weiterhin Uberlaufbehälter verwendet werden. Nach Eintragung der nächsten beiden Datensätze in unserem Beispiel tritt eine Kollision in Behälter 2 auf, was nach dem bisherigen System einen Split dieses Behälters zur Folge hätte. Im linearen Hashing kommt jetzt ein Zeiger n hinzu, der zunächst auf den ersten Behälter zeigt und bei jedem Split um 1 erhöht wird.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Zustand nach acht Einfügungen

Es wird dann bei einer Kollision nicht der Behälter getrennt, in dem der Überlauf stattfindet, sondern der, auf den n zeigt. Im aktuellen Fall heißt das, daß zuerst Nummer 1 gespalten wird und für den zweiten eine Kollisionsbehand-
lung durchgeführt, z.В. ein Uberlaufbehälter angefügt wird. Das Ergebnis zeigt Abbildung 3.

Während der ersten N Kollisionen bewegt sich demnach der Zeiger n von 0 bis V — 1, und der jeweilige Behälter wird getrennt, wobei immer die Funktion hi Verwendung findet. Der tatsächlich übergelaufene Behälter wird erst dann einem Split unterzogen, wenn der Zeiger ihn erreicht hat, also in der Regel mit einiger Verspätung. Ist dies der Fall, so wird der gebildete Überlauf meist wieder aufgelöst, sofern die Hashfunktion gut gewählt ist.

In Abbildung 4 stellt sich das Endergebnis dar. Beim Schreiben des vorletzten Datensatzes entstand eine Kollision im Behälter 3, worauf Behälter 2 gespalten wurde. Der Datensatz selbst wurde wieder in einem Uberlaufbehälter abgelegt, der an den Behälter 3 angefügt wurde.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Endergebnis

Nach N Kollisionen ist also h = h_i und es existieren nach (1) genau 2N Behälter. Der Zeiger beginnt nun wieder bei 0 und bewegt sich bis 2₁ N — 1 usw.

2.2 Bestimmung der Adresse eines Datums

Überraschenderweise kann man die Position eines Datensatzes bestimmen, ohne den Wert des Zeigers n zu kennen. Der folgende Algorithmus beweist dies:

Abbildung in dieser Leseprobe nicht enthalten

m ist hier die Adresse des Datums mit dem Schlüssel к, und В ist die Anzahl der primären Behälter. Für den Fall n = 0 ist der Algorithmus richtig, da dann die Hashfunktion für alle Datensätze mit der Splitfunktion übereinstimmt. Ist n ≠ 0,

so gilt:

Abbildung in dieser Leseprobe nicht enthalten

Im ersten Fall gibt die Bedingung an, daß für den Datensatz schon die neue Funk­tion hj gilt, d.h. der Zeiger hat den entsprechenden Behälter schon passiert. Also h(k) < n. Für diesen Fall ist der Algorithmus demnach korrekt. Im nächsten ist es etwas komplizierter. Sind hj(k) und hj-i(k) gleich, so heißt das, daß hj (к) im Bildbereich von hj-1 liegen muß (siehe auch (1) und (2) in 2.1). Anderenfalls ist hj{k) ф hj-i{k) = h(k), d.h hj(k) > B, da der Behälter h(k) noch nicht getrennt wurde. Der Algorithmus für die Bestimmung der Adresse arbeitet demnach kor­rekt.

2.3 Variante - “Kontrollierte Splits”

Eine Abwandlung des Grundschemas ist das lineare Hashing mit einer Kontrolle des Füllgrads (engl, load factor), um eine bessere Speicherauslastung zu erhalten (siehe auch Abschnitt 2.4). Der Füllgrad f ist das Verhältnis zwischen belegtem und zugewiesenem Plattenspeicher. Die Spaltung von Behältern soll nicht nur dann erfolgen wenn ein Überlauf stattfindet, sondern erst, wenn der Füllgrad zusätzlich einen bestimmten Wert erreicht hat.

Analog können zwei Behälter wieder zusammengruppiert werden, sobald f die vorgegebene Schranke unterschreitet. Folglich muß der Zeiger n dann um 1 verringert werden. Mit Hilfe dieser sog. “load control” erreicht man, daß der Füllgrad einer Datei annähernd konstant bleibt.

2.4 Leistungsanalyse

In diesem Abschnitt soll ein Überblick über die Leistungsdaten des linearen Ha­shings gegeben werden. Eine genauere Analyse ist in [Lit] zu finden.

Zwei Komponenten sind wichtig bei der Betrachtung der Performance: die Zu­griffsgeschwindigkeit auf die Daten und die Speicherauslastung, d.h. der Füllgrad einer erzeugten Datei. Beim Basisschema kann die Adresse eines Datensatzes wie oben beschrieben (2.1) grundsätzlich ohne einen Zugriff auf den physikalischen Speicher bestimmt werden. Die Kollisionsbehandlung, die im folgenden zugrun­degelegt wird ist wie bisher die separate Anhängung von Uberlaufbehältern an die primären Behälter, d.h. falls ein Behälter überläuft, wird ein neuer angehängt in dem der Datensatz abgelegt wird.

a) Unkontrollierte Spaltung

Die Leistungswerte des Algorithmus bestimmt man mit Hilfe von Simulationen. Den Ergebnissen, die in Tabelle 2 dargestellt sind, liegen Simulationen mit Da­tenbanken zugrunde, bei denen nach und nach mehr als 213 Datensätze eingefügt wurden. Dabei bezeichnet b die Kapazität der Behälter, d.h. die Anzahl der Da­tensätze, die ein Behälter aufnehmen kann. Nach einigen Einfügungen stellt sich ein stabiler Zustand ein, in dem die zugehörigen Kurven periodisch verlaufen. In der Tabelle sind jeweils nur die Durchschnittswerte der benötigten Zugriffe s auf die Datei, bzw. des Füllgrads f angegeben.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Performance mit unkontrollierten Splits: s1 : erfolgreiche Suche s2 : erfolglose Suche s3 : Einfügung s4 : Spaltung / : Füllgrad

Man sieht, daß die Zahl der Zugriffe auf den Speicher bei einer erfolgreichen Suche annähernd konstant bei 1 liegt. B-Bäume benötigen hier durchschnittlich ca. 2.5 Zugriffe. Lineares Hashing erreicht also in diesem Fall die Performance des klassischen Hashing, während es bei einer erfolglosen Suche mit etwas mehr als einem Zugriff geringfügig schlechter abschneidet. Die benötigten Zugriffe beim Einfügen eines Datensatzes, bzw. bei der Spaltung von Behältern liegen natürlich wesentlich höher.

Der Füllgrad bei größeren Werten von b liegt bei fast 60% und ist damit nahezu 10% schlechter als bei den B-Bäumen. Es wird jedoch oft mehr Wert auf einen schnelleren Zugriff, als auf die Auslastung des immer billiger werdenden Plattenspeichers gelegt. Für einen besseren Füllgrad ist die Spaltung mittels “load control” zuständig, die im nächsten Abschnitt analysiert wird.

b) Kontrollierte Spaltung

Wird der Füllgrad der Datenbank kontrolliert und eine Spaltung, bzw. Grup­pierung nur beim Erreichen dieser Grenze durchgeführt (siehe 2.3) bleibt die

Auslastung fast konstant bei der vorgegebenen Schranke. Natürlich muß die Per­formance bei einer Erhöhung dieser Grenze schlechter werden, da die Anzahl der Uberlaufbehälter zunimmt. Simulationen zeigen, daß eine Verbesserung der Aus­lastung erreicht werden kann, und die Zugriffszahl doch noch sehr gut bleibt. In Tabelle 3 ist die durchschnittliche Performance bei verschiedenen Werten für f und Behältergrößen aufgelistet. bu bezeichnet in dieser Tabelle die Größe der Uberlaufbehälter. Sie wurde so gewählt, daß sich die beste Performance ergibt. Je größer die Primärbehälter sind, desto größer sollten auch die Uberlaufbehälter sein.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3: Performance mit kontrollierten Splits: s1 : erfolgreiche Suche s2 : erfolglose Suche s3 : Einfügung s4 : Spaltung

Man erkennt, daß die durchschnittliche Anzahl der Zugriffe auf den Platten­speicher für eine erfolgreiche Suche trotz einer signifikanten Verbesserung des Füllgrades immer noch nahe bei 1 liegt. Demnach läßt sich mit dem linearen Ha­shing ein viel schnellerer Zugriff auf Daten ermöglichen als bei B-Bäumen, und es kann zusätzlich auch noch mehr als 20% Speicher gespart werden.

3 Dynamisches und erweiterbares Hashing

Neben dem oben vorgestellten linearen Hashing gibt es noch weitere Techniken, die eine dynamische Anpassung des Sekundärspeichers an die Datenbankgröße ermöglichen. Dazu zählen das erweiterbare Hashing (extendible hashing) von Fa- gin [Fag] und das dynamische Hashing (dynamic hashing) nach Larson [Lar], Wie auch beim linearen Hashing werden Behälter bei einem Überlauf getrennt, doch verwenden beide Techniken eine Indexstruktur zur Adressierung der Daten. Die Position des Behälters wird bestimmt, indem man den Index nach dem jeweiligen Schlüssel durchsucht.

Der Index beim erweiterbaren Hashing verwendet ein sog. “buddy system”. Er hat 2d Einträge, von denen jeder auf den Behälter zeigt, in dem der Datensatz ge­speichert ist. Das Ergebnis der Hashfunktion muß nun eine Binärzahl sein, wobei nur die ersten d Bits des Ergebnisses verwendet werden, um die Adresse festzu­legen. Läuft ein Behälter über, so wird er getrennt, wobei nun das nächste Bit relevant wird, d entspricht also der Tiefe der Struktur. Werden nun Datensätze gelöscht und die Anzahl der Datensätze in zwei benachbarten Behältern (bud­dies) so gering, daß sie in einem Platz finden, so können diese beiden wieder verschmolzen werden.

Ähnlich ist die Vorgehens weise beim dynamischen Hashing, das nun genauer betrachtet werden soll. Der Unterschied besteht darin, daß der Index anders als beim erweiterbaren Hashing aus einer Baumstruktur besteht, was das Wachsen und Schrumpfen erleichtert.

3.1 Vorgehensweise des dynamischen Hashing

Wie schon oben angedeutet, verwendet das dynamische Hashing als Index für die Datei, in der die Daten gespeichert sind, Bäume, genauer gesagt einen Wald aus sog. binären Hashbäumen. Zur Erläuterung soll wieder das Beispiel aus Tabelle 1 herangezogen werden. Begonnen wird ähnlich wie beim klassischen Hashing: für die ersten Behälter wird Sekundärspeicher initialisiert. Beginnen wir beispiels­weise mit zwei Behältern mit einer Kapazität von jeweils zwei Datensätzen. Im Index werden dafür zwei Einträge initialisiert, wovon jeder einen Zeiger auf einen Behälter in der Datei enthält.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Initialisierung

In Abbildung 5 sieht man die Ausgangssituation dargestellt. Zusätzlich braucht man wieder eine Hashfunktion ho für die Verteilung der Daten. Der Unterschied zum linearen Hashing besteht darin, daß die Funktion ho nur dazu dient einen Einstiegspunkt in den Index, d.h. den richtigen Baum im Wald zu finden. Die Position des Behälters selbst wird durch den Zeiger im jeweiligen In­dexeintrag bestimmt. Es können nun also die Datensätze eingefügt werden. Mit Verwendung der Hashfunktion

h_o(k) = к mod 2

ergibt sich für die ersten vier Daten das in Abbildung 6 dargestellte Ergebnis.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6: Zustand nach fünf Einfügungen

Früher oder später kommt es auch hier zu einem Überlauf. Passiert dies, wird der betroffene Behälter gespalten und der Index aktualisiert, d.h. aus dem betroffenen Blatt wird ein innerer Knoten, an dem sich nun wiederum zwei Blätter befinden. Die Verteilung der Datensätze auf die beiden benachbarten Behälter wird durch eine zweite Hashfunktion h\ realisiert. Damit bei einer Suche nach dem Datensatz nicht (schlechtestenfalls) ein gesamter Baum durchsucht werden muß, muß der Weg durch den Baum eindeutig bestimmt sein. Dies erreicht man, indem man h\ so wählt, daß die Funktion von der Menge der Schlüssel in die Menge der Binärzahlen abbildet:

Abbildung in dieser Leseprobe nicht enthalten

Dabei genügt es in der Praxis d bis höchstens 32 zu wählen, da 2³² über 4 Milli­arden ergibt, was für die meisten Datenbanken mehr als ausreichend ist [Sil].

Die Funktion h₁ muß ein Pseudo-Zufallsgenerator sein, d.h bei einem Aufruf mit demselben Argument auch wieder das gleiche Ergebnis liefern. Dies bestimmt nun eindeutig, ob ein Datensatz bei einer Spaltung im linken (b_i = 0) oder im rechten (b_i = 1) Behälter untergebracht werden soll.

Für das vorliegende Beispiel soll die Funktion h₁ die umgekehrte binäre Dar­stellung der Quersumme der Matrikelnummer ausgeben. Am Beispiel Wolf: 3 + 1 + 9 + 2 + 8 = 23. Binärdarstellung von 23: 10111. Demnach hi(31928) = 11101. Tabelle 4 zeigt zur Veranschaulichung die Ergebnisse dieser Berechnung. In der Praxis gibt es bessere Alternativen für h_i z.B. durch eine Kopplung mit dem schon oben angewandten Divisionsrestverfahren, doch zu Demonstrationszwecken ist die Wahl gut genug.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 4: Ergebnisse von h\

Nachdem man die ersten vier Datensätze eingefügt hat, sind beide Behälter voll besetzt. Beim Versuch den nächsten unterzubringen muß also, wie in Bild 7 dargestellt, ein Split durchgeführt werden. Das erste Bit des Ergebnisses von h\ bestimmt dabei, wohin geschrieben werden soll. Im vorliegenden Fall also die beiden alten Datensätze nach links, der neue nach rechts.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 7: Zustand nach dem ersten Split

Es ist nun klar, wie weiter verfahren wird. Das nächste Datum muß wegen h0(k) wieder in den rechten Baum, und dort aufgrund des ersten Bits in den rech­ten Behälter. Schon bei der darauffolgenden Einfügung muß wieder eine Spaltung vollzogen werden (Bild 8), worauf nun die ersten beiden Bits der Daten im rechten Baum relevant werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 8: Zustand nach dem zweiten Split

Der nächste Satz verursacht nun auch eine Spaltung im linken Baum, so daß man schließlich ein Endergebnis erhält, wie es in Abbildung 9 dargestellt ist.

Es ist möglich, daß die Einfügung eines Datums mehr als nur eine Spaltung benötigt, nämlich dann, wenn jeweils alle Datensätze in den linken, bzw. in den rechten Behälter gehen. Die Wahrscheinlichkeit für ein solches Auftreten liegt jedoch bei einer gut gewählten Hashfunktion und Behälterkapazitäten von 10 Datensätzen bei etwa einem von tausend Splits [Lar], Die weitere Analyse der Leistungsfähigkeit des dynamischen Hashings soll im nächsten Abschnitt erfolgen.

3.2 Leistungsdaten

Anders als beim linearen Hashing ist die Zahl der Zugriffe auf den Sekundärspei­cher beim dynamischen Hashing konstant, da ja die Adresse des betroffenen Behälters direkt aus der Indexstruktur bestimmt wird, von der angenommen wird, daß sie sich komplett im Hauptspeicher befindet. Diese Annahme läßt sich bei größeren Datenbanken mit demzufolge größerem Index nicht immer aufrecht­erhalten, was der Hauptnachteil beim dynamischen Hashing ist. Die Anzahl der Zugriffe beim Einfügen in einen leeren Behälter, bzw. Löschen eines Datums liegt im “normalen” Fall bei 1 falls kein Split durchgeführt wird, und bei 3 (Auslesen alter Behälter, Schreiben der zwei neuen) falls ein Split auftritt.

Es ist demnach interessanter die Speicherauslastung des Algorithmus zu ana­lysieren. Dazu wird zunächst der Index betrachtet. Die Auslastung des Platten-

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 9: Endergebnis

Speichers kann man dann daraus ableiten. Für eine ausführliche Betrachtung sei wiederum auf [Lar] verwiesen.

Die Indexstruktur ist wie schon oben erwähnt ein Wald aus binären Hash- bäumen. Die Ähnlichkeit zu einem Binärbaum besteht darin, daß jeder Knoten entweder zwei Nachfolger hat (falls ein Split durchgeführt wurde), oder über­haupt keinen (falls er noch nicht übergelaufen ist). Für die Berechnung werden die Hashbäume nun zu kompletten unendlichen Binärbäumen ergänzt. Die hinzu­gefügten Knoten werden einfach als inaktiv angesehen. Es läßt sich daraufhin die Wahrscheinlichkeit berechnen, daß ein Datum durch einen bestimmten Knoten nach unten “rutscht”. Daraus kann man Formeln ableiten, die die Anzahl der benötigten aktiven Knoten für eine festgelegte Anzahl von einzufügenden Daten ausgeben. Diese sollen hier nicht direkt angegeben werden, sondern das Ergebnis an einem Beispiel verdeutlicht werden.

Gewählt wird eine Datei mit 4000 Datensätzen, 100 anfängliche Einträge im Index, d.h 100 Bäume, sowie eine Behälterkapazität von 10 Daten. Für diese Konstellation werden mindestens 400 Behälter benötigt. Die Berechnung ergibt eine erwartete Anzahl von 575.5, da die Datensätze zufällig verteilt sind, und nicht jeder Behälter voll sein wird, d.h. einige Daten sind weiter “nach unten gerutscht”, als bei einer optimalen Verteilung notwendig. Dies ergibt eine voraus­sichtliche Sekundärspeicherauslastung von 69,5%. Tabelle 5 zeigt, daß sich dieser Wert auch bewahrheitet, wenn man die Anzahl der Einfügungen bei verschiede­nen Behälterkapazitäten b gegen unendlich gehen läßt (siehe [Lar]).

Der Füllgrad liegt bei geringeren Behältergrößen etwas höher, da die Wahr­scheinlichkeit steigt, daß ein Behälter voll gefüllt ist, je weniger Datensätze er aufnehmen kann.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 5: Plattenspeiclierauslastung bei verschiedenen Behälterkapazitäten

3.3 Variante zur besseren Speicherauslastung

Analog der “load control” beim linearen Hashing kann man auch beim dynami­schen Hashing eine Verbesserung des Füllgrads erreichen. Dazu trennt man einen Behälter erst dann, wenn sein “buddy”, d.h. der benachbarte Behälter am selben Vorgänger auch voll ist. Dazu muß man die überzähligen Datensätze zunächst in dem benachbarten unterbringen, was wesentlich kompliziertere Algorithmen zum Lesen und Schreiben zur Folge hat. Die erwarteten Ergebnisse sind wie in Tabelle 6 dargestellt jedoch nicht deutlich besser.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 6: Vergleich der Füllgrade /1 : Verzögerte Splits f2 : normales Verfahren

4 Zusammenfassung

Mit den verschiedenen dynamischen Hashverfahren gibt es leistungsfähige Metho­den zur Adressierung von Datenbanken, die häufigen Größenänderungen unter­liegen. Tatsächlich gibt es kaum einen Grund das konventionelle Hashing weiter zu verwenden, außer wenn es sich um absolut statische Dateien handelt, da die Performance z.B. des linearen und des dynamischen Hashing weitestgehend ver­gleichbar ist, und die zugrundeliegenden Algorithmen für Lese-, Schreib- und Löschvorgänge nur wenig komplizierter sind.

Literatur

[Lar] Per-Ake LARSON - Dynamic Hashing. Bit 18(2): 184-201 (1978)

[Lit] WlTOLD Litwin - Linear Hashing: A New Tool for File and Table Addres­sing. VLDB 1980: 212-220

[Fag] R. Fagin, J. Nievergelt, N. Pippenger, H.R. Strong - Extendible Hashing - A fast access method for dynamic hies. ACM Transactions on Database Systems, 4(3): 315-344 (1979)

[Ram] K. Ramamohanarao/John W. LLOYD - Dynamic Hashing Schemes. The Computer Journal 25(4): 478-585 (1982)

[Sch] MICHEL Scholl - New File Organizations Based on Dynamic Hashing. ACM Transactions on Database Systems, 6(1): 194-211 (1981)

Häufig gestellte Fragen

Was ist das Ziel dieser Arbeit über Hashing?

Das Ziel ist ein schneller und effizienter Zugriff auf den Hintergrundspeicher in Datenbankprogrammen. Die Arbeit gibt einen Überblick über konventionelles Hashing und konzentriert sich auf erweiterte Hashverfahren für dynamische Datenbanken.

Was sind die grundlegenden Datenstrukturen beim Hashing?

Datensätze, die von einem Schlüssel indiziert werden. Hashing ermöglicht das schnelle Auffinden von Daten, im Idealfall mit nur einem Zugriff.

Wie funktioniert konventionelles Hashing?

Der Plattenspeicher wird in Behälter (Buckets) unterteilt. Die Hashfunktion verteilt die Datensätze auf diese Behälter, indem sie den Schlüssel des Datensatzes in eine Indexnummer des Zielbehälters umwandelt.

Welche Probleme können beim konventionellen Hashing auftreten?

Kollisionen, bei denen mehrere Datensätze in denselben Behälter geschrieben werden müssen, führen zu Überläufen und verringern die Performance. Wenn der Füllgrad zu hoch wird, ist eine Reorganisation der Datenbank mit einer neuen Hashfunktion erforderlich.

Was sind die Vorteile von dynamischem und erweiterbarem Hashing?

Diese Techniken ermöglichen es, die Hashfunktion dynamisch zu verändern, um den Speicherplatz bei Bedarf anzupassen. Sie vermeiden aufwendige Reorganisationen.

Was ist Lineares Hashing und wie funktioniert es?

Lineares Hashing ist eine Technik, die ein lineares Wachstum des benötigten Speichers erreicht. Bei einem Überlauf wird nicht der betroffene Behälter gespalten, sondern ein Behälter in linear aufsteigender Reihenfolge (mit Hilfe eines Zeigers). Eine Splitfunktion wird verwendet, um die Daten neu zu verteilen.

Wie bestimmt man die Adresse eines Datums beim Linearen Hashing?

Die Adresse kann ohne Kenntnis des Zeigers n bestimmt werden, indem man den entsprechenden Algorithmus anwendet, der zwischen der ursprünglichen Hashfunktion und einer Splitfunktion unterscheidet, je nachdem, ob der Zeiger den entsprechenden Behälter schon passiert hat.

Was ist "Kontrollierte Splits" beim Linearen Hashing?

Eine Variante, bei der die Spaltung von Behältern nicht nur bei einem Überlauf erfolgt, sondern erst, wenn der Füllgrad (load factor) einen bestimmten Wert erreicht hat. Dies dient zu einer besseren Speicherauslastung.

Wie ist die Performance des Linearen Hashings?

Die Zugriffsgeschwindigkeit bei einer erfolgreichen Suche liegt in der Regel nahe bei 1. Die Speicherauslastung (Füllgrad) kann durch kontrollierte Splits verbessert werden.

Was ist Dynamisches Hashing und wie funktioniert es?

Dynamisches Hashing verwendet eine Indexstruktur in Form eines Waldes aus binären Hashbäumen zur Adressierung der Daten. Bei einem Überlauf wird der betroffene Behälter gespalten und der Index aktualisiert.

Wie wird beim Dynamischen Hashing die Position des Behälters bestimmt?

Die Position wird durch den Zeiger im jeweiligen Indexeintrag bestimmt. Eine

• College: University of Passau
• Course: Proseminar "Datenstrukturen und Algorithmen für Datenbanken" an der Fakultät für Mathematik und Informatik
• Author: Andreas Gärtner (Author)
• Publication Year: 1998
• Pages: 16
• Catalog Number: V96296
• ISBN (eBook): 9783638089722
• Language: German
• Tags: Lineares, Hashing, Proseminar, Datenstrukturen, Algorithmen, Datenbanken, Fakultät, Mathematik, Informatik