Neuer Eintrag <BBN, TIDN>

• Geeignetes Blatt suchen:
  • Beginne in der Wurzel
  • Wähle den Nachfolger, dessen DirBB minimal vergrößert werden muß
• Eintrag in Blatt einfügen:
  • Bei Overflow Blatt splitten
• Vaterknoten rekursiv anpassen:
  • DirBBs vergrößern
  • Bei Split neuen Eintrag hinzufügen

Bei rekursiven Splits bis zur Wurzel wächst der Baum um genau eine Ebene!