Древовидный форум

Макс · 14 Фев 2002

Древовидный форум

Пишу форум с древовидной структурой.
Есть у меня 2 варианта.

1. При построении дерева из БД сообщения получаю с "неправильной" сортировкой и с помощью PHP отсортировать сообщения в правильном порядке для вывода в виде дерева.
Дерево строится сравнительно медленно, но при создании сообщений все будет быстро (в один запрос).

2. Получить из БД сразу сообщения в правильном порядке и сразу выводить дерево.
Так оно конечно будет строится гораздо быстрее.
Но в этом случае нужно 3-4 запроса к БД для того чтобы организовать такое расположение данных. Хотя в этих запросах работа будет вестись с цифровыми данными (числами) которые можно сделать индексами и соответственно работа с ними ускорится.

Вот сижу и думаю, чтобы выбрать мне.
Кто что посоветует.

Demiurg · 14 Фев 2002

Re: Древовидный форум

Автор оригинала: Maxim Matyukhin
Вот сижу и думаю, чтобы выбрать мне.
Кто что посоветует.

Древовидные структуры давольно тяжело извлекать из базы данных. Так что легче, на мой взгляд, будет просто записывать в базу постинги со своей структурой, которая пользователю, при выводе будет козаться древовидной.
А еще можно посмотреть, как с этой проблемой обходится Phorum.

su1d · 15 Фев 2002

Re: Re: Древовидный форум

Древовидные структуры давольно тяжело извлекать из базы данных.

Хмм.. а что тяжёлого в таком запросе на получение всей ветки дерева?
SELECT * FROM table_name WHERE field_name BETWEEN 3 AND 8

http://e-taller.net/dev/dbtree/

Demiurg · 15 Фев 2002

Re: Re: Re: Древовидный форум

Автор оригинала: su1d
Хмм.. а что тяжёлого в таком запросе на получение всей ветки дерева?
SELECT * FROM table_name WHERE field_name BETWEEN 3 AND 8
http://e-taller.net/dev/dbtree/

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

chira · 15 Фев 2002

Одним запросом в MySQL нельзя построить дерево для структуры о которой говорил Demiurg, но можно использовать рекурсивную функцию. Примерно такую:

PHP:

function recc($id,$level){
   global $sys_max_level, $tb_name;
   if($level > $sys_max_level) return;
   $q = 'select cc_id, category '.
           "from $tb_name cc ".
           'where cc1_id = '.$id.
           " and available = 1";

   $res = mysql_query($q) or die("query failed: ".mysql_error());
   $nrows = mysql_num_rows($res);
   if($nrows > 0){
       while($row = mysql_fetch_array($res)){
              for ($n = 0; $n < $level; $n++) echo '. . . . ';
              echo '&nbsp;'.$row['category'].'<br>';
              recc($row['cc_id'],$level + 1);
       }
   }
}

Выборка идет по условию Primary Key = $id, работает быстро.

Demiurg · 15 Фев 2002

Автор оригинала: chira
.... работает быстро.

В этом я не уверен. Количество запросов даже не прямо зависит от вложености. ИМХО при сильном ветвлении будет сильно тормозить.

chira · 15 Фев 2002

Здесь как-то было предложение структуры таблицы форума выборка из которой делается одним запросом.

Идея : для записи главного вопроса хранить все id ответов через запятую (10,30,100,1000)
при выборке использовать IN оператор
а для каждого ответа хранить ID вопроса.

Если список ответов хранить в VARCHAR , то появляется ограничение на количество ответов или использовать TEXT.

Если форум будет выглядеть как этот (дерево в ответах не просматривается) , то вполне можно использовать такой подход ...

Макс · 15 Фев 2002

Автор оригинала: chira
Здесь как-то было предложение структуры таблицы форума выборка из которой делается одним запросом.
Идея : для записи главного вопроса хранить все id ответов через запятую (10,30,100,1000)
при выборке использовать IN оператор
а для каждого ответа хранить ID вопроса.
Если список ответов хранить в VARCHAR , то появляется ограничение на количество ответов или использовать TEXT.
Если форум будет выглядеть как этот (дерево в ответах не просматривается) , то вполне можно использовать такой подход ...

Я делал по другому.
У каждого сообщения есть поле Number - номер сообщения в ветке. Именно по нему и происходит сортировка и получается дерево в нужном порядке.
+ еще поле level - для определения уровня вложенности данного сообщения в ветке.

Если скажем, кто-то вносит в ветвь еще одно сообщение - происходит определение, какой number должен быть у этого нового сообщения и у всех сообщений данной ветки, имеющих number больше или равный вычисленому делаем UPDATE ... SET number=number+1 ...
Именно на определение number и изменение порядка следования сообщений идут 2-3 запроса при создании сообщения.

AnToXa · 15 Фев 2002

блин, люди вы читали http://e-taller.net/dev/dbtree/ или нет??
там все очень красиво и правильно, или вы сюда пришли не спрашивать, а рассказывать себе как вы делаете?

З.Ы. 2 su1d сделай новые тесты кстати, плиз и выложи так же как и с шаблонами, а то неудобно

и еще, можт стоит оригинал скопировать? тот который в html и выложить, большинству на русском удобнее будет, если забыл ссылку, то http://sdm.viptop.ru/articles/sqltrees.html

Vladimir · 15 Фев 2002

Правильно говоришь, полностью согласен.
Закон Мэрфи гласит - "Если у вас чего то не получается, прочтите наконец инструкцию".
Дополнение - "Не перепрограммируйте функцию вычисления квадратного корня".

Макс · 15 Фев 2002

Автор оригинала: AnToXa
блин, люди вы читали http://e-taller.net/dev/dbtree/ или нет??

Уже читаю

там все очень красиво и правильно, или вы сюда пришли не спрашивать, а рассказывать себе как вы делаете?

Это я в последнем сообщениии немного тупо выразил свои мысли.
То что я там описал один из методов, между которыми я выбираю.
А второй - это рекурсивная функция, как chira написал.

su1d · 15 Фев 2002

Re: Re: Древовидный форум

Автор оригинала: Demiurg
Единственный способ хранения деревьев в чистом виде, который мне приходит на ум...

Demiurg, ты даже отквотил мой линк в своём ответе, но по-моему не утруждал себя нажатием на него.

Совсем недавно я на этом же форуме предлагал ТРИ способа хранения дерева в базе данных. Все разные, и у каждого есть свои особенности и недостатки. Так что способ уж точно не один...

Сейчас я везде храню деревья во вложенных множествах (Nested Sets) - очень быстро и удобно. По скорости и эффективности выборки совсем не сравнить с Adjacency List, где ты хранишь для каждой записи идентификатор родителя, и со структурой, где полный путь в дереве хранится в одном поле (что, более того, уже идёт против принципов нормализации БД).
Надо заметить, что вложенные множества относительно тормозят при добавлении/удалении записи (это видно на бенчмарках), но в большинстве случаев программирования для веба выборка данных происходит НАМНОГО более чаще их изменения. Поэтому оптимизировать нужно именно поиск и выборку данных из БД, а здесь вложенным множествам равных почти нет.

Способ этот пока малоизвестен. Может быть из-за своей относительной новизны (Joe Celko его предложил в 92м году), а возможно из-за того, что в нём достаточно трудно разобраться человеку несведущему в математике и программировании, а таких как это ни прискорбно, большинство. Но для таких создаются библиотеки, которые можно использовать, мало понимая как они работают (хоть это и не рекомендуется). Моя библиотека по Вложенным Множествам тоже лежит на линке, который я давал выше.

Удач!

З.Ы. А что значит "хранить дерево в ЧИСТОМ виде"? ...а что тогда "грязный вид"?

AnToXa · 16 Фев 2002

Re: Re: Re: Древовидный форум

su1d: 5 баллов! :э)

Demiurg · 17 Фев 2002

Re: Re: Re: Древовидный форум

Автор оригинала: su1d
Demiurg, ты даже отквотил мой линк в своём ответе, но по-моему не утруждал себя нажатием на него.

Я нажимал, честно

Но я думал, что там все хорошо рассписано. А увидел несколько файлов. Да и некогда было посмотреть по-нормальному. Для меня лично тяжело установить связь между запросом "SELECT * FROM table_name WHERE field_name BETWEEN 3 AND 8 " и древовидной структуры, без других объяснений. Так что извини, если чем обидел, не со зла я

PS а по поводу деревьев в чете мне как-нить расскажешь.

StUV · 12 Май 2003

2All:

как образуются значения полей left и right ???

emp salary left right
==============================
'Jerry' 1000.00 1 12
'Bert' 900.00 2 3
'Chuck' 900.00 4 11
'Donna' 800.00 5 6
'Eddie' 700.00 7 8
'Fred' 600.00 9 10

... в статье толком объясняется только для корневого узла, остальное - с червяком - как-то очень туманно (не понимаю как-куда-откуда он ползет)

Древовидный форум

Макс

Старожил PHPClub

Demiurg

Guest

su1d

Старожил PHPClubа

Demiurg

Guest

chira

Новичок

Demiurg

Guest

chira

Новичок

Макс

Старожил PHPClub

AnToXa

prodigy-одаренный ребенок

Vladimir

Guest

Макс

Старожил PHPClub

su1d

Старожил PHPClubа

AnToXa

prodigy-одаренный ребенок

Demiurg

Guest

StUV

Rotaredom