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

26-11-2021Время чтения ~ 4 мин.Albireo Framework / CMS, SQL 3082

Теперь рассмотрим другой вариант организации «деревьев» — алгоритм Materialized Path. В отличие от других методов, здесь рубрика хранит сразу весь путь в иерархии. Но основная фишка в том, что выстроить данные в таблице можно единственным примитивным sql-запросом с ORDER BY.

Лично мне этот вариант особенно нравится за свою «идеальную свободу». С точки зрения теории всяких сложных структур это может и не так, но с практической точки зрения, он удобный и не требует сложного кода.

Я также буду показывать на предыдущей схеме данных.

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

Pdo\PdoQuery::query($db, "
CREATE TABLE IF NOT EXISTS cat2 (
   id INTEGER PRIMARY KEY,
   name TEXT NOT NULL,
   path TEXT NOT NULL DEFAULT '',
   slug TEXT NOT NULL DEFAULT ''
);
");

Обратите внимание, что теперь используется текстовое поле path, которое и будет хранить местоположение каждой рубрики.

Примеры я даю для Albireo Framework.

Добавим данные:

Pdo\PdoQuery::insert($db,  'cat2', 
	['name' => 'B', 'path' => '10', 'slug' => 'cat/b'],
		['name' => 'b2', 'path' => '10.1', 'slug' => 'cat/b2'],
		['name' => 'b1', 'path' => '10.2', 'slug' => 'cat/b1'],
		
	['name' => 'A', 'path' => '20', 'slug' => 'cat/a'],
		['name' => 'a1', 'path' => '20.1', 'slug' => 'cat/a1'],
			['name' => 'a11', 'path' => '20.1.1', 'slug' => 'cat/a11'],
				['name' => 'a111', 'path' => '20.1.2', 'slug' => 'cat/a111'],
	
		['name' => 'a2', 'path' => '20.2', 'slug' => 'cat/a2'],
		['name' => 'a3', 'path' => '20.3', 'slug' => 'cat/a3'],
		
	['name' => 'C', 'path' => '30', 'slug' => 'cat/c'],
		['name' => 'c2', 'path' => '30.1', 'slug' => 'cat/c2'],
			['name' => 'c22', 'path' => '30.1.1', 'slug' => 'cat/c22'],
			['name' => 'c21', 'path' => '30.1.2', 'slug' => 'cat/c21'],
			
		['name' => 'c1', 'path' => '30.2', 'slug' => 'cat/c1'],
);

Прежде чем двигаться дальше, потратьте немного времени и посмотрите как формируется поле path. Оно состоит как бы из сегментов, разделёнными точкой. Первый сегмент всегда указывает на самого верхнего родителя (произвольное число). Дальше число, которое указывает порядок рубрики на этом уровне иерархии. Следующий сегмент также указывает на порядок сортировки.

То есть нам не нужно следить за id рубрик — для иерархии достаточно знать только path своего родителя. Потом ставим точку и номер для сортировки (не обязательно по порядку).

Теперь мы можем вывести все рубрики скопом:

$rows = Pdo\PdoQuery::fetchAll($db, 'SELECT * FROM cat2 ORDER BY path, id;');
 
echo Pdo\PdoQuery::outTableRows($rows);

Обратите внимание, что мы сразу получили правильную сортировку всех рубрик. По сути это уже готовая для вывода таблица за исключением того, что в ней нет поля level. Это поле, как вы помните, используется для формирования UL/LI списка.

Но как это сделать?

На самом деле, всё намного проще. Если внимательно присмотреться к path, то становится понятно, что разделительный символ (секций) — точка — это и есть искомый level. То есть достаточно посчитать количество вхождений символа «.». В SQLite нет готовой функции, поэтому используем хитрость с LENGTH и REPLACE. Вот так можно вывести все рубрики:

$rows = Pdo\PdoQuery::fetchAll($db, "
SELECT *, LENGTH(path) - LENGTH(REPLACE(path, '.', '')) + 1 AS level
FROM cat2 
ORDER BY path;
");
 
echo Pdo\PdoQuery::outTableRows($rows);

Получив значение level мы уже можем сформировать UL/LI список, как я это показал в прошлый раз.

Если же стоит вывести только самые верхние рубрики, то используем level = 1

$rows = Pdo\PdoQuery::fetchAll($db, "
SELECT *, LENGTH(path) - LENGTH(REPLACE(path, '.', '')) + 1 AS level
FROM cat2 
WHERE level = 1
ORDER BY path;
");
 
echo Pdo\PdoQuery::outTableRows($rows); 

А если нужно вывести ветку одной рубрики, то используется более сложный запрос:

$rows = Pdo\PdoQuery::fetchAll($db, "
SELECT t2.*, LENGTH(t2.path) - LENGTH(REPLACE(t2.path, '.', '')) + 1 AS level
FROM cat2 t1
JOIN cat2 t2 ON t2.path LIKE t1.path||'%' -- или '.%' если не нужно включать родителя
WHERE t1.id = 4
ORDER BY t2.path;
");
 
echo Pdo\PdoQuery::outTableRows($rows);

Здесь мы выводим рубрику id=4. Для того, чтобы найти «правильный» path для подрубрик используется поиск LIKE.

Какие плюсы и минусы Materialized Path?

Минус в том, что поле path необходимо формировать в заданных правилах. Поскольку на это поле и завязана вся сортировка, то если ошибиться, можно получить неверную структуру итогового списка. Но зато это может быть и плюсом, поскольку позволяет на практике дать пользователю полную свободу по созданию совершенно произвольной структуры рубрик. Максимум, что может случиться, это просто неверное расположение рубрики в списке. Это легко исправляется и не создаёт проблем.

Ещё есть нюанс, связанный с особенностью сортировки строк в программах. Программисты это и так знают. :-)

Например есть числа «1, 2, 3, 10». После сортировки мы получим «1, 10, 2, 3». Так работает обычная сортировка строк в любой программе. Чтобы получить более привычную используют натуральную сортировку, но она к сожалению, не поддерживается в SQLite. Поэтому, чтобы обойти это ограничение, начинать нумерацию нужно с 10. Тогда до 99 рубрик всё будет работать корректно. Если на сайте ещё больше рубрик, то можно начинать нумерацию со 100 или 1000.

Ещё, как вариант, можно добавлять ведущие нули: 001, 002, 024, 099, 139 и т.д. Это делается для того, чтобы уравнять количество символов в пределах своего уровня иерархии.

Теперь плюсы.

Очень лёгкая реализация: простые sql-запросы и никаких рекурсивных функций.

И ещё один плюс, который я нашёл для себя. В поле path для родителей совершенно не обязательно указывать число. Можно указать какой-то понятный текст. Например для потомков рубрики о новостях можно указывать «news» (в скобках path):

Новости          (news)
  По миру        (news.1)
  По стране      (news.2)
  Городские      (news.3)
  Сельские       (news.4)
  Уличные        (news.5)
  Лавочные       (news.6)
  Кухонные       (news.7)

То есть мы получаем очень хорошую семантику рубрик — сразу понятно кто её родитель и каков порядок в своей группе.

Лично я никогда не встречал использование Materialized Path в существующих CMS, но идея, согласитесь, очень привлекательная. :-)