Как стать автором
Обновить

Реализация иерархии — объединение Adjacency List и Materialized Path через one-to-many

Время на прочтение 3 мин
Количество просмотров 20K
Хранение иерархии в 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 p.`id`=pp.`parent_id` 
WHERE item_id=:id ORDER BY `order`

Собрать всех детей (или посчитать их количество без JOIN`a):
SELECT * FROM `pages_paths` pp JOIN `pages` p ON p.`id`=pp.`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 или другие умные мысли.
Теги:
Хабы:
+15
Комментарии 26
Комментарии Комментарии 26

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн
PG Bootcamp 2024
Дата 16 апреля
Время 09:30 – 21:00
Место
Минск Онлайн
EvaConf 2024
Дата 16 апреля
Время 11:00 – 16:00
Место
Москва Онлайн