Вывод комментариев с иерархической структурой

Question

[Mirgorod]

Здравствуйте, как реализовать вывод комментариев как на хабре?
Меня интересует как это будет выглядеть на серверной стороне, в плане вёрстки и стилей для таких комментариев всё понятно.

К примеру у меня есть таблица:

Messages:
id
pid
topic_id
message

Где pid — идентификатор родительского комментария.

Comments

[1nd1go]

Хочу уточнить вопрос:
1. Как организовать хранение дерева в NoSQL, например в Mongo
2. Что лучше — высосать все дерево одним запросом, потом этот запрос мапить в структуру объектов, или почастям вычекивать из БД, и постепенно замапапливать в структуру, чтобы потом ее транслировать в HTML?
3. Какая структура должна быть в коде приложения в результате мапинга из базы?

Answer 1

[Анатолий]

Серверный вариант:
1. Считываем все из базы
2. Строим дерево
3. Проходим по дереву и выводим каменты
4.!!!
5. PROFIT

Comments

[Анатолий]

Немного корявенько, но я не люблю рекурсию

<?php

$elems = array(
	array( 'id' => 1, 'pid' => 0, 'title' => '1' ),
	array( 'id' => 2, 'pid' => 1, 'title' => '2' ),
	array( 'id' => 3, 'pid' => 1, 'title' => '3' ),
	array( 'id' => 4, 'pid' => 3, 'title' => '4' ),
	array( 'id' => 5, 'pid' => 0, 'title' => '5' ),
	array( 'id' => 6, 'pid' => 5, 'title' => '6' ),
	array( 'id' => 7, 'pid' => 5, 'title' => '7' ),
	array( 'id' => 8, 'pid' => 5, 'title' => '8' ),
	array( 'id' => 9, 'pid' => 0, 'title' => '9' ),
);

$links = array();

$tree = array();

for( $q = 0; $q < count( $elems ); $q++ )
{
	$elem = $elems[$q];
	
	if( $elem['pid'] === 0 )
	{
		$tree[$elem['id']] = $elem;
		$links[$elem['id']] = &$tree[$elem['id']];
	}
	else
	{
		$links[$elem['pid']]['childrens'][$elem['id']] = $elem;
		$links[$elem['id']] = &$links[$elem['pid']]['childrens'][$elem['id']];
	}
}

echo '<pre>';
print_r( $tree );
echo '</pre>';

?>

Answer 2

[Lergero]

Прочтите статью
www.getinfo.ru/article610.html — все достаточно ясно. Я для себя даже распечатал

Comments

[interrupt_controller]

зачем все так сложно, ему всего-навсего нужно вывести комментарии в виде дерева

Answer 3

[Артур Хашаев]

Вообще говоря, есть три подхода.

Первый и самый простой — материализованные пути, это когда мы для каждого комментария храним весь его путь от корня, то есть имеем такую структуру, которая выглядит как-то так:

1.
1.1.
1.2.
1.2.1.
1.3
2.
2.1.

Ну и так далее. Для получения всех комментариев в нужном порядке необходимо просто сделать запрос на получение всех комментариев, только отсортированных в лексикографическом порядке по полю, которое содержит этот путь. Если не учитывать время выполнения запроса, то асимптотически это дело будет работать за O(n), где n — количество комментариев.

Второй подход, чуть посложнее, но выглядящий менее криво — для каждого комментария хранить номер родительского. После того, как мы сделали запрос на получение комментариев, отсортированных по id, мы пробегаем по этим комментариям. Будем строить дерево комментов. Понятно, что если у какого-то комментария есть родитель, то мы его уже добавили в дерево, так как у нас комментарии приходят в отсортированном порядке по их номеру. Поэтому возьмём номер родительского комментария и вставим в список его детей текущий коммент (т. е. что-то типа children[parent_id].insert(node_id)). После такого прохода получим дерево, с которым дальше можем делать что угодно. Получаем асимптотику O(n) при использовании обычных массивов и O(n log n) при использовании ассоциативных массивов, но меньший расход памяти.

Третий подход — использовать уже указанные выше Nested Sets, но на практике, по-моему, их никто не использует.

Comments

[Виктор]

Да, NestedSets — очень хороший вариант. И на практике, довольно часто используемый способ, на самом деле.

[Анатолий]

Эм, если что, Ваш второй вариант самый простой, третий самый сложный, а первый — гибрид предидущих. И у Вашего «самого простого» варианта, по сравнению со вторым большие накладные расходы при вставке/переносе каментов, и эти расходы на много существенней чем расходы на выборку во втором подходе.

Answer 4

[TheHorse]

Рекомендую хранить дерево другим образом:
id…… pos
1…… '00'
2…… '01'
3…… '0000'
4…… '0001
Где pos — позиция коммента.
pos = pos(parent(last_child)) + 1 (если parent имеет childs);
pos = pos(parent) + '00'; ( в любом другом случаее).

Строка pos хранит точное положение коммента, по ней можно определить parent и всех child. А самое главное, для вывода дерева, достаточно сделать запрос:
select * from comments order by pos;
и одним циклом вывести весь результат на экран (без доп операций), указывая отступ от левого края равным длине строки pos.

Comments

[TheHorse]

А еще этот вариант расчитан на то, что просмотры — более частая операция чем добавление комментов; соответственно будет работать быстрее. Скорость будет хорошей даже без кэша. А построение дерева по набору id, pos — сложная операция.

[Анатолий]

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

[TheHorse]

Ну зато это ровно 1 запрос к БД (у меня в него-же получалось вписать и рейтинги, без вложенных select-oв), и на стороне сервера (который скорей всего не нативный) почти ничего не нужно создавать. В общем, я не понимаю, почему минусуют. Алгоритм проверен годами. Может описал не подробно? Или не на тот вопрос ответил?

[Анатолий]

select * from comments У меня тоже ровно один запрос получился, как ни странно.

[TheHorse]

Ну пре-обработка на сервере займет тучу времени (относительно). Вы считаете, что ваш вариант будет работать быстрее?

[asm0dey]

А почему пре-обработка должна происходить на сервере? Можно же и на js реализовать.

[TheHorse]

Можно, но лучше этого не делать. JS может быть отключен, комп клиента может быть плохим и с устаревшим браузером.

[Анатолий]

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

[TheHorse]

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

[TheHorse]

*лиш

[Анатолий]

Нужно два массива, один для дерева коментариев, а второй для ссылок на каждый элемент того дерева.
При добавлении дитя в дерево, находим по айди ссылку на нужную ветку во втором массиве и просто добавляем ему элемент. Второй массив содержит ссылки, поэтому памяти будет не так много уходить как кажется

Answer 5

[Артур Кох]

Я уже задавал подобный вопрос. Возможно вам ответы будут полезны

Answer 6

[interrupt_controller]

функция комментарий(id родителя)
{

}

Comments

[interrupt_controller]

функция комментарий(id родителя)
{
получить список детей
начало цикла:
вывести ребенка
если есть дети
вызвать комментарий(id текущего элемента(ребенка))
конец цикла
}

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

зы: случайно отправил ответ

[Владимир Голованов]

Рекурсивный алгоритм с подзапросом на каждой ветке?
Или сразу все ветки дерева подгружаем из базы, а потом строим?

[interrupt_controller]

загружаем из базы одним запросом данные в массив, элементами которого является ассоциативный массив вида
array(«field_name1» = > «value1», «field_name2» = > «value2», etc)

получение списка детей можно делать двоичным поиском, отсортировав массив по pid ksort'ом, например

это как один из вариантов, можно в принципе это дело оптимизировать, но автору вопроса нужна только суть

Answer 7

[mark_ablov]

можно использовать вспомогательную таблицу родителей.
там всего 3 поля — id, parentId, parentLevel.
собственно, если есть кусок дерева:
-1
--2
---3
то в таблице будет 3 записи:

3, 2, 1
3, 1.

Comments

[mark_ablov]

id, parentId, parentLevel.
3, 2, 1
3, 1, 2
2, 1, 1

Answer 8

[nixmale]

Если еще актуально, то есть и такое решение habrahabr.ru/qa/7550#answer_32413

Отличается оно тем, что добавляя коментарии с помощью ajax не обязательно перестраивать все комменты, а можно перегрузить лишь ветку, начинающуюся с коммента на который отвечаете, и без рекурсиии и строковых полей.