cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

B-Bäume

anchored to [[111.00_anchor]] requires [[111.08_algo_datastructures#Trees Grundlegende Definition]] and [[111.36_balanced_search_trees]]

Overview |

Wir möchten folgend eine spezifischere Version von Bäumen betrachten:

[!Definition] B-Bäume welche drei Eigenscahften hat ein B-Baum. Worin besteht die Motivation von B-Trees? #card Wir sprechen bei einem Bau von einem B-Baum, wenn dieser der Ordnung $k\ge 2$ ist und er folgende Eigenschaften aufweist:

1. alle Blätter haben die gleiche Tiefe –> sonst wäre er unbalanced!
2. die Wurzel des Baumes hat $\ge 2$ Kinder, und weiterhin haben alle weiteren Knoten dann immer$\ge k$ Kinder
3. die inneren Knoten ( also nicht die Kinder ganz links und rechts von einem Knoten ) haben zwingend $\le 2k-1$ Kinder!

B-Trees nutzen wir, weil sie in ihrer Struktur / Definition große Datenmengen in flachen Bäumen speichern können, denn sie können pro Knoten mehrere Kinder aufweisen. Dabei kann jetzt jeder Knoten mehrere Keys aufweisen, wodurch sie sich größer auffächern können. Weiterhin geben wir aber eine obere Grenze von Keys an, sodass der Tree balanciert wird ( ein Knoten darf nicht über $2\cdot k-1$ keys haben und somit nur $2\cdot k$ Kinder haben!) ^1706630244046

[!Warning] Was wird mit einem inneren Knoten gemeint? #card Ein innerer Knoten in einem Baum ist solcher, der auf seiner Höhe noch weitere Nachbarn hat und somit nicht die Wurzel oder ein Blatt ( also Boden vom Baum) ist! ^1706630244058

Eigenschaften |

Es ergeben sich für diese Datenstruktur jetzt folgende Eigenschaften:

[!Important] In welchem Größenbereich ( Range, abhängig von Ordnung $k$ und Höhe $h$) kann sich $n$ befinden? #card Sofern $T$ ein B-Baum der Ordnung $k$ mit $n$ Blättern und einer Höhe von $h$ ist, gilt jetzt folgend: $$2k^{h_{1-1}}\le n\le (2k-1{)}^h$$

Beweisen können wir es folgend: Die Zahl der Blätter ist minimal, wenn der innere Knoten die Minimalanzahl von Kindern hat. Also genau dann, wenn diese inneren Knoten $2k^{h-1}\le n$ was laut 3. Bedingung ${\le }_{2}k-1$ gefordert ist! Weiterhin ist die Blattzahl maximal, wenn die Konten eine Maximalzahl von Kindern haben, denn dann folgt zwingend: $n\le (2k-1{)}^h$ wobei $h$ angibt, wie viele wir davon haben!

Es gilt dann folgend: $${\log }_{2k-1}\cdot n\le h\le 1_{+}{\log }_k\left(\frac{n}{2}\right)$$ ^1706630244066

Folgend können wir uns noch anschauen, wie in einem Knoten eines von $i$ Kindern gefunden bzw spezifisch ausgewählt werden kann.

[!Definition] Schlüssel eines Knoten $u$, welche Speicherorientierung liegt vor? was gilt für einen Schlüssel und dessen Teilbaum dazu? #card Wir betrachten einen Knoten $u$. Dieser hat $s_1,\dots ,s_{i-1}$ Schlüssel ( welche dabei Im Knoten direkt gespeichert werden ) –> also knotenorientierte Speicherung und jedem Schlüssel ist jeweils ein Unterbaum zugeschrieben, unter welchem wir weiter expandieren.

![[Pasted image 20240124150952.png]]

Diese Schlüssel sind geordnet und somit gilt jetzt folgend für die Knoten im Teilbaum von einem Schlüssel $s_i$: wenn $i=1$ –> also der linkeste Schlüssel im Knoten, dann: $s\le s_1$ –> also alle Schlüssel im Teilbaum müssen zwingend kleiner sein, als der Schlüssel von $s_{i=1}$ im Knoten $U$ –> von wo aus wir schauen!

falls $1<i<I$ ( also einer der zwischen dem linkesten /rechtesten Schlüssel im Knoten $u$ liegt), dann gilt: $s_{i-1}<s<s_j$ –> also alle Schlüssel innerhalb dieses Teilbaums von $s_i$ müssen größer als der Schlüssel links von $s_i$ ($S_{i-1}$) und kleiner als der Schlüssel rechts von $s_i$ ( $s_{i+1}$) sein

falls jetzt noch: $i=I$, also der Schlüssel ganz rechts vom Knoten $u$, dann ist der Schlüssel größer und somit alle Elemente des Teilbaumes, größer als die linken Nachbarn $s_{I-1}<s$ ^1706630244074

Zugreifen / Suchen

Wir möchten folgend den Verlauf einer Suche bzw eines Zugriffes in einem B-Baum betrachten:

[!Information] Zugriff mit Schlüssel $a$ und B-Baum $S$ wie suchen wir jetzt entsprechend nach unserem Inhalt? whats the resulting runtime? #card Wir beginnen in der Wurzel unseres Baumes $S$ Wenn in wir da schon unseren Schlüssel in der Liste der Schlüssel ( es kann ja mehr als 2 geben!) finden, dann sind wir schon fertig. Sonst , schauen wir, wo sich der Schlüssel befinden kann ( wir wissen ja, dass die Schlüssel sortiert und die Schlüssel derer Teilbäume auch wieder kleiner sein müssen) und suchen dann mit dieser Information den Schlüssel Wir finden ihn / oder auch nicht Wir können jetzt den Eintrag in $\mathcal{O}(k\cdot {\log }_{k}n)$ finden –> weil wir ja pro Teilbaum maximal $k$ Elemente betrachten werden! ^1706630244082

Einfügen

Auch hierfür möchten wir eine sinnige Implementation finden, die es uns ermöglicht neue Elemente in den Baum einzufügen, so dass die Struktur erhalten bleibt!

[!Definition] Einfügen von Schlüssel $a$ wie gehen wir vor? Was passiert bzw was ist wichtig für den Knoten, wo er eingefügt wird? #card Wir wollen nach folgendem Ablauf agieren / arbeiten:

1. Zugriff für Element $a$ $Search(a,S),S\in T$. Wir werden an einem Punkt ein Ende erreichen ( das Element existiert noch nicht!)
2. An diesem Blatt $b$ und dessen $parent$ “verorten wir jetzt $a$”, weil wir ja nach der Suche immer nach den Keys traversieren und abbiegen, bis wir beim gesuchten Key angekommen sind ( oder unser gesuchter kleiner/größer ist)
3. Sei dann jetzt bei diesem Parent $s_j$ der kleinste Schlüssel, wobei hier jetzt weiter $a<s_j$ ( und wenn dieser Eintrag existiert, ist der zuvor gefundene Eintrag $b$ das $j$-te Blatt, was größer ist! )
4. Wir fügen jetzt folgend $a$ als Schlüssel in $v$ links von $s_j$ ein und erweitern weiterhin den Bereich links von a um das Blatt $b^{\prime }$. und den Bereich rechts von $a$ ( also größer $a$, aber kleiner $s_j$) um $b$ ( den wir zuvor schon hatten) Wir erhalten folgende Struktur: ![[Pasted image 20240125210739.png]] nach dem einfügen –> der Knoten $v$ hat einen weiteren Schlüssel –> Prüfen, ob wir noch $2k-1$ Kinder haben, sonst müssen wir aufspalten ^1706630244091

Am Ende wird ein mögliches Problem beim einfügen eines neuen Elementes genannt, welches wir betrachten und zur Not kompensieren müssen. Für diesen Fall, dass jetzt also der Knoten $v$ mehr Kinder hat, als erlaubt, müssen wir den Baum entsprechend erweitern/ anpassen.

[!Definition] Aufspalten, wenn wir im Knoten $2k$ Kinder/Schlüssel haben! wie müssen wir jetzt vorgehen,um die verletzte Eigenschaft aufzulösen? #card Wir sehen jetzt, dass unser erweiterte Knoten $v$ mit $2k$ Knoten zu groß ist, also müssen wir aufspalten. Dafür brauchen wir den Parent von $w$ und werden jetzt folgend $v$ in zwei Knoten mit jeweils $k$ Kindern aufspalten.

1. Wir nehmen uns den Schlüssel $s_k$ aus dem Knoten $v$ ( weil dieser die Mitte bildet! also alles links ist kleiner, alles rechts größer) und werden diesen als Schlüssel im Parent $w$ einfügen.
2. Jetzt wissen wir, dass alle Schlüssel $s_1,\dots s_{k-1}$ kleiner sind, als $s_k$ und somit können wir den Baum mit diesen Schlüsseln jetzt in die Lücke links von $s_k$ im Knoten $w$ einbringen
3. Weiterhin gilt selbiges für die Elemente rechts von $s_k$ also $s_{k+1},\dots 2k$ und die binden wir nach selbigen Prinzip rechts von $s_k$ im Knoten $w$ also dem Parent! Beachte, dass jetzt $w$ einen Schlüssel $s_k$ mehr hat und wir müssen somit schauen, das auch für diesen die Menge von Schlüssel $\le 2k-1$ ist Sonst müssen wir weiter aufteilen, anch selbigen Prinzip ![[Pasted image 20240125212923.png]] ^1706630244099

[!Information] Overview Einfügen in einen B-Baum was müssen wir beachten, wenn wir ein neues Element einfügen möchten? #card Wir suchen zuerst den Punkt im Baum, wo wir dann den neuen Schlüssel einfügen können ( also da, wo $a$ < $s_k$ und $a>s_{k-1}$ (irgendwo im Teilbaum ist unser Schlüssel passend!)). Dann werden wir folgend das Element als neuen Schlüssel einfügen und müssen bei erreichen von $2k$ Kindern in einem Knoten $v$ diesen in zwei Knoten $\mid v^{\prime }\mid =k$ und $\mid v^{\prime \prime }\mid =k$ aufteilen und dabei dann in den Parent-Knoten $w$ $s_k\in v$ als neuen Schlüssel einfügen. Hier kann es dabei wieder zu Problemen kommen –> es kann dabei bis zur Wurzel iterieren.

Nur bei Eintreten dieses Falles wird die Höhe des Baumes um 1 erhöht ^1706630244108

Entfernen / Removing from B-trees

Nach der Suche und dem Einfügen, möchten wir noch das entfernen von Elementen betrachten. Man kann schon vermuten, dass es Fälle gibt, wo dann ein Teilbaum bzw Knoten angepasst oder verändert werden muss ( sonst könnten wir irgendwann nur noch Hüllen haben, visuell betrachtet)

[!Definition] Entfernen von Schlüssel $a$ wie gehen wir vor, was müssen wir nach der Ausführung betrachten? #card Auch hier möchten wir zuerst mit $Search(a,S)$ nach dem Element suchen, damit wir damit anschließend arbeiten können. Wir haben das Element dann im Knoten $u$ am $j$ ten Schlüssel gefunden. Sei dann jetzt $T_j$ der Unterbaum links von $a$. Wenn er nur aus einem Blatt besteht, können wir den Schlüssel $a$ löschen, weil wir damit keinen Verlust erleben. Dabei verringert sich die Zahl von Kindern im Knoten $u$. Wenn der Teilbaum ${}_j$ jetzt größer ist, dann ist $s$ der rechteste Schlüssel innerhalb des betrachteten Teilbaums $T_j$. Wir entfernen dieses Element aus dem Teilbaum und nehmen es als neuen Schlüssel statt $a$ -> wir haben also $s$ entfernt und werden das größte Element des linken Teilbaums davon als neuen Schlüssel nehmnen. Problem was jetzt auftreten könnte: Wir haben weniger als $k$ Kinder in einem Knoten –> wir verletzten also eine Grundeigenschaft ^1706630244116

Wie obig beschrieben kann es dazu kommen, dass beim Entfernen eines Elementes ein Knoten weniger als $k$ Elemente aufweist und somit die Eigenschaft verletzt, die sie haben müssen. Wir möchten das jetzt noch betrachten und eine Lösung dafür konzipiern.

[!Definition] Entfernen | Wie gehen wir vor, wenn von einem Knoten $v$ nach dem löschen weniger als $k$ Kinder auftreten? Was müssen wir bei dem neuen Knoten beachten? #card Wenn $v$ eine Wurzel mit einem einzigen Kind ist, dann können wir diese Wurzel entfernen. –> Denn wir können das Element dann als Schlüssel im darüberliegenden Knoten übernehmen! Dabei verringert sich die Höhe des Baumes!

Wenn jetzt $v$ keine Wurzel ist, dann probieren wir diesen Knoten mit dem Geschwisterknoten zu vereinigen. Das heißt wir schauen uns von Schlüssel $s_1$ den Nachbarknoten an, wo der Baum $v$ dazwischen liegt (also etwa $s_0$ oder $s_2$), und versuchen dann die beiden zu verbinden und zu einem Knoten zu vereinigen. Visuell folgend: ![[Pasted image 20240125215506.png]] Dabei wir jetzt der neue Knoten $v=v_1\cup v_2$ eventuell zuviele Kinder haben mit $\le 3k-2$ Wenn das der Fall ist, dann spalten wir $v$ nochmals auf, bis wir entsprechend genug / wenige Knoten haben ->Diese Operation ist immer möglich! ^1706630244125

Wir können jetzt aus der obigen Betrachtung heraus folgende Eigenschaften zu B-Bäumen festhalten:

[!Important] Eigenschaften von B-Bäumen im Bezug auf die Operationen auf diesen was ist die Laufzeit für alle Operationen?, warum? #card Jegliche B-Bäume der Ordnung $k$ haben bei den Operationen Search,Einfügen,Entfernen eine Laufzeit von $$\mathcal{O}(k\log n),n=\text{ Menge von Schlu¨sseln}$$ Wie groß wählt man dann jetzt $k$? Das ist stark variable und kommt drauf an, wo man diese Struktur anwendet: -> Bei Festplatten schaut man, dass ein einziger Knoten auf das Paging eines Hauptspeichers passt ( man also nur einmal laden und dann mit schnellem Zugriff damit arbeiten kann) Das wäre meist so 4MB! ^1706630244133