iv_an_runikichaleпропущено...


Не понял, причем тут свойства Z-кривой, по моему доступ по любому индексу в большой файл плох, если порядок записей в таблице и в индексе не коррелируют.В случае случайного доступа к "зету" на случайных данных, плох не только доступ к записям таблицы по индексу, но и доступ к страницам самого индекса.

С другой стороны, есть алгоритмы, как раз хорошо оптимизируемые под Z-порядок. Например, микрософтовская пирамида растров. В ней k-ая плитка N-го уровня получается склейкой плиток уровня 0 с Z-номерами от 4^N * k до 4^N * (k+1) - 1 включительно, либо склейкой плиток уровня N-1 с Z-номерами от 4k до 4k+3. Сплошные последовательные чтения, для диска это удобнее некуда.

Ну так это как раз то, что нужно для поиска точек в рамке: "k-ая плитка N-го уровня" это рамка некоторого размера для поиска, а плитки уровня 0 с Z-номерами в интервале от 4^N * k до 4^N * (k+1) - 1 это Z-номера точек которые в ней содержаться! Если рамка поиска не совпадает с плитками - ее нужно покрыть с запасом несколькими плитками так, чтобы минимизировать запас при небольшом количестве плиток. Т.е., чтобы найти точки в некоторой окрестности нужно просканировать несколько интервалов в упорядоченном массиве с Z-номерами точек. И все. И никакие несбалансированные 2D деревья тут не нужны.