$(a,b)$-Bäume

Definition: Ein $(a,b)$-Baum ist ein externer höhenbalancierter (alle Blätter gleiche Tiefe) Suchbaum, bei dem jeder innere Knoten zwischen $a$ und $b$ Kinder hat, die Wurzel zwischen $2$ und $b$. Es gilt stets $b \geq 2a-1$. Die inneren Knoten tragen die Minimal-Schlüsselwerte der Kinder.

Definition: Ein B-Baum (B Tree) [Bayer, McCreight] ist ein $(a,b)$-Baum mit $b = 2a-1$.

Operationen:

1. $Find(k,T)$: Von der Wurzel wird der Baum über die Referenzen bis zu den Blättern traversiert

2. $Insert(x,T)$: $x$ bzw. das Element $w$ mit nächstgrößerem Schlüssel suchen, $x$ links vom Blatt $w$ einfügen. Wird dadurch der Verzweigungsgrad der Vaters zu groß, so ist er zu unterteilen und wiederum der Verzweigungsgrad seines Vorgängers (rekursiv bis zur Wurzel) zu überprüfen.

3. $Delete(x,T)$: Suche $x$ und entferne das Element. Wird dadurch der Verzweigungsgrad des Vaters zu klein, so kann er entweder mit einem Nachbarn verschmelzen (falls beide nicht zu groß werden, also Nachbar $\leq a$) oder ein Kind des Nachbarn adoptieren (falls Nachbar $> a$)

Analyse:
- Alle Operationen benötigen Zeit $O(\log n)$
- Für einen Baum mit Höhe $h$ und $m$ Blättern gilt:
$2a^{h-1} \leq m \leq b^h$
$\log_b{m} \leq h \leq 1 + \log_a{m/2}$

Bemerkung:
B-Bäume finden in Datenbanksystemen Verwendung. Sie werden auf der Platte mit großem $b$, im RAM mit kleinem $b$ gespeichert.