Performanz von 3D-Bäumen.

Wenn die zu speichernden Datenpunkte annähernd gleichmäßig verteilt sind, erfolgt der Aufbau eines 3D-Baumes im Mittel in $\O(3 n \log n)$. Die Suchzeit im Baum ist direkt proportional zu den Knoten, die während der Suche besucht worden sind. Die Suche erfolgt in $\O(n^{2/3})$ [85]. Der 3D-Baum benötigt $\O(3 n)$ Speicher [85].