2

B-Bäume

• B-Bäume sind eine Art von balanciertem Suchbaum.

Balancierte Suchbäume

• Balancierte Suchbäume garantieren eine Suchzeit von $O(\log n)$.
• Beispiele hierfür sind AVL-Bäume, 2-3-Bäume, 2-3-4-Bäume und B-Bäume.
• Das Grundprinzip ist, den Grad des Suchbaums zu erhöhen, um die Höhe zu verringern.

B-Bäume des minimalen Grades t

• Jeder Knoten hat höchstens $2t-1$ Schlüssel.
• Jeder Knoten außer der Wurzel hat mindestens $t-1$ Schlüssel.
• Ein Knoten hat $c$ Kinder, wenn er $c-1$ Schlüssel enthält.
• Alle Blätter haben die gleiche Tiefe.
• Knoten enthalten Schlüssel $key_1, key_2, \dots key_n$, wobei $key_1 \le key_2 \le \dots \le key_n$ gilt.

Suchen in B-Bäumen

• Die Suche in B-Bäumen ähnelt der Suche in binären Suchbäumen.
• Es wird das Intervall bestimmt, das den Suchschlüssel $k$ enthält.
• Danach wird dem entsprechenden Kinder-Zeiger gefolgt.

Einfügen in B-Bäume

• Der Pseudocode beschreibt, wie ein neuer Schlüssel $(k)$ in einen B-Baum eingefügt wird.
  • Wenn der zugehörige Knoten nicht voll ist, wird der Schlüssel eingefügt.
  • Wenn der zugehörige Knoten voll ist, wird er aufgeteilt.

Löschen aus B-Bäumen

• Das Löschen aus B-Bäumen ist komplizierter als das Einfügen.
• Das Löschen kann die B-Baum-Eigenschaften verletzen, insbesondere den Mindestgrad.
• Die Grundidee ist, sicherzustellen, dass ein Knoten nach dem Löschen eines Schlüssels die erforderliche Mindestanzahl an Schlüsseln behält.

Beispiel für einen B-Baum Löschvorgang

• Der Pseudocode beschreibt den Löschvorgang eines Knotens $k$ aus einem B-Baum
  • Wenn sich ein Schlüssel $k$ in einem Knoten $x$ befindet und $x$ ein Blatt ist, lösche einfach $k$ aus $x$.
  • Wenn sich ein Schlüssel $k$ in einem Knoten $x$ befindet und $x$ ein interner Knoten ist:
    • Wenn das Kind $y$, das $k$ in Knoten $x$ vorausgeht, mindestens $t$ Schlüssel hat, finde den Vorgänger $k'$ im Teilbaum mit der Wurzel $y$. Lösche $k'$ rekursiv und ersetze $k$ durch $k'$ in $x$.
    • Wenn $y$ weniger als $t$ Schlüssel hat, untersuche das Kind $z$, das $k$ in Knoten $x$ folgt. Wenn $z$ mindestens $t$ Schlüssel hat, finde den Nachfolger $k'$ im Teilbaum mit der Wurzel $z$. Lösche $k'$ rekursiv und ersetze $k$ durch $k'$ in $x$.
    • Andernfalls, wenn sowohl $y$ als auch $z$ nur $t-1$ Schlüssel haben, verschmelze $k$ und alle $z$ in $y$, so dass $x$ sowohl $k$ als auch den Zeiger auf $z$ verliert und $y$ nun $2t-1$ Schlüssel enthält. Gib $z$ frei und lösche $k$ rekursiv aus $y$.
  • Wenn der Schlüssel $k$ nicht im internen Knoten $x$ vorhanden ist, bestimme die Wurzel $c_i[x]$ des entsprechenden Teilbaums, der $k$ enthalten muss, falls $k$ überhaupt im Baum vorhanden ist. Wenn $c_i[x]$ nur $t-1$ Schlüssel hat, führe die Schritte 4a oder 4b aus, um sicherzustellen, dass wir zu einem Knoten absteigen, der mindestens $t$ Schlüssel enthält. Fahre dann fort, indem du rekursiv auf dem entsprechenden Kind von $x$ läufst.
    • Wenn $c_i[x]$ nur $t-1$ Schlüssel hat, aber ein unmittelbares Geschwisterkind mit mindestens $t$ Schlüsseln hat, gib $c_i[x]$ einen zusätzlichen Schlüssel, indem du einen Schlüssel von $x$ nach $c_i[x]$ verschiebst, einen Schlüssel vom unmittelbaren linken oder rechten Geschwisterkind von $c_i[x]$ nach $x$ verschiebst und den entsprechenden Kinderzeiger vom Geschwisterkind nach $c_i[x]$ verschiebst.
    • Wenn $c_i[x]$ und beide unmittelbaren Geschwister von $c_i[x]$ $t-1$ Schlüssel haben, verschmelze $c_i[x]$ mit einem Geschwisterkind, was beinhaltet, einen Schlüssel von $x$ in den neuen verschmolzenen Knoten zu verschieben, um der mittlere Schlüssel für diesen Knoten zu werden.