Дерева nested sets в MySQL (Вкладені множини)

Кожному програмісту рано чи пізно доводиться зіткнутися із вкладеним безліччю (відомим як дерево чи ієрархія) у реляційних базах даних. У цій замітці я опишу окремий випадок роботи з таким безліччю - модель Nested Sets (далі просто Nested Sets).

Nested Sets (Вкладені множини) передбачає присвоєння кожному вузлу в дереві двох додаткових ключів left key та right key. Для заповнення цих ключів нам доведеться повністю обійти дерево двічі відвідуючи кожен з вузлів. В результаті вибірка з дерева відбуватиметься досить швидко. З іншого боку зміна структури вимагає перерахунку всіх ключів у вузлах наступних за вузлом, що змінюється.

У базах, які не підтримують рекурсивні запити (наприклад, MySQL) вибірка з дерева відбувається швидше, ніж якби вона робилася за допомогою процедури, що зберігається.

Зміни в базі займають багато часу, тому що доводиться оновлювати всі ліві та праві ключі в записах, що йдуть після зміни.

На схемі представлений простий приклад Nested sets:

Які вибірки можна зробити?

• Всі вузли дерева SELECT * FROM tree ORDER BY left_key
• Вибір дочірніх вузлів SELECT * FROM tree WHERE left_key >= $left_key AND right_key = $right_key ORDER BY left_key
• Вибір гілки, в якій бере участь вузол SELECT * FROM tree WHERE right_key > $left_key AND left_key

Конкретні приклади

На роботі переді мною постало завдання завантажити в MySQL базу класифікатор ОКДП який містить понад 44 тисячі позицій і обов'язковою умовою було використання моделі Nested sets. Класифікатор поширюється як архів, який містить близько 15 файлів у форматі XML.

Стало ясно, що набагато ефективніше буде простозавантажити класифікатор у базу, а вже потім будувати ліві та праві ключі. Для цього була написана наступна процедура, яка відпрацювала у мене хвилин за 15:

---