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

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