Сайт вебмастера

Как организовать древовидные рубрики на сайте (Adjacency List)

25-11-2021Время чтения ~ 6 мин.Albireo Framework / CMS, SQL 2962

Рубрики — являются неотъемлемой частью любого сайта, но вместе с тем их реализация не такая простая, как может показаться. Сложность в том, что рубрики представляют собой древовидную структуру данных, а значит перед разработчиком стоят как минимум две задачи. Первая — придумать способ задания иерархии в базе данных и вторая — дать возможность владельцу сайта управлять этой иерархией.

На практике, управление структурой рубрикам происходит через админ-панель или какую-то другую конфигурацию, где для каждой рубрики нужно указать её место в общем дереве.

Для работы с древовидной структурой было придумано несколько алгоритмов. Наиболее распространённый — это метод Adjacency List («Список смежных вершин»), где у рубрики достаточно указать родителя, а дальше вся структура автоматически рассчитывается и выводится на сайте. Другой возможный способ, хотя я его не встречал в CMS, — это Materialized Path («Материализованный путь»), где каждая рубрика хранит полный путь к корневому элементу. Есть и другие способы, но они достаточно сложны для использования на сайтах.

В этой статье я расскажу о практической реализации Adjacency List, а о Materialized Path в следующей.

Не важно как именно организовано хранение рубрик в базе, важно, чтобы у конечного пользователя была возможность ими управлять. В методе Adjacency List для задания структуры используется поле parent_id, которое хранит номер родителя. У корневого элемента (самая верхняя рубрика) нет родителя, а значит parent_id равен NULL или 0.

Таким образом можно на основе только одного поля получить всю структуру рубрик. Вначале получается верхний уровень, после этого в цикле получаются потомки каждого. Если потомки имеют свои дочерние элементы, то запускается новый цикл и т.д. до тех пор, пока всё дерево не будет построено. Делается это с помощью рекурсии, когда в рекурсивной функции выполняются sql-запросы, чтобы получить потомков.

Понятно, что такой подход требует достаточных ресурсов: чем больше рубрик и их «ветвистость», тем больше создаётся sql-запросов. Но именно такой подход наиболее распространён в современных CMS. Проблему большого количества sql-запросов решают с помощью кэширования, что позволяет сайтам нормально работать.

Как оказалось, многие СУБД поддерживают рекурсивные запросы. То есть вместо того, чтобы выполнять цикл на PHP, мы можем создать рекурсивный sql-запрос и тем самым сразу получить необходимые данные для вывода. Такая возможность есть в SQLite и я решил написать свой вариант для работы с рубриками.

Что касается MySQL, то рекурсивные запросы в ней появились только в 8-й версии.

Для начала я покажу условие задачи — структуру, которую мы хотим получить в итоге.

Хотя я рассказываю о рубриках, на самом деле, это всё прекрасно будет работать с любыми другими таблицами и данными. Например точно также можно организовать иерархию меню или связать записи.

Внимательно посмотрите на эту схему. Заметьте, что узел «A» имеет «естественную» сортировку, а в узлах «B» и «C» она нарушена. Например «c22» и «c21» будут иметь одного родителя, но при этом «c22» должен иметь более высокий приоритет при выводе. Сделать это только одним полем parent_id будет невозможно, поэтому вводят ещё одно дополнительное поле, где указывается порядок в пределах своего уровня. Поле может быть, например menu_order с числовым типом (числа проще сортировать).

Таким образом каждая рубрика будет иметь эти два поля и с их помощью можно выстроить всю необходимую иерархию.

Пусть у нас будет такая таблица:

CREATE TABLE IF NOT EXISTS cat (
   id INTEGER PRIMARY KEY NOT NULL,
   name TEXT NOT NULL,
   parent_id INTEGER DEFAULT 0,
   slug TEXT NOT NULL DEFAULT '',
   menu_order INTEGER NOT NULL DEFAULT 0
);

Поле name будет хранить имя рубрики, а поле slug какие-то дополнительные данные, например ссылку.

Поле id я специально не отметил как автоинкрементное для того, чтобы в своих демо-примерах корректно указать номера рубрик и их родителей.

Теперь наполним таблицу данными. Я сразу приведу код для Albireo Framework

Pdo\PdoQuery::insert($db,  'cat', 
	['id' => 1, 'name' => 'A', 'parent_id' => 0, 'slug' => 'cat/a', 'menu_order' => 20],
	['id' => 2, 'name' => 'B', 'parent_id' => 0, 'slug' => 'cat/b', 'menu_order' => 10],
	['id' => 3, 'name' => 'C', 'parent_id' => 0, 'slug' => 'cat/c', 'menu_order' => 30],
	
	['id' => 4, 'name' => 'a1', 'parent_id' => 1, 'slug' => 'cat/a1', 'menu_order' => 1],
	['id' => 5, 'name' => 'a2', 'parent_id' => 1, 'slug' => 'cat/a2', 'menu_order' => 2],
	['id' => 6, 'name' => 'a3', 'parent_id' => 1, 'slug' => 'cat/a3', 'menu_order' => 3],
	
	['id' => 7, 'name' => 'a11', 'parent_id' => 4, 'slug' => 'cat/a11', 'menu_order' => 1],
	['id' => 8, 'name' => 'a111', 'parent_id' => 7, 'slug' => 'cat/a111', 'menu_order' => 1],
	
	['id' => 9, 'name' => 'b1', 'parent_id' => 2, 'slug' => 'cat/b1', 'menu_order' => 20],
	['id' => 10, 'name' => 'b2', 'parent_id' => 2, 'slug' => 'cat/b2', 'menu_order' => 10],	
	
	['id' => 11, 'name' => 'c1', 'parent_id' => 3, 'slug' => 'cat/c1', 'menu_order' => 20],
	['id' => 12, 'name' => 'c2', 'parent_id' => 3, 'slug' => 'cat/c2', 'menu_order' => 10],
	
	['id' => 13, 'name' => 'c21', 'parent_id' => 12, 'slug' => 'cat/c21', 'menu_order' => 20],
	['id' => 14, 'name' => 'c22', 'parent_id' => 12, 'slug' => 'cat/c22', 'menu_order' => 10],
);

В результате получится такая структура:

$rows = Pdo\PdoQuery::fetchAll($db, 'SELECT * FROM cat ORDER BY parent_id, menu_order;');
 
echo Pdo\PdoQuery::outTableRows($rows);

Такой вывод достаточно далёк от того, что нам нужно, но мы уже можем получить самые верхние рубрики:

$rows = Pdo\PdoQuery::fetchAll($db, 'SELECT* FROM cat WHERE parent_id = 0 ORDER BY menu_order, id;');
 
echo Pdo\PdoQuery::outTableRows($rows);

Если станет задача получить каждую ветку, то первый запрос будет именно таким.

Теперь немного магии SQLite — рекурсивный запрос, который выполнит всю работу.

$rows = Pdo\PdoQuery::fetchAll($db, "
WITH r(id, parent_id, name, menu_order, rm, level, path, path_ids) AS (
   SELECT id, parent_id, name, menu_order, menu_order, 1, name, id
   FROM cat
   WHERE parent_id = 0
 
   UNION ALL
    
   SELECT e.id, e.parent_id, e.name, e.menu_order, r.rm, 
       level+1 as lvl, 
       r.path||' > '||e.name as path,
       r.path_ids||','||e.id as path_ids
   FROM cat as e
   JOIN r ON e.parent_id = r.id
   ORDER BY r.rm, e.menu_order, lvl DESC, e.id
)
SELECT r.id, r.name, r.path, r.path_ids, r.level, cat.slug
FROM r
LEFT JOIN cat ON cat.id = r.id;
");
 
echo Pdo\PdoQuery::outTableRows($rows);

Запрос формирует дополнительные поля:

path — похож на «хлебные крошки».
path_id — номера родительских элементов в «правильном» порядке.
level — уровень отступа слева.

Объяснять как работает такой запрос я здесь не буду. Если не понимаете, то воспринимайте, как «черный ящик». :-)

Как правило иерархия рубрик нам нужна для вывода на сайте в виде UL/LI-списка. Чтобы его сделать, можно использовать поле level. Либо, чтобы не заморачиваться с преобразованием, можно его сымитировать с помощью левого padding:

foreach($rows as $row) {
	echo '<div style="padding-left: ' . $row['level'] * 20 . 'px;">• ' . $row['name'] . '</div>';
}

Будет что-то вроде такого:

Вообще задача по формированию UL/LI списка не самая простая, поэтому здесь я её также опускаю. Важно то, что итоговая таблица содержит все данные для его формирования.

Ну и самое главное, что это всего лишь один sql-запрос, который не требует рекурсивных функций для PHP. Это в 100500 раз проще у удобней, чем всё то, что было до этого момента. :-)

Поле path в общем-то не особо востребовано, но я его сделал для визуальных целей — так проще воспринимать таблицу. А вот поле path_id может использоваться если нужно получить данные текущей ветки — фактически это готовое условие IN.

В запросе я специально добавил LEFT JOIN чтобы получить все остальные данные из таблицы. В нашем случае это поле slug. В других таблицах это могут быть другие данные и их можно добавить не редактируя рекурсивную часть запроса.

Какие здесь могут быть «подводные камни»?

В общем-то они определяются самим алгоритмом Adjacency List. Необходимо следить за тем, чтобы номер родителя в действительности существовал. Также не желательно, чтобы рубрика ссылалась на саму себя. То есть перед тем, как внести данные от пользователя, нужно их проверить на корректность. Возможна ситуация, когда неверные данные могут скрыть вывод рубрики из общего списка, поэтому нужен дополнительный «простой» запрос (первый пример).

В любом случае эти вопросы уже из немного другой плоскости.

ps

Небольшой бонус. Можно заметить, что вывод списка по сути есть синтаксис Markdown.

* B
  * b2
  * b1
* A
  * a1
    * a11
      * a111
  * a2
  * a3
* C
  * c2
    * c22
    * c21
  * c1

Можно заставить его выполнить преобразование в HTML тэги UL/LI вот таким простым кодом:

$md = '';
foreach($rows as $row) {
	$md .= str_repeat(' ', ($row['level']-1) * 2) . '* ' . $row['name'] . "\n";
}
 
require_once SYS_DIR . 'lib/md.php';
$mdList = md($md);
echo $mdList;

Парсер Markdown входит в комплект Albireo Framework, поэтому всё будет работать из коробки.

Как организовать древовидные рубрики на сайте (Adjacency List)

ps

Проекты

Ссылки