Древовидные комментарии с бесконечной вложенностью

Sanu0074 · 2013-11-04T11:18:30.0000000Z

Есть идея написать древовидные комментарии, не знаю на сколько она тупая или хорошая, и как сильно нагрузит сервер, но степень вложенности получится = 2 Есть таблица комментов: id - id комента content_id => id поста к которому принадлежат комменты parent_id => id родительского коммента ..... и другие данные При добавлении коммента, записываем parent_id = NULL - если это комментарий, не ответ на какой-либо (нет родителя) или parent_id = id_коммента - которому ответили (родитель) При извлечении: - выбираем все комменты с нужным content_id - проходим циклом по извлеченному массиву, если parent_id = NULL - приступаем к следующей итерации цикла, если в parent_id чтото есть - то извлекаем нужный коммент Сформированную строку отдаем в браузер. НУЖНО, переделать эту идею так чтобы степень вложенности была бесконечная. Для этого необходимо что-то абсолютно новое или как-то можно доработать эту идею? Интересны ваши предложения. Спасибо за внимание.

97

bukachuk

4 ноября 2013, 15:42

#21

var_dump($comments); какой у вас, если конечно не огромный:D

Программирование PHP,Mysql (/ru/forum/934470)

110

Sanu0074

4 ноября 2013, 15:46

#22

bukachuk:
var_dump($comments); какой у вас, если конечно не огромный:D

вот кусок кидаю:

---------- Добавлено 04.11.2013 в 19:54 ----------

Сделал так, выводит только последний добавленный по списку parent_id:

$str = "<ul>";



$pcm=array();



for($i=0;$i<count($comments);$i++){

	 if(!empty($comments[$i]["parent_id"])){

		 $pcm[$comments[$i]["parent_id"]]=$comments[$i];

	 }

}



function buildTree($pid,$pcm){

	

	if(isset($pcm[$pid])){

		$tree = '<ul>';

		   $tree .= '<li style="background:green">'.$pcm[$pid]['text'];

		   if(!empty($pcm[$pid]["parent_id"]) && $pcm[$pid]["parent_id"]!=$pid){$tree.=buildTree($pcm[$pid]["parent_id"],$pcm);}

		   $tree .= '</li>';

		$tree .= '</ul>';

	  }

	  else {return NULL;}

	  return $tree;

}

for($i=0;$i<count($comments);$i++){

	 if(empty($comments[$i]["parent_id"])) $str.="<li style='background:red'>".$comments[$i]["text"]."</li>";

	 if(!$comments[$i]["parent_id"]){

		 $str.=buildTree($comments[$i]["id"],$pcm);

	 }

}

echo $str."</ul>";

204

дани мапов

4 ноября 2013, 15:55

#23

LEOnidUKG:
Название темы прочитайте и самый верхний комментарий сами.

Это и ребёнок может с 2-мя уровнями :)

Точно - я ошибся, ТС сорри. Хорошо что на форуме есть такие люди как Leonindkg - всегда с готовностью укажут на чужие ошибки.

Написание и доработка скриптов (PHP, MySQL, JavaScript, jQuery) (/ru/forum/811046)

97

bukachuk

4 ноября 2013, 16:03

#24

for($i=0;$i<count($comments);$i++){

	 if(!empty($comments[$i]["parent_id"])){

		 $pcm[$comments[$i]["parent_id"]]=$comments[$i];

	 }

}

Вот тут комменты дочерние затирать будут друг друга, то есть одному родителю - один дитя

110

Sanu0074

4 ноября 2013, 17:03

#25

bukachuk:

Вот тут комменты дочерние затирать будут друг друга, то есть одному родителю - один дитя

точно! и еще пару ошибок исправил:

$str = "<ul>";



$pcm=array();



for($i=0;$i<count($comments);$i++){

	 if(!empty($comments[$i]["parent_id"])){

		 $pcm[$comments[$i]["parent_id"]]=$comments[$i];

	 }

}



function buildTree($pid,$pcm){

	if(isset($pcm[$pid])){

		$tree = '<ul>';

		   $tree .= '<li style="background:green">'.$pcm[$pid]['text'];

		   if(!empty($pcm[$pid]["parent_id"]) && $pcm[$pid]["parent_id"]!=$pid){$tree.=buildTree($pcm[$pid]["parent_id"],$pcm);}

		   $tree .= '</li>';

		$tree .= '</ul>';

	  }

	  else {return NULL;}

	  return $tree;

}

for($i=0;$i<count($comments);$i++){

	 if(empty($comments[$i]["parent_id"])) $str.="<li style='background:red'>".$comments[$i]["text"]."</li>";

	 if(!$comments[$i]["parent_id"]){

		 $str.=buildTree($comments[$i]["id"],$pcm);

	 }

}

echo $str."</ul>";

И как же обойти эту проблему?

K

185

Kuasar

4 ноября 2013, 20:49

#26

Рекурсия при "бесконечной" вложенности - это зло.

Сортировка массива в памяти при большом количестве комментов - это зло.

Не секрет, что страницу комментов чаще читают, чем постят комменты. Поэтому выдачу надо делать максимально быстро с минимальной нагрузкой на сервер. А вот когда поступает новый пост, тут и надо делать всю работу.

У меня на компе уже больше 10 лет хранится такая вот статья. Не помню уже даже откуда слил.

Статья подробная и длинная. Поэтому постить буду в несколько этапов.

---------- Добавлено 04.11.2013 в 23:50 ----------

Алгоритм построения древовидного форума без использования рекурсии

Копия от 21 декабря 2002 года. Оригинал статьи

Постановка задачи

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

Если рассмотреть задачу подробно, оказывается, что проблему представляет только сортировка писем внутри треда. Применим стандартный прием для таких ситуаций: предварительную сортировку, осуществляемую еще на этапе вставки письма в тред. Для этого в таблице писем создадим дополнительное поле X типа INT для этой цели. При этом проблема быстродействия перемещается в момент вставки письма, но тут мы ее легко решаем при помощи алгоритма со сборкой мусора, где мусором является неравномерность распределения значений поля X по допустимому диапазону (от 0 до MAXINT).

freebitco.in - раздача BitCoin'ов + депозит в BTC под 4,08% (https://goo.gl/M1WZoZ)

Какую бесплатную CMS без Структура БД книг сервер с CentOS 5.7

K

185

Kuasar

4 ноября 2013, 20:50

#27

Реализация

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

Опишем таблицу для хранения сообщений. В данном случае я дам только поля, необходимые для функционирования алгоритма, и абстрактное поле Data, в котором хранятся данные, относящиеся к письму. В реальных условиях это поле заменяется на поля TEXT Body, VARCHAR(255) Subject, VARCHAR(255) FromUser и так далее — все, что Вам надо для конкретной реализации.

CREATE TABLE Messages

(INT UNSIGNED ID NOT NULL PRIMARY KEY

,INT UNSIGNED ForumID NOT NULL,INDEX(ForumID)

,INT UNSIGNED ThreadID NOT NULL,INDEX(ThreadID)

,INT UNSIGNED ParentID NOT NULL DEFAULT 0,INDEX(ParentID)

,INT UNSIGNED X NOT NULL DEFAULT 0,INDEX(X)

,INT UNSIGNED Level NOT NULL DEFAULT 0,INDEX(Level)

,TEXT Data

);

Описание полей

ID

Идентификатор письма

ForumID

Идентификатор форума

ThreadID

Идентификатор треда

ParentID

Идентификатор исходного письма для данного ответа. Ноль, если письмо начинает новый тред.

X

Последовательность вывода писем в треде

Level

Отступ при выводе письма

Data

Данные письма

Алгоритмы

Итак, что нам нужно уметь делать с этим хозяйством: а) вставлять письмо, начинающее новую тему; б) вставлять ответ на уже существующее письмо; в) выводить все это красивыми ступеньками, причем на каждом уровне письма отсортированы по времени в обратном порядке, то есть самый последний ответ сверху, ближе всего к оригиналькому письму (на которое отвечали), остальные уезжают вниз. Рассмотрим каждое из этих действий.

Вставка нового письма

Исходные данные: $ForumID, $data. Мы должны сформировать номер для нового треда и вставить письмо. Делается это двумя запросами:

// Нашли новый ThreadID

mysql_query("SELECT @NewThreadID:=MAX(ThreadID)+1 FROM Messages");

// Вставили письмо

mysql_query("INSERT INTO Messages SET ForumID=$ForumID,ThreadID=@NewThreadID,Data=$data");

Поля X и Level мы не устанавливаем, и они принимают значение по умолчанию, то есть ParentID=0 (это не ответ), X=0 (первое письмо в треде) и Level=0 (нулевой уровень, нет отступа). Обратите внимание на два момента. Во-первых, я использовал для хранения номера нового треда переменную MySQL, потому что снаружи MySQL это число мне просто не нужно. Этого делать не обязательно, Вы можете передавать это число из одного запроса в другой через переменную языка программирования. Второй момент связан с тем, что номер ThreadID является глобальным для всех форумов в данной базе. Тут есть некоторое искушение добавить в первый запрос WHERE ForumID=$ForumID и тем самым «сэкономить» идентификаторы тредов, но не надо ему поддаваться. Потому что есть такая дополнительная операция, как перенесение треда в другой форум, и нам лучше будет не искать новый ThreadID при этом.

Добавление ответа на письмо

Самая интересная ситуация, потому что именно тут мы осуществляем всю грязную работу. Сначала опишем, каким образом формируются поля, а потом общий алгоритм. Исходные данные: переменная $parent, в которой лежит запись исходного письма (мы ее туда взяли по mysql_fetch_object()), а также переменная $data, где находятся полученные от пользователя данные.

ForumID

Такой же, как у $parent (ForumID=$parent->ForumID). Если только Вы не предусмотрите возможности отвечать из одного форума в другой.

ThreadID

Такой же, как у $parent (ThreadID=$parent->ThreadID).

ParentID

Идентификатор $parent (ParentID=$parent->ID).

Level

На единицу больше, чем у $parent (Level=$parent->Level).

X

Тут-то кабан и порылся. Мы должны вставить новое письмо между $parent и следующим письмом треда, либо после $parent, если $parent — последнее письмо треда. Для этого берем диапазон, снизу ограниченный $parent->X, а сверху — либо X следующего письма треда, либо максимальным возможным значением MAXINT. И ставим X прямо в центр этого диапазона, вычисляя его по нехитрой формуле X=(MinX+MaxX)/2. При этом может возникнуть ситуация, когда вследствие накопления мусора у нас уже не осталось зазора между $parent и следующим письмом треда. Это может случиться, к примеру, если будет много ответов на одно письмо (с каждым новым ответом диапазон уменьшается в два раза). Выявив эту ситуацию, мы должны запустить единственный длительный процесс в этом алгоритме: сборку мусора. Она будет выражаться в том, что мы заново перенумеруем весь тред по полю X, выровняв все интервалы между сообщениями. Предварительно можно проверить, а влезет ли в этот тред что-либо еще вообще. Простейший способ это сделать — посчитать количество писем в треде и сравнить его с MAXINT/2. Конечно, при этом мы получим тред в два раза менее емкий, чем теоретический предел, но не будем заморачиваться на этом. Лично я надеюсь в этой жизни не увидеть ТАКИХ дискуссий. После сборки мусора у нас гарантированно есть интервал между $parent и следующим письмом, так что после этого мы смело идем на процедуру вставки ответа в момент вычисления диапазона для X.

Теперь все вместе

function getRecord($sql)

{

  $rs=mysql_query($sql);

  $record=mysql_fetch_object();

  mysql_free_result($rs);

  return $record;

}



function getNextX($parent)

{

  $rs=mysql_query("SELECT X FROM Messages WHERE ThreadID=$parent->ThreadID AND X>$parent->X 

ORDER BY X LIMIT 1");

  $record=mysql_fetch_object($rs);

  mysql_free_result($rs);

  if($record) return $record->X;

  return MAXINT;

}



$maxX=getNextX($parent);



// Если у нас некуда вставлять запись...

if($maxX-$parent->X < 2)

{

  // Сколько писем-то?	

  $cnt=getRecord("SELECT COUNT(*) as Messages FROM Messages WHERE ThreadID=$parent->ThreadID");

  $step=(int)(MAXINT / $cnt->Messages);

  if($step<2)

    die("Can't insert message!");



  // Перенумеруем!

  $cursor=0;

  $rs=mysql_query("SELECT * FROM Messages WHERE ThreadID=$parent->ThreadID ORDER BY X");

  while($message=mysql_fetch_object($rs))

  {

     mysql_query("UPDATE Messages SET X=$cursor WHERE ID=$message->ID");

     if($message->ID == $parent->ID)

        $maxX=($parent->X=$cursor)+$step;

     $cursor+=$step;

  }

  mysql_free_result($rs);

}



// Вычисляем новый X

$newX=(int)(($parent->X + $maxX)/2);



// Все готово, вставляем сообщение

mysql_query("INSERT INTO Messages SET ForumID=$parent->ForumID, ThreadID=$parent->ThreadID,"

           ."ParentID=$parent->ID, Level=1+$parent->Level, X=$newX, Data=$data");

Примерно так. Естественно, этот фрагмент кода можно рассматривать только как чисто условный, так как с целью упрощения тут делаются вещи, которые обычно делаться не должны: «обработка» ошибки при помощи die(), использование низкоуровневых функций php для обращения к mysql безо всякого враппера, и так далее.

Вывод форума

Итак, теперь у нас есть сортировка внутри тредов, так что мы можем смело вывести весь форум одним запросом. Исходные данные — $ForumID.

function printMessage($message)

{

	$offset=offsetStart+$message->Level*offsetStep;

	echo "<DIV STYLE=\"margin-left: $offset\">";

		// Печатать заголовок сообщения...

		echo ...

	echo "</DIV>";

}



$rs=mysql_query("SELECT * FROM Messages WHERE ForumID=$ForumID ORDER BY ThreadID DESC, X");

while($message=mysql_fetch_object($rs))

	printMessage($message);

mysql_free_result($rs);

Правда, реальность несколько отличается от данной теории. Проблема в том, что форум надо выводить не весь, а постранично, и хорошо бы бить на страницы по границам тредов. Для этого нам придется сделать дополнительный запрос, чтобы выбрать все треды, нужные для данной страницы. Исходные данные: $ForumID, $PageSize — количество тредов на страницу, $CurrentPage — текущая страница.

$startRecord=$PageSize*$CurrentPage;

$threads=array();



$rs=mysql_query("SELECT ThreadID FROM Messages THERE ForumID=$ForumID GROUP BY ThreadID "

                "ORDER BY ThreadID DESC LIMIT $startRecord,$PageSize");

while($thread=mysql_fetch_object()) $threads[]=$thread->ThreadID;

mysql_free_result($rs);



$rs=mysql_query("SELECT * FROM Messages WHERE ThreadID IN (".join(',',$threads).") 

ORDER BY ThreadID DESC, X");

while($message=mysql_fetch_object($rs))

	printMessage($message);

mysql_free_result($rs);

В данном случае сортировка осуществляется по номеру треда, но можно также сортировать по «свежести» сообщений, если хранение этой информации предусмотрено (ORDER BY MAX(CreatedAt_field)), или еще как-нибудь.

Как видите, данный принцип позволяет свести наиболее частую операцию — показ дерева форума — к минимальному алгоритму всего с парой запросов. Форумы на этом принципе, реализованные на ASP, а затем PHP, эксплуатируются автором несколько лет и показали высокую эффективность данного подхода.

Комментарии — на akul@otamedia.com

1

[MySQL] выбор случайных записей какие существуют CMS без Помощь по Oracle

110

Sanu0074

5 ноября 2013, 07:19

#28

Kuasar, спасибо) хорошая статья

Яндекс Вебмастер вынес товарные фиды в отдельный раздел

Что делать, чтобы попасть в ответы Google Bard