Как использовать порядок Мортона (кривая z порядка) при поиске по диапазону?
Как использовать Morton Order в диапазоне поиска? Из вики, в параграфе "Использование с одномерными структурами данных для поиска по диапазону",
это говорит
"Запрашиваемый диапазон (x = 2, ..., 3, y = 2, ..., 6) указан пунктирным прямоугольником. Его наибольшее значение Z (MAX) равно 45. В этом примере значение F = 19 встречается при поиске структуры данных в направлении увеличения значения Z. ......BIGMIN (в нашем примере 36)..... поиск только в промежутке между BIGMIN и MAX...."
Мои вопросы:
1) почему F 19? Почему F не должно быть 16?
2) Как получить БОЛЬШОЙ?
3) Существуют ли какие-либо веб-блоги, демонстрирующие, как выполнять поиск по диапазону?
2 ответа
РЕДАКТИРОВАТЬ: блог базы данных AWS теперь содержит подробное введение в эту тему.
Этот пост в блоге хорошо иллюстрирует процесс.
При поиске прямоугольного пространства x=[2,3], y=[2,6]
:
- Минимальное значение Z (12) определяется путем чередования битов младшего
x
а такжеy
значения: 2 и 2 соответственно. - Максимальное значение Z (45) определяется путем чередования битов старшего
x
а такжеy
значения: 3 и 6 соответственно. - Найдя минимальное и максимальное значения Z (12 и 45), теперь у нас есть линейный диапазон, который мы можем перебирать, который гарантированно содержит все записи внутри нашего прямоугольного пространства. Данные в линейном диапазоне будут расширенным набором данных, которые нам действительно нужны: данные в прямоугольном пространстве. Если мы просто проведем итерацию по всему диапазону, мы найдем все данные, которые нас интересуют, а затем и некоторые. Вы можете проверить каждое значение, которое вы посещаете, чтобы увидеть, является ли оно актуальным или нет.
Очевидная оптимизация - попытаться минимизировать количество лишних данных, которые вы должны пройти. Это в значительной степени зависит от количества "швов", которые вы пересекаете в данных - местах, где кривая "Z" должна делать большие скачки, чтобы продолжить свой путь (например, от значения Z от 31 до 32 ниже).
Это может быть смягчено путем использования BIGMIN
а также LITMAX
функции, чтобы идентифицировать эти швы и перейти обратно к прямоугольнику. Чтобы минимизировать количество ненужных данных, которые мы оцениваем, мы можем:
- Ведите подсчет количества последовательных фрагментов ненужных данных, которые мы посетили.
- Определите максимально допустимое значение (
maxConsecutiveJunkData
) для этого рассчитывать. Сообщение в блоге, связанное в верхней части, использует3
за это значение. - Если мы столкнемся
maxConsecutiveJunkData
кусочки нерелевантных данных подряд мы инициируемBIGMIN
а такжеLITMAX
, Важно отметить, что в тот момент, когда мы решили их использовать, мы сейчас находимся где-то в пределах нашего линейного пространства поиска (значения Z от 12 до 45), но за пределами прямоугольного пространства поиска. В статье в Википедии они, похоже, выбралиmaxConsecutiveJunkData
ценность4
; они начинали с Z=12 и шли до тех пор, пока не достигли 4 значений за пределами прямоугольника (за 15), прежде чем решили, что пришло время использоватьBIGMIN
, Так какmaxConsecutiveJunkData
остается на ваш вкус,BIGMIN
может использоваться для любого значения в линейном диапазоне (значения Z от 12 до 45). В некоторой степени сбивает с толку, статья только показывает область от 19 до как перекрестно, потому что это поддиапазон поиска, который будет оптимизирован, когда мы используемBIGMIN
сmaxConsecutiveJunkData
из 4
Когда мы понимаем, что мы вышли за пределы прямоугольника слишком далеко, мы можем заключить, что прямоугольник не является смежным. BIGMIN
а также LITMAX
используются для определения характера раскола. BIGMIN
предназначен для того, чтобы при любом значении в пространстве линейного поиска (например, 19) найти следующее наименьшее значение, которое вернется обратно в половину разделенного прямоугольника с большими значениями Z (т. е. прыгнет с 19 до 36). LITMAX
аналогично, помогая нам найти наибольшее значение, которое будет внутри половины разделенного прямоугольника с меньшими значениями Z. Реализации BIGMIN
а также LITMAX
подробно объясняются в zdivide
объяснение функции в связанном сообщении в блоге.
Похоже, что приведенный пример в статье Википедии не был отредактирован для уточнения контекста и предположений. Подход, использованный в этом примере, применим к линейным структурам данных, которые допускают только последовательный (прямой и обратный) поиск; то есть предполагается, что никто не может случайным образом искать ячейку памяти в постоянное время, используя только ее индекс Morton.
С этим ограничением ваша стратегия начинается с полного диапазона, который является индексом мининовой доли (16) и максимальным индексом степени (45). Для оптимизации необходимо найти и устранить большие полосы поддиапазонов, которые находятся за пределами прямоугольника запроса. Заштрихованная область на диаграмме относится к тому, что было бы доступно (последовательно), если бы такая оптимизация (исключая поддиапазоны) не применялась.
После обсуждения основной стратегии оптимизации для линейных последовательных структур данных мы поговорим о других структурах данных с лучшими возможностями поиска.