DOC.PROTOTYPES.RU

Правила деревьев 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% гарантии, но определит большее количество ошибок.