• Аудит
  • Консалтинг
  • Миграция
    • Миграция с Oracle на PostgreSQL
    • Миграция 1С на PostgreSQL
  • Поддержка
  • Статьи и инструкции
Меню
  • Аудит
  • Консалтинг
  • Миграция
    • Миграция с Oracle на PostgreSQL
    • Миграция 1С на PostgreSQL
  • Поддержка
  • Статьи и инструкции

Nested Sets. Правила

Прежде чем начинать работать с деревом, что бы линий раз не наступать на «грабли», определим основные правила:

  1. Левый ключ ВСЕГДА меньше правого (1);
  2. Наименьший левый ключ ВСЕГДА равен 1 (2);
  3. Наибольший правый ключ ВСЕГДА равен двойному числу узлов (2). Отсюда же правило, что разрывов последовательности ключей быть не может;
  4. Разница между правым и левым ключом ВСЕГДА нечетное число (3);
  5. Если уровень узла нечетное число то тогда левый ключ ВСЕГДА нечетное число, то же самое и для четных чисел (4);
  6. Ключи ВСЕГДА уникальны, вне зависимости от того правый он или левый (5). Но это правило, увы, не получится реализовать на уровне уникального индекса, т.к. в процессе перестроения дерева, в пределах транзакции данное правило не работает;

Можно определить проверочные запросы:

SELECT id
FROM my_tree
WHERE left_key >= right_key;

Если все правильно то результата работы запроса не будет, иначе, получаем список идентификаторов неправильных строк;

SELECT
    COUNT(id),
    MIN(left_key),
    MAX(right_key)
FROM
    my_tree;

Получаем количество записей (узлов), минимальный левый ключ и максимальный правый ключ, проверяем значения.

SELECT
    id,
    MOD( ( right_key - left_key ) / 2 ) AS ostatok
FROM
    my_tree
WHERE
    ostatok = 0;

Если все правильно то результата работы запроса не будет, иначе, получаем список идентификаторов неправильных строк;

SELECT
    id,
    MOD(( left_key - level + 2 ) / 2 ) AS ostatok
FROM
    my_tree
WHERE
    ostatok = 1;

Если все правильно то результата работы запроса не будет, иначе, получаем список идентификаторов неправильных строк;

SELECT
    t1.id,
    COUNT(t1.id) AS rep,
    MAX(t3.right_key) AS max_right
FROM
    my_tree AS t1,
    my_tree AS t2,
    my_tree AS t3
WHERE
    t1.left_key <> t2.left_key
  AND
    t1.left_key <> t2.right_key
  AND
    t1.right_key <> t2.left_key
  AND
    t1.right_key <> t2.right_key
GROUP BY
    t1.id
HAVING
    max_right <> SQRT( 4 * rep + 1 ) + 1;

Здесь, я думаю, потребуется некоторое пояснение запроса. Выборка по сути осуществляется из одной таблицы, но в разделе FROM эта таблица «виртуально» продублирована 3 раза: из первой мы выбираем все записи по порядку и начинаем сравнивать с записями второй таблицы (раздел WHERE) в результате мы получаем все записи неповторяющихся значений. Для того, что бы определить сколько раз запись не повторялась в таблице, производим группировку (раздел GROUP BY) и получаем число «не повторов» (COUNT(t1.id)). По условию, если все ключи уникальны, то число не повторов будет меньше на одну единицу чем общее количество записей. Для того, чтобы определить количество записей в таблице, берем максимальный правый ключ (MAX(t3.right_key)), так как его значение — двойное число записей, но так как в условии отбора для записи с максимальным правым ключом — максимальный правый ключ будет другим, вводится третья таблица, при этом число «неповторов» увеличивается умножением его на количество записей. SQRT(4*rep +1) — решение уравнения x^2 + x = rep. Если все правильно то результата работы запроса не будет, иначе, получаем список идентификаторов неправильных строк. Но сразу хочу оговориться, что данный запрос весьма ресурсоемкий, и при большом количестве узлов скорость его выполнения будет очень медленной а нагрузка на сервер — высокая, поэтому, я лично, данный запрос не использую, предпочитая несколько простых и обработку результатов в программе.

Хотя данные проверки не дают 100% гарантии, но определит большее количество ошибок.

Ссылке по теме:

  • https://postgres.men/database/postgresql/nested-sets-introdution/
  • https://postgres.men/database/trees/nested-sets-manage/
  • https://postgres.men/database/postgresql/nested-sets-postgresql-triggers/

Рубрики
  • Базы данных
    • PostgreSQL
    • Деревья
  • Без рубрики
  • Веб
    • Nginx
  • Операционные системы
    • Linux
Метки
ACL Adjacency List Contrib DevOps Extensions GRANT Linux ltree Materialized Path Nested Sets nginx ngx_http_dav_module ngx_http_image_filter_module ngx_http_map_module ngx_http_proxy_module ngx_http_random_index_module ngx_http_secure_link_module pg_hba.conf PostgreSQL privileges REVOKE Trees Ubuntu Web ZFS Деревья Индекс Миграция Оптимизация запросов триггеры

КОНСАЛТИНГ 
ПО POSTGRESQL

Консалтинг — 
это когда мы сами выполняем работу

ПОДРОБНЕЕ

ЕЩЕ СТАТЬИ ПО ДАННОЙ ТЕМЕ

PostgreSQL. Миграция. Как начать

Вот проснулись вы как-то утром и решили начать новую жизнь вместе с базой данных PostgreSQL оставив другие за бортом. Но с чего начать? Как «подкатить» и не быть отвергнутым? А ведь вы уже не молоды и «с прицепом»: с данными, нагрузкой и бизнес-логикой.
Так как в данный момент тема миграций в тренде, не могу пройти мимо и не поделится своим опытом подобных мероприятий. Данная задача не самая простая, так как требует подмены одной из фундаментальных технологий проекта — хранилище данных.

Читать далее »

PostgreSQL. Хочешь похудеть? Cпроси меня как.

Недавно попросили поднять копию одного проекта для тестов, ну и соответственно потянуть базу данных как есть из боя (pg_basebackup). Выяснилось, что физический размер базы составил 505 GB, что само по себе слегка удивило, не то, чтобы данных там было мало. Много, но не настолько.

Читать далее »

PostgreSQL ACL Object

В предыдущей статье мы рассматривали вопросы подключения и глобальных привилегий пользователей сервера PostgreSQL. Будем считать что головную боль админов в виде pg_hba.conf мы прошли, переходим к следующей.
DBA против Разработчиков, DML против DDL. Сразу хочу сказать, что мое мнение: привилегии DDL разработчику не нужны, несмотря на то, что я сам разработчик.

Читать далее »

Поддержка

Поддержка — это когда у нас возникает техническая
проблема с существующей системой,
и вам необходимо некоторое руководство

ПОДРОБНЕЕ

Postgres.men

  • Аудит
  • Консалтинг
  • Поддержка
  • Статьи и инструкции

Миграция

  • Миграция с Oracle на PostgreSQL
  • Миграция 1С на PostgreSQL

Мы в соцсетях

  • Вконтакте

© Postgres.Men by Taktive Ltd, 2022. Не является публичной офертой.