iv_an_ruОдин только недостаток у этой кривой --- мрачная непредсказуемость селективности, поэтому при попытке использовать её на большой дисковой памяти SQL-процессор встаёт колом. Для хорошего пространственного индекса N точек на квадрате площади 1, матожидание трудоёмкости выборки "рамкой" со стороной 1/x почти пропорционально 2 ln(x) + N/(pagesize * x^2), а Z-ордер с вероятностью, экспоненциально падающей с ростом x, выкидывает "фортели", приводящие к чтению до половины точек набора, давая разброс от 2 ln(x) + N/(pagesize * x^2) до 2 ln(x) + N/(pagesize * 2). Для иных задач простая выборка по X и потом по Y может оказатьcя не хуже :)
тут к сожалению или к счастью он прав, при выборе алгоритма Z-обхода нужно "что-то знать о данных"

д0kВ подавляющем большенстве случаев этот матан используется как империческая
константа определяющая критерии балансировки дерева.
автобалансировку для 2D-дерева пока не придумали, насколько мне известно

можно построить совсем не идеальное, но очень простое дерево
модификация декартова дерева:
задать каждой координате случайное число Z - O(n)

отсортировать по Z - O(n*ln(n))

последовательно по уменьшению или увеличению Z добавлять в 2D-дерево, для определения направления С-Ю или З-В использовать н-р чётность Z проходимого узла - O (Ln(n!))

в целом получится O(n*ln(n)) на составление дерева

д0kНе знаю получится ли , но попробую поумничать :)
ИМХО
это только кажется, что данные случайны
потому что система представления физических сущьностей неверная.
Иногда достаточно первести представление для хранения из
декартовой плоскости в полярную систему координат или наоборот
и все оптимизируется само собой...
обычная задача ГИС - поиск окрестностей точки, для любой точки - не прокатит