Hash-Speicherstruktur

Hash-Speicherstruktur
Hash-Speicherstruktur

Die Idee der Hash-Speicherstruktur besteht darin, die Schlüsselwerte eines Datensatzes mit Hilfe eines Algorithmus direkt in die physische Adresse umzurechnen und so eine sehr gute Performance beim Lesen zu erreichen. Dazu wird eine HASH-Funktion verwendet.

Vorgehensweise:

Einer Relation wird ein fester Speicherbereich B von n Blöcken mit den logischen Adressen 0, 1,..., n—1 zugeordnet. Der Schlüsselbereich S wird durch die HASH-Funktion direkt auf einen Block abgebildet. Eine einfache und gebräuchliche HASH-Funktion ist die mathematische Funktion MODULO n, das Teilen mit Rest. Einem Schlüssel wird ein ganzzahliger, benachbarter Wert zugeordnet und dieser Wert wird durch n dividiert. Je nach Restklasse wird er einem unterschiedlichen Block zugeschlagen. Als n nimmt man eine große (Prim)-Zahl.

Datenzugriffe beim HASH-Verfahren

LesenAus dem Schlüsselwert wird die Adresse des Satzes direkt ermittelt. Bei Überläufen muss die Kette linear abgearbeitet werden. Ohne Überlaufseiten kann auf jeden Datensatz in konstanter Zeit zugegriffen werden und damit ist dies dann die schnellste Zugriffsform.
SchreibenDie HASH-Funktion liefert die Adresse des zugeordneten Blocks. Falls nicht genügend Platz vorhanden ist, muss eine Überlaufseite angelegt werden.
LöschenDer betreffende Satz wird aus dem Block physisch eliminiert. Falls eine Überlaufseite leer wird, kann sie wieder freigegeben werden.
SpeichereffizienzHASH-Speicherstrukturen benötigen keine zusätzlichen Verwaltungsdaten. Der Primärbereich muss ausreichend groß angelegt werden, damit neue Daten Platz finden und die Überlaufseiten nicht ausarten. Bei veränderlichen Datenbeständen ist die Speichereffizienz niedrig.

Diese hier beschriebene Hash-Funktionalität transformiert die Werte einer Quellmenge in eine Zielmenge fixer Größe. Es sind aber auch Anwendungen denkbar, wo die Größe der Zielmenge unbekannt ist bzw. sich sehr häufig ändert. Dies ist z.B. der Fall, wenn mittels Hash-Funktion der Rechnerknoten bestimmt werden soll, auf dem ein Datensatz gespeichert werden soll und es sich um einen großen Rechnerverbund handelt, bei dem Ausfälle und Neuzugänge einkalkuliert und dynamisch ausgeglichen werden, wie es z.B. bei NoSQL-Systemen der Fall ist. Bei solchen Anwendungsfällen hilft das Consistent-Hashing weiter.

Quellen:

  • Elmasri, Ramez/Navathe, Shamkant B.: "Grundlagen von Datenbanksystemen" , Pearson Studium, München, 2002, ISBN 3-8273-7021-3
  • Faeskorn-Woyke, Heide/Bertelsmeier, Birgit/Riemer, Petra/Bauer, Elena: "Datenbanksysteme - Theorie und Praxis mit SQL2003, Oracle und MySQL", Pearson Education, München, 2007, ISBN 978-3-8273-7266-6
  • Kemper, Alfons/Eickler, André: "Datenbanksysteme", Oldenbourg, München, 2009, 978-3-486-59018-0
  • Saake, Gunter/Sattler, Kai-Uwe/Heuer, Andreas: "Datenbanken - Konzepte und Sprachen", mitp-Verlag, Redline GmbH, Heidelberg, 2007, ISBN 3-8266-1664-2
  • Vossen, Gottfried: "Datenmodelle, Datenbanksprachen und Datenbankmanagementsysteme", Oldenbourg, München, 2008, ISBN 978-3-486-27574-2

Kategorie. Speicherstrukturen, H