Дерево категорий.

А нельзя ли дерево хранить в виде структуры в базе? При его изменении, обновлять запись...
Тот же мемкешед, только для не страшен для виртуальных хостингов.
Или вообще готовый php-массив хранить в папке, а потом его инклудить.

http://www.photosight.ru/photos/3101546/

 

NestedSets - самый медленный способ работы с деревьями

 

как часто в дерево будут вноситься изменения?

доступ к shared memory куда быстрее чем доступ к memcached

 

сорри, я тему не читал, но влезу. Нафигачил вчера такой класс:

PHP:

1. <?php
2. class Array2Tree
3. {
4.     private $array;
5.     private $tree;
6.    
7.     function __construct($array)
8.     {
9.         $this->tree[0] = array('id'=>0, 'title'=>'root');
10.         $this->array = $array;
11.     }
12.    
13.     private function addEl($el, &$node)
14.     {
15.         if(!is_array($node))
16.             return;
17.         if(array_key_exists($el['pid'], $node)) {
18.             $node[$el['pid']]['child'][$el['id']] = array(
19.                 'id'=>$el['id'],
20.                 'title'=>$el['title']
21.             );
22.         } else {
23.             foreach($node as &$subNode) {
24.                 $this->addEl($el, $subNode['child']);
25.             }
26.         }
27.     }
28.    
29.     public function convert()
30.     {
31.         foreach($this->array as $node)
32.             $this->addEl($node, $this->tree);
33.        
34.         return $this->tree;
35.     }
36.    
37.     private function resetKeys($node)
38.     {
39.         $i = 0;
40.         foreach($node as $el) {
41.             $newNode[$i] = $el;
42.             if(is_array($el['child']))
43.                 $newNode[$i]['child'] = $this->resetKeys($el['child']);
44.             $i++;
45.         }
46.         return $newNode;
47.     }
48.    
49.     public function convertAndResetKeys()
50.     {
51.         $this->convert();
52.         return $this->resetKeys($this->tree);
53.     }
54. }
55. ?>

суть его работы в следующем: есть таблица `categories` (`id`, `pid`, `title`).
...
SELECT `id`, `pid`, `title` FROM `categories` ORDER BY `id`;
...
$array = $db->fetchAll // будет массив ассоциативных массивов
$a2t = new Array2Tree($array);
$tree1 = $a2t->convert();
$tree2 = $a2t->convertAndResetKeys();

теперь $tree1 = массив в виде:

Код (Text):

1. 0=>array(
2.     'id'=>0,
3.     'title'=>root,
4.     'child'=>array(
5.         3=>array(
6.             'id'=>3,
7.             'title'=>холодильники,
8.             'сhild'=>array(
9.                 5=>array(
10.                 'id'=>5,
11.                 'title'=>с 2 дверями
12.                 )
13.             )
14.         )
15.     )
16. )

$tree2 - Тоже самое, что и $tree1, только ключи с 0 начинаются (вместо 3 и 5 - 0)

сорри, что перебил

как выбирать отдельные ветви - пока не придумал. Не хотел заморачиваться с дополнительными полями типа hasChild, соседиСлева, соседиСправа. Только id, pid, прочие поля типа title

 

На виртуальных хостингах разве есть memcached?

 

Самый медленный где и по сравнению с чем? Запись и, особенно, нормализация дерева - всегда тяжелые операции. И можно с ними бороться, улучшать их производительность, только зачем? В обычной веб-практике редко бывает больше тысячи категорий. И добавление категории происходит относительно редко. Относительно выборок.

 

http://habrahabr.ru/blogs/development/47280/ не совсем "самый"

 

Kreker
Я одним глазом пролистал и повторю ту же мысль:

 

Глубина?

 

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

 

Да в пхп файле структуру хранить и всё =)

 

есть такой былинный код

PHP:

1. <?php
2.     private function getRows()
3.     {
4.         $res = $this->db->query('SELECT ?c@ FROM ?t ORDER BY ?c ?k', array('id', 'pid', 'title'), 'category', 'id', 'ASC');
5.         while($row = $this->db->fetch($res))
6.             $rows[$row['pid']][$row['id']] = $row['title'];
7.        
8.         $this->rows = $rows;
9.     }
10.    
11.     function buildTree($tree, $pid = 0)
12.     {
13.         $tpl = new phparser('templates/admin', 'cache');
14.         $tpl->load('modules/' . $this->module . '/categories', '.xml');
15.         $i = 0;
16.        
17.         foreach($tree as $id=>$root) {
18.             if($pid != $id) continue;
19.             if(count($root)) {
20.                 foreach($root as $key=>$title) {
21.                     $rows[$i]['id'] = $key;
22.                     $rows[$i]['title'] = $title;
23.                     $rows[$i]['child'] = NULL;
24.                     if(count($tree[$key]))
25.                         $rows[$i]['child'] = $this->buildTree($tree, $key);
26.                     $i++;
27.                 }
28.             }
29.         }
30.        
31.         $tpl->l('rows', $rows);
32.         return $tpl->get_parse();
33.     }
34.    
35.     private function writeXML()
36.     {
37.         $tpl = new phparser('templates/admin', 'cache');
38.         $tpl->load('modules/' . $this->module . '/list', '.xml');
39.        
40.         $tpl->v('header', XML_HEADER);
41.         $tpl->v('categories', $this->buildTree($this->rows));
42.         file_put_contents('cache/categories.xml', $tpl->get_parse());
43.     }
44.  

в базе id,pid,title.

Прошу обратить внимание именно на 6 строку. Это какой-то алгоритм вывода дерева, подразумевающий формирования массива $a['pid']['id'] = $title; Тогда это дерево безболезненно выводится. Но возникают проблемы: как производить сортировку вывода? К примеру я хочу чтобы в меню "лопаты" находились под "электролобзиками". Тут же будет просто вывод непонятно как отсортированный

 

тут как ни сортируй, все равно будет сформирован массив a[pid][id], который потом выводится и вся сортировка идет лесом ((.

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

upd: я вру, все нормально сортирует, если выводить полностью дерево. Возможно будут проблемы при выводе путя от текущей категории до корня с показом подразделов.