DE 
English
Українська
Polski🗃️ B-Baum — Mehrweg-Suchbaum
Bauen Sie einen B-Baum der Ordnung m durch Einfügen von Schlüsseln: Knoten füllen sich, teilen sich am Median und schieben einen Schlüssel nach oben, sodass jedes Blatt auf derselben Tiefe bleibt. Die Struktur hinter Datenbank- und Dateisystem-Indizes.
Über diese Simulation
Ein B-Baum der Ordnung m ist ein selbstbalancierender Mehrweg-Suchbaum, in dem jeder Knoten zwischen ⌈m/2⌉−1 und m−1 Schlüssel sowie zwischen ⌈m/2⌉ und m Kindzeiger hält. Schlüssel innerhalb jedes Knotens bleiben sortiert, und Kindzeiger trennen aufeinanderfolgende Schlüsselintervalle, sodass eine Suche höchstens O(log⌈m/2⌉ n) Knoten durchläuft — typischerweise nur 2–4 Knoten für einen Millionen-Eintrags-Datenbankindex.
Häufig gestellte Fragen
Was ist ein B-Baum?
Ein B-Baum ist ein selbstbalancierender Mehrweg-Suchbaum. Jeder Knoten kann viele Schlüssel und viele Kinder halten, und alle Blätter bleiben auf derselben Tiefe, sodass Suchen, Einfügen und Löschen O(log n) mit sehr wenigen Knotenbesuchen sind — ideal für platten- und seitenbasierten Speicher.
Was bedeutet die Ordnung m?
Die Ordnung m ist die maximale Anzahl an Kindern, die ein Knoten haben darf. Ein Knoten der Ordnung m hält höchstens m−1 Schlüssel und, wenn er nicht die Wurzel ist, mindestens ⌈m/2⌉−1 Schlüssel. Diese Simulation lässt Sie m von 3 bis 6 wählen.
Wie funktioniert eine Teilung?
Wenn ein Knoten mit m Schlüsseln überlaufen würde, teilt er sich: Der Median-Schlüssel wird in den Elternknoten hochgeschoben, und die restlichen Schlüssel werden zu zwei Geschwisterknoten. Teilt sich die Wurzel, wird eine neue Wurzel erzeugt und der Baum wächst um eine Ebene.
Warum bleiben alle Blätter auf derselben Tiefe?
Ein B-Baum wächst nur höher, indem sich die Wurzel teilt und einen Schlüssel nach oben schiebt. Da sich Teilungen nach oben fortpflanzen und niemals nur einen Zweig verlängern, hat jeder Wurzel-zu-Blatt-Pfad stets exakt dieselbe Länge, was den Baum perfekt höhenbalanciert hält.
Warum werden B-Bäume für Datenbank-Indizes verwendet?
Da jeder Knoten viele Schlüssel packt, ist der Baum sehr flach, sodass eine Suche nur eine Handvoll Knoten — und damit eine Handvoll Festplattenseiten — berührt. Dies minimiert langsame Festplattenzugriffe, weshalb B-Bäume und ihre B+-Baum-Variante fast jeden relationalen Datenbankindex und viele Dateisysteme unterstützen.