1 Einleitung
Das Ziel eines jeden Datenbankprogramms ist ein möglichst schneller und effizienter 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 folgenden 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 statischen Dateien generell mit nur einem Zugriff gefunden werden.
Beim Anlegen einer Datenbank wird zunächst der Plattenspeicher in verschiedene 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 Datensatzes 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 Zielbehä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 werden, 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ückgegriffen werden. Eine zunehmende Anzahl von Überläufen hat jedoch eine schlechtere 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 Reorganisation 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 Datenbank 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 konventionellen Hashing. Während Litwin ein lineares Wachstum des benötigten Speichers erreicht, und sich die Daten direkt adressieren lassen, benötigt Larson zum Zugriff eine Indexstruktur. Zunächst soll Litwin’s Schema näher betrachtet werden.