Pull to refresh

Про Z-оrder и R-дерево

PostgreSQL *Algorithms *C *Geoinformation services *
image

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

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

Впрочем, у индексов на основе Z-order есть и недостаток — сравнительно низкая производительность :). Под катом мы попробуем разобраться с чем связан этот недостаток и можно ли что-то с этим сделать.
Читать дальше →
Total votes 35: ↑34 and ↓1 +33
Views 13K
Comments 10

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

PostgreSQL *Algorithms *C *Geoinformation services *

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

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

Вот именно этим мы и займёмся под катом.
Читать дальше →
Total votes 26: ↑26 and ↓0 +26
Views 7.8K
Comments 9

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

PostgreSQL *Algorithms *C *Geoinformation services *

Ранее (1, 2) мы обосновали и продемонстрировали возможность существования
пространственного индекса, обладающего всеми плюсами обычного B-Tree — индекса и
не уступающего по производительности индексу на основе R-Tree.
Под катом обобщение алгоритма на трёхмерное пространство, оптимизации и бенчмарки.
Читать дальше →
Total votes 22: ↑21 and ↓1 +20
Views 6K
Comments 0

Z-order в 8D

Open source *PostgreSQL *Algorithms *C *

Индексы на основе самоподобных заметающих кривых пригодны не только для организации поиска пространственных данных. Они работоспособны и на разнородных данных, положенных на целочисленную решетку.

Под катом мы займёмся проверкой возможности применения Z-кривой для реализации 8-мерного индекса с прицелом на куб OLAP.
Читать дальше →
Total votes 15: ↑15 and ↓0 +15
Views 3.8K
Comments 0

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

Open source *PostgreSQL *Algorithms *C *Geoinformation services *

Под катом будет небольшая заметка о применении пространственного индекса
на основе zcurve для индексации точечных данных, расположенных на сфере. А так же bencmark-и для PostgreSQL и сравнение с таким же (но совсем другим)
индексом на R-дереве.
Читать дальше →
Total votes 15: ↑15 and ↓0 +15
Views 5.3K
Comments 2

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

Open source *PostgreSQL *Algorithms *C *


Под катом будем разбираться нужен ли для индексации интервалов специальный индекс, как быть с многомерными интервалами, правда ли что с 2-мерным прямоугольником можно обращаться как с 4-мерной точкой и т.д. Всё это на примере PostgreSQL.
Читать дальше →
Total votes 8: ↑8 and ↓0 +8
Views 4.9K
Comments 0

Кривая Гильберта vs Z-order

Open source *PostgreSQL *Algorithms *C *Geoinformation services *

Неоднократно доводилось слышать мнение, что из всех заметающих кривых. именно кривая Гильберта наиболее перспективна для пространственной индексации. Мотивируется это тем, что она не содержит разрывов и потому в некотором смысле “хорошо устроена”. Так ли это на самом деле и при чем здесь пространственная индексация, разберёмся под катом.
Читать дальше →
Total votes 30: ↑29 and ↓1 +28
Views 14K
Comments 20