Рубрика «r-tree»

Про интервальные индексы - 1

Под катом будем разбираться нужен ли для индексации интервалов специальный индекс, как быть с многомерными интервалами, правда ли что с 2-мерным прямоугольником можно обращаться как с 4-мерной точкой и т.д. Всё это на примере PostgreSQL.
Читать полностью »

Проекции? Hет, спасибо - 1

Под катом будет небольшая заметка о применении пространственного индекса
на основе zcurve для индексации точечных данных, расположенных на сфере.
А так же bencmark-и для PostgreSQL и сравнение с таким же (но совсем другим)
индексом на R-дереве.
Читать полностью »

Z-order vs R-tree, оптимизация и 3D - 1

Ранее (1, 2) мы обосновали и продемонстрировали возможность существования
пространственного индекса, обладающего всеми плюсами обычного B-Tree — индекса и
не уступающего по производительности индексу на основе R-Tree.
Под катом обобщение алгоритма на трёхмерное пространство, оптимизации и бенчмарки.
Читать полностью »

Z-order vs R-tree, продолжение - 1

В прошлый раз мы пришли к выводу, что для эффективной работы пространственного индекса на основе Z-order необходимо сделать 2 вещи:

  • эффективный алгоритм получения подинтервалов
  • низкоуровневую работу с B-деревом

Вот именно этим мы и займёмся под катом.
Читать полностью »

image
Индекс на основе Z-order кривой в сравнении с R-деревом имеет массу преимуществ, он:

  • реализован как обычное B-дерево, а мы знаем что
  • страницы B-дерева имеют лучшую заполняемость, кроме того,
  • Z-ключи сами по себе более компактны
  • B-дерево имеет естественный порядок обхода, в отличие от R-дерева
  • B-дерево быстрее строится
  • B-дерево лучше сбалансировано
  • B-дерево понятнее, не зависит от эвристики расщепления/слияния страниц
  • B-дерево не деградирует при постоянных изменениях
  • ...

Впрочем, у индексов на основе Z-order есть и недостаток — сравнительно низкая производительность :). Под катом мы попробуем разобраться с чем связан этот недостаток и можно ли что-то с этим сделать.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js