Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

Normale Binärbäume lassen sich schlecht auf Seiten abbilden und sind deswegen ungeeignet. Besser sind da B-Bäume, deren Knotengrößen auf Seitengröße abgestimmt werden und auf eine Seite abgebildet werden. Jeder Eintrag im Knoten umfasst Schlüssel und Tupel.
Die Anzahl der Seitenzugriffe beim Zugriff entspricht der Höhe des Baums, durch die Balancierung ist jedes Blatt gleich weit weg von der Wurzel. Jeder Knoten hat zwischen und Einträge, nur die Wurzel hat Einträge. Auf Einträge folgen an Nicht-Blättern Kinder.
Beim Löschen oder Einfügen muss der Baum ggf. neu balanciert werden, damit diese Eigenschaften erfüllt werden.

Besser: B+-Bäume