О трехмерном Z-order замолвите слово

[andy_p]

kdtree для индексации данных на сфере не рассматривался?

[zzeng]

IMHO оно несбалансировано, деградирует при интенсивной вставке/удалении.
Кроме того, предназначено для хранения точек, прямоугольники потребуют удвоения размерности дерева, что усугубит вышеуказанные проблемы.
Не используется (я не знаю, во всяком случае) в СУБД.

[andy_p]

> деградирует при интенсивной вставке/удалении.

Э-э-э… А что, звезды так часто зажигаются/гаснут?

[AlexanderG]

Значит, это кому-нибудь нужно.