Datenbanken Online Lexikon TH Köln, Campus Gummersbach
Aktuelle Änderungen - Suchen:

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