Prinzip:

• Datenstruktur genauso wie beim R-Baum
• lediglich verbesserte Algorithmen für das Einfügen neuer Einträge

Verbesserungen:

• Übervolle Knoten werden nicht sofort gesplittet. Stattdessen wird ein Teil der Einträge (z.B. 30%) ausgewählt, aus dem Knoten entfernt und erneut in den Baum eingefügt (forced insert).
  • weniger Seitensplits
  • größere Unabhängigkeit der Baumstruktur von der Eingabereihenfolge
• Verbesserter Seitensplit:
  • Optimierung von Überlappung, Fläche und Umfang der DirBBs
  • nur Heuristik möglich:
    1. Auswahl einer Splitachse (Kriterium Umfang)
    2. Auswahl eines Splits über diese Achse (Kriterium Überlappung) (siehe ...)