7. 1 Interne Ebene: Hashorganisation (eindimensional, statisch)

• exakte Definition, Varianten, usw. s. Vorlesung Informatik A
• Prinzip: Hashfunktion, bildet Menge der Primärschlüsselwerte ab auf Menge von Bucketadressen (1 Bucket = 1 oder mehrere Seiten, i.F. 1 Seite)
• Implementierung:

  

Hashorganisation (eindimensional, statisch) Operationen:

• Lookup: 'w Primärschlüsselwert, finde Satz mit diesem Wert'
  Hashwert von w berechnen, zugeordneten Zeiger im Hashverzeichnis holen, über Zeiger erste Seite holen, Sätze auf Seite durchsuchen, falls nicht gefunden Nachfolgeseite holen und durchsuchen,..., falls keine Nachfolgeseite da: Satz nicht gefunden.
• Modifizieren: falls modifizierte Attribute Teil des Primärschlüssels: unveränderten Satz löschen, modifizierten Satz neu einfügen;
  falls nicht: Lookup ausführen, falls Satz gefunden: Attributwerte ändern
• Einfügen: Lookup durchführen,
  falls Satz gefunden: Fehler, da Primärschlüsselwert schon vorhanden,
  falls Satz nicht gefunden: Hashwert von w berechnen, Zeiger holen, in (Überlauf-)Seiten bis zum letzten Satz suchen, Satz dahinter eintragen
• Löschen: Lookup durchführen,
  falls Satz gefunden: Bit im Belegungsvektor auf 0 setzen (Vorsicht bei pinned records)

Zeitkomplexität:
wenn Hashverzeichnis nicht im HS: jede Operation benötigt einen Seitenzugriff für relevanten Teil des Hashverzeichnisses;
für Lookup: maximal 1 + Anzahl Überlaufseiten Seitenzugriffe

Hashorganisation (eindimensional, statisch) Probleme:

• Anpassung der Hashfunktion an wachsende oder schrumpfende Datenmengen, wenn max verändert wird: komplette Reorganisation notwendig (alle Datensätze neu hashen)
• Leistungsfähigkeit abhängig von Wahl der Hashfunktion, bei schlechter Wahl evtl. fast alle Sätze auf gleicher Seite (+Überlaufseiten)
• Bestimmte Anfragen umständlich zu beantworten, z.B.
  'Gib alle Sätze sortiert aus' oder
  'Gib alle Milch-Artikel aus' (Primärschl. ist Artnr; Bereichsanfrage)