Was ist ein B-Baum?
Ein B-Baum ist eine Datenstruktur, die vor allem für Datenbanken (z.B. SQLite) und Dateisysteme (z.B. ext3) eingesetzt wird. Im Folgenden sollte man immer im Hinterkopf behalten, dass an den Schlüsseln auch Werte – sog. Satellitendaten – hängen.
Was sind die Varianten des B-Baums?
Verbreitete Varianten des B-Baumes sind B+-Bäume, in denen die Daten nur in den Blättern gespeichert werden, und B*-Bäume, die durch eine modifizierte Überlaufbehandlung immer zu gefüllt sind. Alle diese Varianten werden wie auch der reguläre B-Baum in der Praxis oft eingesetzt.
Was sind die B-Bäume?
1972 wurden die B-Bäume (Englisch B-tree) von Rudolf Bayer und Edward M. McCreight entwickelt. In Kombination mit dem relationalen Datenbankmodell wurde die erste Basis für SQL-Datenbanksysteme bei IBM geschaffen, da der Baum eine perfekte Daten- und Indexstruktur zur Verwaltung von Indizes darstellt. Jeder Knoten besitzt höchstens Schlüssel.
Was sind die verschiedenen Operationen von B-Baum?
Zusätzlich zeigen wir dir, die verschiedenen Varianten der Operationen: Suchen, B-Baum Einfügen, B-Baum Löschen von Elementen eines Blatts, sowie eines inneren Knotens mittels Verschiebungen und Verschmelzungen inklusive Beispiel. Doch eigentlich willst du die Funktionsweise einfach und schnell an einem B-Baum Beispiel verstehen?
Wie viele Schlüssel gibt es in einem B-Baum?
In einem B-Baum der Ordnung 2 hat jeder Knoten mindestens einen und höchstens 3 Schlüssel. Egal wo wir also landen würden, es würde noch in diesen Baum passen. Wir landen aber im Knoten rechts unten, da 11 < 16 11 < 16 ist. Will man nun in den B-Baum der Ordnung 2 aus Abb. 3 den Schlüssel 17 hinzufügen, so gibt es einen „Knotenüberlauf“.
Wie kann man ein B-Baum einfügen?
Wenn man in einen B-Baum einfügen möchte, wird erstmal das entsprechende Blatt gesucht, in dem das neue Element eingefügt werden soll. Nun muss zwischen zwei Fällen unterschieden werden: