B-Baum

Der B-Baum (engl. B-tree) ist eine effiziente Baumdatenstruktur, die vor allem in Datenbanken und Dateisystemen eingesetzt wird. Er ermöglicht schnelle Such-, Einfüge- und Löschoperationen, selbst bei großen Datenmengen.

Im Gegensatz zu einfachen Binärbäumen erlaubt der B-Baum die Speicherung mehrerer Schlüssel pro Knoten und ist besonders für Blockzugriffsgeräte wie Festplatten optimiert. Entwickelt wurde er 1972 von Rudolf Bayer und Edmund McCreight, um die Performance von Speichersystemen zu verbessern.

Durch seine balancierte Struktur und geringe Höhe bleibt der B-Baum auch bei häufigen Änderungen stabil und gewährleistet eine gleichmäßige Auslastung der Speichermedien.

B-Baum - Aufbau und Struktur

Ein B-Baum besteht aus internen Knoten und Blättern, wobei jeder Knoten bis zu m Kinder (bei einem m-ären B-Baum) und bis zu m−1 Schlüssel enthalten kann. Die Ordnung m (meist eine ungerade Zahl ≥ 3) bestimmt die maximale Anzahl der Kinder und Schlüssel pro Knoten.

Blätter speichern die eigentlichen Daten und sind auf derselben Ebene, was die Suche beschleunigt. Interne Knoten enthalten nur Suchschlüssel, die die Kinder trennen, und verweisen auf deren erste Schlüssel. Durch Split-Operationen bei Überfüllung und Verschmelzungen bei Unterfüllung bleibt der Baum balanciert und minimiert die Suchtiefe.

Diese Eigenschaften machen den B-Baum besonders für sekundäre Speicher geeignet, da er die Anzahl der I/O-Operationen reduziert.

B-Baum - Vorteile und Nachteile

Vorteile von B-Bäumen

Der B-Baum bietet mehrere entscheidende Vorteile für den Einsatz in Speichersystemen:

• Effiziente Suche: Durch die geringe Höhe des Baumes (logarithmische Komplexität) werden Suchoperationen auch bei großen Datenmengen schnell ausgeführt.
• Optimierte Speichernutzung: Die Speicherung mehrerer Schlüssel pro Knoten reduziert die Anzahl der benötigten Zugriffe auf Blockspeicher wie Festplatten.
• Dynamische Anpassung: Der Baum passt sich durch Split- und Merge-Operationen automatisch an wachsende oder schrumpfende Datenmengen an, ohne seine Balance zu verlieren.
• Geringe Fragmentierung: Im Vergleich zu linearen Strukturen wie Arrays oder verketteten Listen vermeidet der B-Baum Speicherfragmentierung und hält die Daten kompakt.

Nachteile von B-Bäumen

Trotz seiner Stärken gibt es auch einige Einschränkungen:

• Komplexität der Implementierung: Die Split- und Merge-Operationen erfordern präzise Algorithmen, um die Balance des Baumes zu erhalten, was die Implementierung aufwendiger macht.
• Speicheroverhead: Jeder Knoten benötigt zusätzlichen Platz für Zeiger auf Kinder und Schlüssel, was bei sehr kleinen Datensätzen ineffizient sein kann.
• Eingeschränkte Eignung für Hauptspeicher: Da der B-Baum für Blockzugriff optimiert ist, ist er für Anwendungen im Hauptspeicher (RAM) oft weniger geeignet als Hash-Tabellen oder Binärbäume.
• Feste Ordnung: Die Wahl der Ordnung m beeinflusst die Performance; eine zu kleine Ordnung führt zu hohen Bäumen, eine zu große zu ineffizienter Speichernutzung.

B-Baum - Beispiel für B-Baum

Ein einfaches Beispiel eines B-Baums der Ordnung 3 (maximal 2 Schlüssel pro Knoten) sieht wie folgt aus:

    [10, 20]
   /    |    \
[5, 7] [15] [25, 30]

• Wurzelknoten: Enthält die Schlüssel 10 und 20 und verweist auf drei Kinder.
• Interne Knoten: Der Knoten trennt die Blätter und verweist auf diese.
• Blätter: Enthalten die Werte und sind auf derselben Ebene.

Wird der Schlüssel 8 eingefügt, spaltet sich der Blattknoten [5, 7, 8] in [5] und [8], und der mittlere Schlüssel 7 steigt in den internen Knoten auf.

    [7, 10, 20]
   /     |      \
[5] [8] [15] [25, 30]

Warum steigt beim Split genau der Schlüssel 7 auf?

Wird in einem B-Baum ein neuer Schlüssel eingefügt, darf ein Knoten die maximal erlaubte Anzahl an Schlüsseln nicht überschreiten. Im Beispiel entsteht im Blattknoten die Folge [5, 7, 8]. Da dieser Knoten nun zu viele Schlüssel enthält, muss er aufgeteilt werden.

Dabei wird der mittlere Schlüssel ausgewählt - hier die 7. Dieser Schlüssel hat eine besondere Eigenschaft: Er trennt die kleineren Werte (5) eindeutig von den größeren Werten (8). Der mittlere Schlüssel 7 wird deshalb in den übergeordneten (internen) Knoten verschoben. Links von ihm befinden sich alle kleineren Schlüssel, rechts alle größeren. So bleibt die Sortierordnung des B-Baums erhalten.

Wichtig ist außerdem: Die neu entstehenden Knoten bleiben Blätter, und alle Blätter liegen weiterhin auf derselben Ebene. Dadurch bleibt der B-Baum balanciert, was schnelle Such-, Einfüge- und Löschoperationen garantiert.

B-Baum - Definition & Erklärung -Zusammenfassung

Im Zusammenhang mit dem Lexikoneintrag B-Baum sollte man sich folgende Punkte merken:

• Der B-Baum ist eine balancierte Baumdatenstruktur, die durch mehrfache Schlüssel pro Knoten und geringe Höhe Suchoperationen in logarithmischer Zeit ermöglicht.
• Seine Blockoptimierung macht ihn ideal für Datenbanken und Dateisysteme, während seine dynamische Anpassung durch Splits und Merges Stabilität bei Datenänderungen garantiert.
• Trotz Implementierungsaufwand und Speicheroverhead übertrifft der B-Baum lineare Strukturen in Performance und Speichereffizienz für große, auf Blockspeicher gespeicherte Datensätze.