\documentclass{bschlangaul-aufgabe}
\bLadePakete{baum}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 5},
  Thematik = {Tupel-Identifikator und B-Baum},
  Referenz = 66114-2016-H.T2-A5,
  RelativerPfad = Examen/66114/2016/09/Thema-2/Aufgabe-5.tex,
  ZitatSchluessel = 66114:2016:09,
  BearbeitungsStand = unbekannt,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Physische Datenorganisation, Tupel-Identifikator, B-Baum},
  EinzelpruefungsNr = 66114,
  Jahr = 2016,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 5,
}

\begin{enumerate}

%%
% a)
%%

\item Erläutern Sie die wesentliche Eigenschaft eines
Tupel-Identifikators (TID) in ein bis zwei Sätzen.
\index{Physische Datenorganisation}
\index{Tupel-Identifikator}
\footcite{66114:2016:09}

\begin{bAntwort}
\begin{itemize}
\item Daten werden in Form von \emph{Sätzen} auf der Festplatte
abgelegt, um auf Sätze zugreifen zu können, verfügt jeder Satz über eine
\emph{eindeutige, unveränderliche Satzadresse}

\item TID = Tupel Identifier: dient zur Adressierung von Sätzen in einem
Segment und besteht aus zwei Komponenten:

\begin{itemize}
\item Seitennummer (Seiten bzw. Blöcke sind größere Speichereinheiten
auf der Platte)

\item Relative Indexposition innerhalb der Seite
\end{itemize}

\item Satzverschiebung innerhalb einer Seite bleibt ohne Auswirkungen
auf den TID. Wird ein Satz auf eine andere Seite migriert, wird eine
„Stellvertreter-TID“ zum Verweis auf den neuen Speicherort verwendet.
Die eigentliche TID-Adresse bleibt stabil.
\footcite[Seite 219]{kemper}
\end{itemize}
\end{bAntwort}

%%
% b)
%%

\item Fügen Sie in einen anfangs leeren B-Baum mit $k = 1$ (maximal 2
Schlüsselwerte pro Knoten) die im Folgenden gegebenen Schlüsselwerte der
Reihe nach ein. Zeichnen Sie den Endzustand des Baums nach jedem
Einfügevorgang. Falls Sie Zwischenschritte zeichnen, kennzeichnen Sie
die sieben Endzustände deutlich.
\index{B-Baum}

\begin{center}
3, 7, 13, 11, 9, 10, 8
\end{center}

\begin{bAntwort}
\begin{center}
\begin{tikzpicture}[
  b bbaum,
  level 1/.style={level distance=10mm,sibling distance=32mm},
  level 2/.style={level distance=10mm,sibling distance=20mm},
]
\node {9} [->]
  child {
    node {7}
    child {
      node {3}
    }
    child {
      node {8}
    }
  }
  child {
    node {11}
    child {
      node {10}
    }
    child {
      node {13}
    }
  };
\end{tikzpicture}
\end{center}
\end{bAntwort}

%%
% c)
%%

\item Gegeben ist der folgende B-Baum:

\begin{center}
\begin{tikzpicture}[
  b bbaum,
  level 1/.style={level distance=15mm,sibling distance=32mm},
  level 2/.style={level distance=15mm,sibling distance=15mm},
]
\node {6 \nodepart{two} 19} [->]
  child {
    node {3}
    child {
      node {0}
    }
    child {
      node {4 \nodepart{two} 5}
    }
  }
  child {
    node {13 \nodepart{two} 17}
    child {
      node {9}
    }
    child {
      node {14}
    }
    child {
      node {18}
    }
  }
  child {
    node {42}
    child {
      node {40}
    }
    child {
      node {43}
    }
  };
\end{tikzpicture}
\end{center}

Die folgenden Teilaufgaben sind voneinander unabhängig.

\begin{enumerate}

%%
% i)
%%

\item Löschen Sie aus dem gegebenen B-Baum den Schlüssel 3 und zeichnen
Sie den Endzustand des Baums nach dem Löschvorgang. Falls Sie
Zwischenschritte zeichnen, kennzeichnen Sie den Endzustand deutlich.

\begin{bAntwort}
\begin{center}
\begin{tikzpicture}[
  b bbaum,
  level 1/.style={level distance=15mm,sibling distance=32mm},
  level 2/.style={level distance=15mm,sibling distance=15mm},
]
\node {6 \nodepart{two} 19} [->]
  child {
    node {4}
    child {
      node {0}
    }
    child {
      node {5}
    }
  }
  child {
    node {13 \nodepart{two} 17}
    child {
      node {9}
    }
    child {
      node {14}
    }
    child {
      node {18}
    }
  }
  child {
    node {42}
    child {
      node {40}
    }
    child {
      node {43}
    }
  };
\end{tikzpicture}
\end{center}
\end{bAntwort}

%%
% ii)
%%

\item Löschen Sie aus dem (originalen) gegebenen B-Baum den Schlüssel 17
und zeichnen Sie den Endzustand des Baums nach dem Löschvorgang. Falls
Sie Zwischenschritte zeichnen, kennzeichnen Sie den Endzustand deutlich.

\begin{bAntwort}
\begin{center}
\begin{tikzpicture}[
  b bbaum,
  level 1/.style={level distance=15mm,sibling distance=32mm},
  level 2/.style={level distance=15mm,sibling distance=15mm},
]
\node {6 \nodepart{two} 19} [->]
  child {
    node {3}
    child {
      node {0}
    }
    child {
      node {4 \nodepart{two} 5}
    }
  }
  child {
    node {13}
    child {
      node {9}
    }
    child {
      node {14 \nodepart{two} 18}
    }
  }
  child {
    node {42}
    child {
      node {40}
    }
    child {
      node {43}
    }
  };
\end{tikzpicture}
\end{center}
\end{bAntwort}

%%
% iii)
%%

\item Löschen Sie aus dem (originalen) gegebenen B-Baum den Schlüssel 43
und zeichnen Sie den Endzustand des Baums nach dem Löschvorgang. Falls
Sie Zwischenschritte zeichnen, kennzeichnen Sie den Endzustand deutlich.

\begin{bAntwort}

\begin{center}
\begin{tikzpicture}[
  b bbaum,
  level 1/.style={level distance=15mm,sibling distance=32mm},
  level 2/.style={level distance=15mm,sibling distance=15mm},
]
\node {6 \nodepart{two} 17} [->]
  child {
    node {3}
    child {
      node {0}
    }
    child {
      node {4 \nodepart{two} 5}
    }
  }
  child {
    node {13}
    child {
      node {9}
    }
    child {
      node {14 \nodepart{two} 18}
    }
  }
  child {
    node {19}
    child {
      node {40}
    }
    child {
      node {42}
    }
  };
\end{tikzpicture}
\end{center}

\end{bAntwort}

\end{enumerate}

\end{enumerate}
\end{document}