Informatik Datenstrukturen – B-Bäume
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was ist ein B-Baum? · Was legt die Ordnung m eines B-Baums fest?
Karten
15 KartenWas ist ein B-Baum?
Rückseite
Ein selbstbalancierender Suchbaum, bei dem alle Blätter auf gleicher Tiefe liegen und Knoten mehrere Schlüssel und Kindzeiger enthalten dürfen.
Was legt die Ordnung m eines B-Baums fest?
Rückseite
Maximale Kinderanzahl pro Knoten ist m; jeder innere Knoten (außer Wurzel) hat mindestens ⌈m/2⌉ Kinder und entsprechend viele Schlüssel.
Wie viele Schlüssel enthält ein innerer Knoten mindestens und maximal?
Rückseite
Mindestens ⌈m/2⌉ − 1, maximal m − 1 Schlüssel; die Wurzel darf weniger haben, solange sie nicht Blatt ist.
Welche Eigenschaft garantiert, dass alle Blätter dieselbe Tiefe haben?
Rückseite
Bei Splits wird der mittlere Schlüssel in den Elternknoten hochgezogen; die Baumhöhe wächst nur an der Wurzel, nie an den Blättern.
Wie verläuft die Suche nach einem Schlüssel im B-Baum?
Rückseite
Vom Wurzelknoten abwärts: Schlüssel mit Knotenschlüsseln vergleichen, passenden Kindzeiger folgen, bis Blatt erreicht oder Schlüssel gefunden wird.
Was passiert beim Einfügen, wenn ein Blattknoten bereits m − 1 Schlüssel enthält?
Rückseite
Der Knoten wird gesplittet: mittlerer Schlüssel wandert zum Elternknoten, linke und rechte Hälfte bilden zwei neue Kindknoten.
Wie wird ein Split an der Wurzel behandelt?
Rückseite
Eine neue Wurzel wird erzeugt, der mittlere Schlüssel wird dort eingetragen, die beiden Hälften werden ihre Kinder – Baumhöhe steigt um 1.
Welche Strategien gibt es beim Löschen, um Unterlauf (Underflow) zu vermeiden?
Rückseite
Schlüssel aus linkem oder rechtem Geschwisterknoten leihen (Rotation) oder mit Geschwister und Elternschlüssel verschmelzen (Merge).
Was unterscheidet einen B+-Baum vom klassischen B-Baum?
Rückseite
Nur Blätter speichern Datensätze; innere Knoten nur Routing-Schlüssel. Blätter sind zusätzlich als verkettete Liste verbunden für Bereichsabfragen.
Warum sind B-Bäume für Festplattenzugriffe besser geeignet als binäre Suchbäume?
Rückseite
Hoher Verzweigungsgrad reduziert Baumhöhe drastisch; ein Knoten passt in einen Festplattenblock, minimiert I/O-Operationen bei Suche, Einfügen, Löschen.
Wie lautet die Zeitkomplexität für Suche, Einfügen und Löschen im B-Baum?
Rückseite
Alle Operationen laufen in O(logₘ n) Zeit, wobei m die Ordnung und n die Anzahl gespeicherter Schlüssel ist.
Welche typischen Anwendungen nutzen B-Bäume oder Varianten?
Rückseite
Datenbank-Indizes (MySQL InnoDB, PostgreSQL), Dateisysteme (NTFS, ext4, HFS+), NoSQL-Stores (MongoDB WiredTiger).
Was versteht man unter einem B*-Baum?
Rückseite
Variante mit höherer Auslastung: Knoten werden erst bei 2/3-Füllung gesplittet, stattdessen werden Schlüssel in Geschwisterknoten verschoben (Redistribution).
Wie viele Kindzeiger hat ein Blattknoten im B-Baum?
Rückseite
Null – Blattknoten enthalten nur Schlüssel und optional Datensatzzeiger, keine weiteren Kindzeiger.
Wann ist ein B-Baum der Ordnung 3 minimal gefüllt?
Rückseite
Jeder innere Knoten (außer Wurzel) hat mindestens 2 Kinder und 1 Schlüssel; Blätter enthalten mindestens 1 Schlüssel.