Как стать автором
Обновить

Комментарии 9

А можно бенчмарк для 32-битных ключей. В принципе 16 бит на координату — достаточно, особенно если использовать Z именно как индекс.
Во всяком случае не прямо сейчас.
Думаю, что на малых запросах ничего не изменится т.к. читаются единичные страницы.
Разница за счет более плотной упаковки (если она вообще будет) возникнет только когда число точек в запросе заметно превысит число точек на странице.
16 бит — на 1000 км — разрешающая способность 15 метров
маловато будет, хотя, смотря для каких целей
16 метров же?
А обычный 32-ти битный Z код описывает квадрат по стороной 300 метров если его применять «world-wide». Достаточно для фильтрации большинства данных.
прямоугольник 600Х300, для блочного индекса более чем
Как пространственный индекс R-Tree хорош, есть еще различные его модификации под частные случаи. Но если взять задачу определения присутствия объектов в области, то Z-Index будет быстрее, сложность O(1) по операциям сравнения.
Много лет назад делал растеризатор на собственных векторных картах, испоьзование Z-Index для отсечения пустых областей дало отличный прирост. При этом не важно было какой масштаб, все делалось на битовых операциях в памяти.

Была задача реализовать собственную СУБД с индексированием и прочими плюшками. Долго выбирал между различными реализациями пространственных индексов, в итоге остановился на R*Tree (брал реализацию из https://libspatialindex.github.io/). Судя по статьям по данной теме R*Tree однозначно выигрывает перед стандартным R-Tree

Самое время сказать в чем выигрывает, в каких условиях и привести ссылки

Вообще была отличная статья в pdf, но ее сходу найти не смог. Сходу нашел только описание в https://en.wikipedia.org/wiki/R*_tree. Вкратце индекс получается более компактным за счет снижения количества пересечений узлов дерева. Изначально в моей задаче был сильный перекос на чтение и при активном чтении R*Tree однозначно побеждало R-Tree. Возможно при большом количестве вставок и обновлений ситуация будет немного иная

Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории