Datenstrukturdienstag:
B-Bäume und B+-Bäume (nein, das B steht nicht für “Binary”). Beides selbst-balancierende Suchbäume.

Was ist “Balancierend”?
Wenn man einen Baum hat, in dem man Daten sucht, ist die Zeit, die man braucht, um ein Element zu finden, häufig an die Höhe des Baums gebunden. Es ist also von Vorteil, wenn der Baum möglichst niedrig ist.
Je nach Baum kann es aber vorkommen, dass es einen langen Pfad gibt, der deutlich länger als die anderen im Baum ist. Sowas ist immer ungünstig, wenn man dann genau eines der Elemente sucht, das sich in diesem langen Pfad befindet.
Hierfür hat balanciert man Bäume - d.h. man ordnet die Knoten so um, dass die Blätter des Baums immer in etwa auf der gleichen Höhe hängen.
“Selbst-balancierend” heißt hier, dass das nicht ein Prozess ist, der ab und zu mal angestoßen wird, sondern dass die Operationen auf dem Baum (einfügen, Löschen etc.) so definiert sind, dass er sich beim Verändern entsprechend balanciert.

Beide Strukturen werden häufig in Datenbanken und vor allem in Dateisystemen verwendet, z. B. bei NTFS und ext4.