Хранение иерархии в 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