Построение деревьев

Новости	FAQ	Авторы	Документация	В действии	Библиотека
Инструменты	Полезные ссылки	Хостинги	Скачать	Примеры	Форум

Построение деревьев
Misha v.3 [19 мая 2002]
DISCLAIMER.
Данная статейка — не набор примеров, которые вы скопируете и у вас все заработает, даже более того: в нее специально внесены некоторые синтаксические ошибки, чтобы простое копирование методов не дало работоспособный результат. Сделано это для того, чтобы люди, думали до, а не вместо. Если вы поймете то, что написано в данной статье, то для вас не будет совершенно никаких проблем написать подобный код в любой момент без какой-либо шпаргалки.
В этой статье так же намерено пропущены некоторые моменты не относящиеся к её основной теме: построение древовидных структур средствами парсера.
Вы не найдете тут упоминаний о том, как хранить данные в текстовых файлах, какими программами пользоваться для подключения к базе данных MySQL, как занести в базу данных сообщения и что означает синтаксис в запросах. Для ответов на эти вопросы отправляю вас к их документации.

Для того, чтобы больше понимать в этой статье рекомендуется ознакомиться со статьей о переносимости SQL запросов.

Хранить и строить древовидные структуры приходится достаточно часто, например при реализации форумов, структур сайта, хранящихся в базе, категорий/подкатегорий товаров и т.д.

Я не буду рассматривать реализацию, когда древовидные структуры, хранящиеся в базе данных, достаются в требуемом виде средствами SQL серверов, т.к. далеко не всякие сервера баз данных умеют делать это. В частности наиболее популярный из-за того, что он бесплатный, MySQL не умеет делать этого.

В данном примере построение древовидных структур будет показано на примере простенького форума, где в качестве сервера баз данных используется MySQL, а в качестве серверного языка сценариев — Parser 3.

Для начала необходимо определиться, каким образом сообщения форума будут храниться в базе данных.

Для этого создадим в БД простую таблицу и несколько индексов
CREATE TABLE forum_message (
	forum_message_id INTEGER UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
	forum_id MEDIUMINT UNSIGNED NOT NULL DEFAULT 1,
	parent_id INTEGER UNSIGNED NOT NULL DEFAULT 0,
	thread_id INTEGER UNSIGNED NOT NULL DEFAULT 0,
	is_published TINYINT(1) UNSIGNED NOT NULL DEFAULT 1,
	dt_published DATETIME NOT NULL,
	author VARCHAR(255) NOT NULL,
	email VARCHAR(255),
	title VARCHAR(255) NOT NULL,
	body TEXT
);
CREATE INDEX ix_forum_message_0 ON forum_message (
	parent_id,
	is_published,
	dt_published
);

CREATE INDEX ix_forum_message_1 ON forum_message (
	thread_id,
	is_published,
	dt_published
);
Собственно в ней и будут лежать все сообщения форума.
forum_message_id — уникальный идентификатор сообщения.
forum_id — введено для того, чтобы можно было хранить в одной табличке сообщения нескольких форумов. Пока будем сюда писfть просто 1. (если захотите — расширите пример, и в этом поле будет ссылка на запись таблица forum)
parent_id — ссылка на идентификатор родительского сообщения. Для корневых сообщений — 0
thread_id — идентификатор треда. Фактически сюда записывается forum_message_id корневого сообщения для всех сообщений данного треда. Это поле — избыточно, оно необходимо лишь для упрощения выборок наборов данных по заданным кретериям.
is_published — признак того, что сообщение нужно показывать на сайте. например, удаление сообщения может всего лишь сбрасывать этот флажок в 0.
dt_published — дата/время публикации сообщения (поле имеет индекс для ускорения сортировок)
author — имя того, кто записал сообщение
email — e-mail автора сообщения
title — заголовок сообщения. Обязательное поле, поэтому оно объявлено NOT NULL
body - текст сообщения

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

1. метод, который достает все данные определенного сообщения. Его использование не показано в данном тексте, но он потребуется вам, если вы будете продолжать писать форум для вывода информации об определенном сообщении.
@getMessageById[iMessageId]
$result[^table::sql{
	SELECT
		forum_message_id AS id,
		parent_id,
		thread_id,
		title,
		author,
		email,
		dt_published,
		body
	FROM
		forum_message
	WHERE
		forum_message_id = ^iMessageId.int(0)
		AND is_published = 1
}]
#end @getMessageById[]
2. метод, который достает данные о всех сообщениях заданного родителя
@getMessagesByParent[iParentId;iLimit]
$result[^table::sql{
	SELECT
		forum_message_id AS id,
		parent_id,
		thread_id,
		title,
		author,
		email,
		dt_published,
		IF(body IS NULL, 1, 0) AS is_empty
	FROM
		forum_message
	WHERE
		is_published = 1
		^if(def $iParentId){
			AND parent_id = ^iParentId.int(0)
		}
	ORDER BY
		dt_published
}[
	^if(^iLimit.int(0)){
		$.limit(^iLimit.int(0))
	}
]]
#end @getMessagesByParent[]
3. метод, который достает данные о заголовках тредов для заданного треда или списка тредов
@getMessagesByThread[uThreadIds]
$result[^table::sql{
	SELECT
		forum_message_id AS id,
		parent_id,
		thread_id,
		title,
		author,
		email,
		dt_published,
		IF(body IS NULL, 1, 0) AS is_empty
	FROM
		forum_message
	WHERE
		is_published = 1
		^if($uThreadIds is "table"){
			^if($uThreadIds){
				AND thread_id IN (^uThreadIds.menu{$uThreadIds.thread_id}[,])
			}
		}{
			AND thread_id = ^uThreadIds.int(0)
		}
	ORDER BY
		dt_published DESC
}]
#end @getMessagesByThread[]
4. метод построения древовидной структуры, рекурсивно вызывающий себя (ниже читайте почему этот метод плох и как его улучшить)
@printMessagesByParent[tMessage;iParentId][tLevel]
$tLevel[^tMessage.select($tMessage.parent_id == $iParentId)]
^tLevel.menu{
	^printTreeItem[$tLevel.fields;^printMessagesByParent[$tMessage;$tLevel.id]]
}
#end @printMessagesByParent[]
5. метод выводы одного элемента древовидной структуры
@printTreeItem[hMessage;sBody]
<tree-item
	id="$hMessage.id"
	date="$hMessage.dt_published"
	is-empty="$hMessage.is_empty"
>
	<title>$hMessage.title</title>
	<author>$hMessage.author</author>
	<email>$hMessage.email</email>
	$sBody
</tree-item>
#end @printTreeItem[]
Наверняка вы обратили внимание на использование мной непонятных тегов:
<tree-item />
<title />
<author />
и т.д.

Вы извините, я щас ругнусь: это XML :)

Моя задача сейчас — сделать древовидную структуру элементов. Мне совершенно безразлично, что это за элементы — дерево форума, структура каталогов сайта или еще что-либо. Мне совершенно безразлично, сколько и каких параметров будет у элемента этой структуры. Я логически организую данные.

Например, если я завтра решу добавить дополнительный параметр «ссылка на сообщение» я немного изменю запись:
<tree-item
	href="./?id=$tLevel.forum_id"
	id="$tLevel.id"
	date="$tLevel.dt_published"
	is-empty="$tLevel.is_empty"
>
И человек, который делает так, чтобы данная древовидная структура отображалась, просто выведет этот элемент как ссылку и все. А если послезавтра я приделаю к форуму mod_rewrite и мне нужно будет изменить href я всего лишь поменяю содержимое href="./${tLevel.id}.html"

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

Ну это было лирическое отступление, в нашем случае вам наверное проще будет пока заменить содержимое ^printTreeItem[] на следующее:
@printTreeItem[hMessage;sBody]
$result[<li>$hMessage.title ^if($hMessage.is_empty){(-)},
	$hMessage.author [$hMessage.dt_published]
	^if(def $sBody){<ul>$sBody</ul>}
</li>]
#end @printTreeItem[]
Собственно после написания этих методов, для реализации простенького форума нужно совсем немного:
@main[]
^pSQL.server{
	^rem{ *** достаем не более 20 корневых сообщений (parent_id == 0) *** }
	$tRootMessage[^getMessagesByParent[0;20]]

	^rem{ *** достаем все сообщения в тредах, которые мы только что достали *** }
	$tMessage[^getMessagesByThread[$tRootMessage]]

	^rem{ *** выводим все данные о сообщениях в виде дерева *** }
	^printMessagesByParent[$tMessage;0]
}
#end @main[]
Собственно всё. И кто говорил, что форум — это сложно? :)

Если вы внимательно разбирали код метода printMessagesByParent то у вас мог возникнуть закономерный вопрос:
«А на фига таскать за собой таблицу $tMessage? Ведь можно работать с ней как с глобальной?»

Да, несомненно, можно. Но... Во-первых интересна следующая модификация строки метода (но она полезна только при переходе от корневого элемента к первому, далее она бессмыслена):
^printTreeItem[$tLevel.fields;^printMessagesByParent[^tMessage.select($tLevel.thread_id == $tMessage.thread_id);$tLevel.id]]
(разберитесь зачем это надо и что оно делает), а во вторых это практически не расходует память в parser3 т.к. данные передаются по ссылке… И при этом у нас остаются возможности вводить дополнительные механизмы фильтрации.

Однако эпопея с деревьями на этом не заканчивается.

Приведенный пример рекурсивного обхода совсем не хорош.
В данном случае он удобен, но если бы нам потребовалось выполнять проверки: есть ли у нас элемент с заданным id нам пришлось бы делать кучу ^locate[], что не есть быстро.

В этом случае лучше сделать так:
1. как и в первом случае достаем все элементы дерева (или интересующую нас его часть)
2. делаем хеш таблиц ($hTree), где ключом является id элемента, а содержимым — таблица с его дочерними элементами.

В этом методе мы один раз пробегаем по всем сообщениям и для каждого из них проверяем: есть ли у нас уже в хеше элемент с ключом, равным parent_id текущего элемента? Если нет, то создаем этот элемент в хеше, а после этого добавляем этот элемент к таблице детей созданного объекта.
@createHashTree[tMessage][tEmpty]
$tEmpty[^table::create[$tMessage][$.limit(0)]]
$result[^hash::create[]]
^tMessage.menu{
	^if(!$result.[$tMessage.parent_id]){
		$result.[$tMessage.parent_id][^table::create[$tEmpty]]
	}
	^result.[$tMessage.parent_id].join[$tMessage][$.limit(1)$.offset[cur]]
}
#end @createHashTree[]
3. на любой итерации рекурсивного обхода мы можем точно так же достать детей и вывести их. Выглядеть это будет так:
@printMessagesByParent[hTree;iParentId][tLevel]
^if($hTree.[$iParentId]){
	^hTree.[$iParentId].menu{
		^printTreeItem[$hTree.[$iParentId].fields;^if($hTree.[$hTree.[$iParentId].id]){^printMessagesByParent[$hTree;$hTree.[$iParentId].id]}]
	}
}
#end @printMessagesByParent[]
Хотя этот метод выглядит сложнее, его использование себя оправдывает. Он почти в 3 раза быстрее чем метод с select-ами и расходует в 1.5-2 раза меньше памяти.

Если вы, посмотрев на метод @createHashTree[] испугались, то сделали это зря, т.к. начиная с версии parser 3.0.8 писать его таким образом совершенно не нужно, т.к. появился внутренний метод для создания подобного хеша таблиц, и @createHashTree[] будет выглядеть так:
@createHashTree[tMessage]
$result[^tMessage.hash[parent_id][$.distinct[tables]]]
#end @createHashTree[]
И ещё… Если вы используете lib.p то там данный метод уже есть, при этом он использует возможности новых версий парсера.

Обратите внимание, т.к. в этом варианте легко (и быстро) делать проверки наличия элементов с заданным parent_id (^if($hTree.[$iParentId]){есть дети у элемента с id равным $iParentId}{нету детей}, то можно не входить рекурсивно в элементы, у которых нету дочерних элементов. В предыдущем примере это можно было бы сделать конструкцией
^if(^tMessage.locate[parent_id;$iParentId]{есть дети у элемента с id = $iParentId}{нету детей}) но делать этого не стОит, т.к. при большом количестве элементов в таблице $tMessage подобные locate происходят медленно.
@main[]
^pSQL.server{
	^rem{ *** достаем не более 20 корневых сообщений (parent_id == 0) *** }
	$tRootMessage[^getMessagesByParent[0;20]]
	
	^rem{ *** достаем все сообщения в тредах, которые мы только что достали *** }
	$tMessage[^getMessagesByThread[$tRootMessage]]
	
	^rem{ *** создаем хеш, в котором ключи &mdash; id элемента, содержание &mdash; таблица со всеми их дочерними элементами *** }
	$hTree[^createHashTree[$tMessage]]

	^rem{ *** выводим все его элементы в виде дерева *** }
	^printMessagesByParent[$hTree;0]
}
#end @main[]
Общие замечания по рекурсии и приведенным здесь методам:
1. рекурсия — далеко не самый эффективный алгоритм. Используя его не злоупотребляйте созданием локальных переменных, т.к. это безвозвратно теряет память и при построении больших деревьев вам её не хватит (говорю о parser3).
2. методы, приводимые здесь в качестве примеров не самые эффективные, к тому-же для простоты я не включал в них некоторые полезные «фичи». Бывают случаи, когда надо менять логику работы.
3. я не рассматривал механизмы форматирования дат, а также анализа: сегодняшним ли числом датируется сообщение или нет.

Для этих целей лучше использовать средства SQL, например так:
$result[^table::sql{
	SELECT
		forum_message_id AS id,
		&hellip;
		email,
		^pSQL.date_format[dt_published;%d.%m %H:%i] AS dt_published,
		IF(dt_published >= ^pSQL.today[], 1, 0) AS is_new
		&hellip;
	FROM
		forum_message
	WHERE
		&hellip;
	ORDER BY
		dt_published DESC
}]
Я пытался получать от SQL сервера дату в чистом виде и форматировать ее средствами парсера…

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

Это не означает, что все следует сваливать на SQL сервер, т.к. порой используя GROUP BY + ORDER BY можно вроде не очень сложным запросом загрузить его по самое не балуйся…

Прежде чем начинать интенсивно использовать какой-либо запрос загляните в документацию по SQL серверу для поиска наиболее оптимальных путей решения тех или иных задач, а для MySQL пусть команда EXPLAIN станет вашей любимой командой :)

P.S. Огромное спасибо за множество идей