Der B-Baum ist eine in der Informatik weit verbreitete Datenstruktur für Datenbanken und Dateisysteme, die Daten sortiert nach Schlüsseln speichert und stets vollständig balanciert ist. Entwickelt wurde er 1972 von Rudolf Bayer und Edward M. McCreight; die Herkunft des Namens „B“ ist ungeklärt, wobei die häufigste Deutung für „balanciert“ steht. Im Gegensatz zu Binärbäumen erlaubt ein B-Baum mehr als zwei Kindknoten pro Knoten, wodurch die Baumhöhe und die Anzahl langsamer Festplattenzugriffe reduziert werden – ideal für Systeme mit riesigen Datenmengen, die nur blockweise in den Hauptspeicher geladen werden können. Diese Eigenschaften machten ihn zur Grundlage für das erste SQL-Datenbanksystem System R bei IBM. Einfügen, Suchen und Löschen sind in amortisiert logarithmischer Zeit möglich, und der Baum wächst – anders als viele Suchbäume – von den Blättern zur Wurzel.