MySQL / [Из песочницы] Реализация иерархии — объединение Adjacency List и Materialized Path через one-to-many

в 12:12, , рубрики: mysql, php, иерархические структуры, иерархия, метки: , , ,

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

Adjacency List (AL) удобен:

  • самоподдерживаемостью целостности данных (ON DELETE CASCADE)
  • легкостью вставкипереноса веток (обновление затрагивает одно поле parent_id у одного элемента)
  • Легкостью получения детей на 1 уровень вложенности

Но главные неудобства возникают при выборках:

  • получение всех детей ветки (для меню с ограничением по уровню вложенности)
  • получение общего количество детей (информация по каталогу)
  • найти полный путь к элементу (хлебные крошки, создание URL).

Сложности в решении они не представляют, но заставляют либо хардкодить количество уровней, либо прибегать к рекурсии. По большому счету можно смириться, написать пару функций с некрасивым кодом и забыть про это всё. Но!
Подглядев в Materialized Path идею хранения полного пути, я не очень понял, а что мешает хранить её во внешней таблице со связью один к многим? Кто-то скажет, что мол "уже было", но есть одно существенное отличие: parent_id!
Итак. Таблица pages:

`id` int(10) unsigned NOT NULL AUTO_INCREMENT, `parent_id` int(10) unsigned DEFAULT NULL, `title` varchar(250) DEFAULT NULL,

Таблица pages_paths:

`item_id` int(10) unsigned DEFAULT NULL, `parent_id` int(10) unsigned DEFAULT NULL, `level` tinyint(3) unsigned DEFAULT '0', `order` tinyint(3) unsigned DEFAULT '0',

Прописываем зависимости:

ALTER TABLE `pages`  ADD CONSTRAINT `pages_ibfk_1` FOREIGN KEY (`parent_id`) REFERENCES `pages` (`id`) ON DELETE CASCADE; ALTER TABLE `pages_paths`   ADD CONSTRAINT `pages_paths_ibfk_2` FOREIGN KEY (`parent_id`) REFERENCES `pages` (`id`) ON DELETE CASCADE,   ADD CONSTRAINT `pages_paths_ibfk_1` FOREIGN KEY (`item_id`) REFERENCES `pages` (`id`) ON DELETE CASCADE;

Таким образом можно «навесить» этот способ на уже существующую таблицу с AL и не вмешиваться в уже работающую логику приложения.
Операции вставки и изменения дерева выполняются как с обычным AL. При удалении основного элемента ветки, внешний ключ тащит за собой всю ветку и зависимости в таблице с путями.
Единственное вмешательство требуется на этапе добавления новых элементов и переносе элементов между ветками. Можно навесить триггер, но для большей совместимости с популярными хостингами я решил ограничиться простым PHP и дергать обновлятыр из скрипта.
Я тестировал всё на таблице с 1000 записей и 5 уровнями вложенности. Чтобы не мучиться руками, написал простую забивалку таблицы:

Tree::Fixture( 'pages', 1000, 5 );

Для начала работы нужно инициализировать пути для существующей таблицы:

Tree::GeneratePaths('pages'); 

Обработка этой таблицы на девелоперской машине заняла ~10 секунд. После этого из таблицы путей можно простыми запросами вытянуть путь к элементу:

SELECT *  FROM `pages_paths `  pp JOIN `pages` p ON `id`=p.`parent_id`  WHERE item_id=:id ORDER BY `order`

Собрать всех детей (или посчитать их количество без JOIN`a):

SELECT * FROM `pages_paths` pp JOIN `pages` p ON `id`=`item_id`  WHERE pp.`parent_id`=:id ORDER BY pp.`level`, pp.`order`

Если мы добавляем элемент, нужно просто обновить пути, если перемещаем, то сначала грохаем старую ветку путей (item_id=:id OR parent_id=:id) и в новой обновляем пути:

Tree::GeneratePaths( 'pages', $id );

Обновления в пределах ветки в 100-200 элементов укладываются до 1 секунды, что для моих задач вполне приемлемо — задержку будет видеть только админ.
Взглянуть целиком на Класс PHP и Базовый SQL.
В завершение примеры использования (или целиком):

//Путь к элементу $arr = Tree::GetPath( 'pages', $id );  //Получение всех детей $arr = Tree::GetChildren( 'pages', $id );  //Количество детей $num = Tree::GetChildrenCount( 'pages', $id );

Буду рад, если кто-то сможет предложить как оптимизировать время выполнения общей индексации, реализацию в виде процедуры MySQL или другие умные мысли.

Автор: azverin


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js