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

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














В последние два месяца лета в управлении хранилищ данных (Data Warehouse, DWH) Тинькофф Банка появилась новая тема для кухонных споров. 
Целостность данных легко нарушить. Бывает так, что в поле price попадает значение 0 из-за ошибки в коде приложения (периодически всплывают новости, как в том или ином инет-магазине продавали товары по 0 долларов). Или бывает, что удалили юзера из таблицы, но какие-то данные о нем остались в других таблицах, и эти данные вылезли в каком-то интерфейсе.
В 2008 году в списке рассылки pgsql-hackers началось