Get these flashcards, study & pass exams. For free! Even on iPhone/Android!

Ist eine Erweiterung des B-Baums um mehrere Dimensionen. FOs können beliebige räumliche Ausdehnung haben.

Cluster-Bildung: lokal gruppierend.
Cluster-Überlappung: Können überlappen, führt zu weniger effizienter Suche
Balance: Ist balanciert durch Split-Algorithmus beim Seitenüberlauf und Seitenzusammenfassung beim Unterlauf.
Objektspeicherung: Nur in den Blättern.
Geometrie: MBR
Anzahl der Kindknoten: An Seitengröße angepasst.

Einfügen:

• Von der Wurzel ausgehend den Kindknoten suchen, dessen Volumen nur minimal erweitert werden müsste.
• Ist dies nicht eindeutig, den Kindknoten wählen, dessen Volumen das kleinste ist.
• Objekt einfügen und Vaterknoten anpassen.
• Wenn ein Knoten überläuft, MBR in zwei kleinere MBR mit minimaler Volumensumme zerlegen. Es gibt verschiedene Algorithmen, üblicherweise nimmt man den linearen.

Suche geht über BaB, HS- und RKV-Algorithmen. Bei Bereichsanfragen muss man in jeden Unterbaum navigieren, dessen MBR den Suchbereich schneidet. Ab Dimension 10 ist NN-Suche nicht mehr effizient. Ausserdem bei hohen Dimensionen stärkere Überlappung -> hoher Suchaufwand

Der R+-Baum ist ein R-Baum ohne Überlappung und erfordert daher einen neuen Einfügealgorithmus. Ein Einfügen kann die Anpassung mehrerer Blätter erfordern. Wenn kein umfassender MBR gefunden werden kann, müssen Einträge mehrfach vorkommen. Ist trotzdem effizienter als R-Baum aber in hohen Dimensionen immer noch ineffizient.