Под катом будем разбираться нужен ли для индексации интервалов специальный индекс, как быть с многомерными интервалами, правда ли что с 2-мерным прямоугольником можно обращаться как с 4-мерной точкой и т.д. Всё это на примере PostgreSQL.
Читать полностью »
Рубрика «r-tree»
Про интервальные индексы
2017-10-02 в 4:05, admin, рубрики: C, open source, postgresql, r-tree, rdbms, spatial index, zorder, Алгоритмы, СУБДПроекции? Hет, спасибо
2017-09-18 в 4:02, admin, рубрики: C, open source, postgresql, r-tree, spatial index, SPI, zorder, Алгоритмы, Геоинформационные сервисы, СУБД
Под катом будет небольшая заметка о применении пространственного индекса
на основе zcurve для индексации точечных данных, расположенных на сфере.
А так же bencmark-и для PostgreSQL и сравнение с таким же (но совсем другим)
индексом на R-дереве.
Читать полностью »
Z-order vs R-tree, оптимизация и 3D
2017-03-06 в 3:19, admin, рубрики: C, postgresql, r-tree, spatial index, SPI, zorder, Алгоритмы, Геоинформационные сервисы, СУБД
Ранее (1, 2) мы обосновали и продемонстрировали возможность существования
пространственного индекса, обладающего всеми плюсами обычного B-Tree — индекса и
не уступающего по производительности индексу на основе R-Tree.
Под катом обобщение алгоритма на трёхмерное пространство, оптимизации и бенчмарки.
Читать полностью »
Z-order vs R-tree, продолжение
2017-01-18 в 4:40, admin, рубрики: C, postgresql, r-tree, spatial index, SPI, zorder, Алгоритмы, Геоинформационные сервисы, СУБДВ прошлый раз мы пришли к выводу, что для эффективной работы пространственного индекса на основе Z-order необходимо сделать 2 вещи:
- эффективный алгоритм получения подинтервалов
- низкоуровневую работу с B-деревом
Вот именно этим мы и займёмся под катом.
Читать полностью »
Про Z-оrder и R-дерево
2017-01-09 в 5:05, admin, рубрики: C, postgresql, r-tree, spatial index, SPI, zorder, Алгоритмы, Геоинформационные сервисы
Индекс на основе Z-order кривой в сравнении с R-деревом имеет массу преимуществ, он:
- реализован как обычное B-дерево, а мы знаем что
- страницы B-дерева имеют лучшую заполняемость, кроме того,
- Z-ключи сами по себе более компактны
- B-дерево имеет естественный порядок обхода, в отличие от R-дерева
- B-дерево быстрее строится
- B-дерево лучше сбалансировано
- B-дерево понятнее, не зависит от эвристики расщепления/слияния страниц
- B-дерево не деградирует при постоянных изменениях
- ...
Впрочем, у индексов на основе Z-order есть и недостаток — сравнительно низкая производительность :). Под катом мы попробуем разобраться с чем связан этот недостаток и можно ли что-то с этим сделать.
Читать полностью »