2014-02-13 11:48:24 +01:00
|
|
|
\section{Sätze}
|
|
|
|
|
\subsection{Allgemein}
|
|
|
|
|
Warum wurden Sätze eingeführt? \\
|
2014-02-15 13:37:47 +01:00
|
|
|
Sätze abstrahieren von Blöcken. Blöcke sind Hardware spezifisch.
|
2014-02-13 11:48:24 +01:00
|
|
|
Sie haben unterschiedliche Längen und die Aufgabe von Einheiten von
|
|
|
|
|
Platte und HS zu transportieren. Daher hat man eine anwendungspezifische
|
|
|
|
|
Einheit eingeführt, die Daten zusammenfasst.\\
|
2014-02-13 13:43:22 +01:00
|
|
|
\subsection{Satzadresse}
|
|
|
|
|
Eine Satzadresse ist ein Bezeichner unter der man einen einzelnen Satz wiederfinden kann. Sie wird als stabil bezeichnet, wenn sich beim
|
|
|
|
|
verschieben des Satzes die Adresse nicht ändert.
|
2014-02-13 11:48:24 +01:00
|
|
|
$\rightarrow$ Neue Schicht über Blöcke
|
|
|
|
|
\subsection{Wechselpuffertechnik}
|
|
|
|
|
Optimierungsmöglichkeit bei sequenziellen Dateien.
|
|
|
|
|
Man verwendet \textit{zwei} Blockpuffer.\\
|
|
|
|
|
Anwendung beim
|
|
|
|
|
\begin{itemize}
|
|
|
|
|
\item Lesen: während Sätze in Puffer 1 gelesen werden \textbf{gleichzeitig} nächsten Block von Platte in Puffer 2 lesen
|
|
|
|
|
\item Schreiben: wenn Puffer 1 voll, \textbf{asynchron} auf Platte schreiben und gleichzeitig Puffer 2 zur Aufnahme weiterer Sätze verwenden
|
|
|
|
|
\end{itemize}
|
2014-02-13 13:43:22 +01:00
|
|
|
\subsection{Satzzugriff über Schlüsselwerte}
|
|
|
|
|
\subsection{Normales Hashing}
|
|
|
|
|
Man möchte nun Sätze und deren Inhalt nicht nur über
|
|
|
|
|
die Satzadresse wiederfinden, sondern auch über \textbf{inhaltliche Kriterien}.
|
|
|
|
|
\textbf{Schlüssel} definieren ein oder mehrere Felder eines Satzes, über
|
|
|
|
|
das man den Satz wiederfinden kann.
|
|
|
|
|
|
|
|
|
|
Lösung dafür ist \textbf{Hashing} der Sätze nach Schlüssel.
|
|
|
|
|
|
|
|
|
|
Kollisionen verhindern:
|
|
|
|
|
\begin{itemize}
|
|
|
|
|
\item Open Addressing (ausweichen auf Nachbar Buckets)
|
|
|
|
|
\begin{itemize}
|
|
|
|
|
\item $+$ kein zusätzlicher Speicherplatz erforderlich
|
|
|
|
|
\item $-$ beim Suchen findet man im Bucket auch Überläufer
|
|
|
|
|
\item $-$ beim löschen Überläufer zurückholen
|
|
|
|
|
\item $-$ in Nachbarbuckets werden ggf weitere Überläufe erzeugt
|
|
|
|
|
\end{itemize}
|
|
|
|
|
\item Overflow Buckets
|
|
|
|
|
\begin{itemize}
|
|
|
|
|
\item Anlegen spezieller Überlauf Buckets für jeden Bucket
|
|
|
|
|
\begin{itemize}
|
|
|
|
|
\item $-$ zusätzlicher Speicherplatz erforderlich
|
|
|
|
|
\item $+$ keine Mischung von sätzen
|
|
|
|
|
\item $+$ keine Beeinträchtigung der Nachbarbuckets
|
|
|
|
|
\end{itemize}
|
|
|
|
|
\end{itemize}
|
|
|
|
|
\end{itemize}
|
|
|
|
|
\subsubsection{Bewertung}
|
|
|
|
|
\begin{itemize}
|
|
|
|
|
\item sehr schneller Zugriff über Schlüssel (1 bis 2 Blockzugriffe)
|
|
|
|
|
\item gestreute Speicherung kann nur nach \textbf{einem} Schlüssel erfolgen
|
|
|
|
|
\item Speicherplatz muss um voraus belegt werden
|
|
|
|
|
\end{itemize}
|
|
|
|
|
\subsection{Virtuelles Hashing}
|
|
|
|
|
Vorteile vom virtuellen Hashing ggü. normalen Hashing:\\
|
|
|
|
|
Das normale Hashing ist nicht erweiterbar, d.h. man muss den gesamten
|
|
|
|
|
Speicher im voraus belegen. Dadurch kommt man in Platznot oder verschwendet zuviel.
|
|
|
|
|
Beim linearen Hashing versucht man durch kontinuierliche Reorganisation
|
|
|
|
|
Überlaufprobleme zu vermeiden.
|
|
|
|
|
|
|
|
|
|
Beschreibung von Dateizustand:
|
