IMHO.WS
Страница 1 из 2 1 2
Показывать 40 сообщений этой темы на одной странице

IMHO.WS (http://www.imho.ws/index.php)
-   Веб-программирование (http://www.imho.ws/forumdisplay.php?f=29)
-   -   Проблемы с построением "дерева"(+) (http://www.imho.ws/showthread.php?t=78590)

Sheryld 27.01.2005 16:51
Проблемы с построением "дерева"(+)
 
Решил тут написать каталог, простенький. Взял банальный алгоритм(не помню как он называется):

ID-PARENT_ID

т.е. каждая ветка знает своего родителя.
рекурсивной функцией строю дерево.

решил провести тест. заполнил базу 10000 записями. причем, каждая ветка имеет 1 потомка.

т.е. получается 10к запросов вида:

select * from table where parentid = id

apache падает(а может и не он).

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

что интересно, ASP.NET+IIS справляется, хотя и долго.

собственно в чем могут быть грабли(я имею ввиду настройки php, apache, mysql)?

p.s. про другие алгоритмы знаю, но некогда их реализовывать, да и для этой задачи - пустая трата времени.

p.p.s.

hard&soft:

athlon xp1700+, 512 DDR
winxp sp1 eng.

apache 1.3.x
php 4.3.9(как модуль).
mysql 3.23.58 d-max-nt

кстати 5-ый php, опять же - как модуль, "съел" - 6k записей, после чего вывод на страницу просто остановился.

p.p.p.s. добавил принудителньое закрытие mysql соединения после каждого запроса. Похоже виновата все же mysql. Теперь под php4 также просто останавливается вывод.

может кто подскажит утилиту(поудобнее), чтобы смотреть текущие connections и queries для mysql. к сожалению mysql administrator требует mysql 4.x.

EvroStandart 27.01.2005 17:02
Может быть просто гдето в настройках прописано максимальное время выполнения. У меня както была похожая проблема. Увеличил время и всё заработало.

Sheryld 27.01.2005 17:04
оно падает гораздо раньше, чем выходит время выполнения скрипты:)

dacuan 27.01.2005 19:49
Возможно, скрипту не хватает оперативки. По умолчанию там стоит 8M.
В любом случае, можно включить отображение ошибок либо поискать их в логе.

Sheryld 27.01.2005 20:04
ошибки у меня отображаются, логи тоже молчат по этому поводу. а что стоит 8 МБ? как параметр называется?

dacuan 27.01.2005 20:27
Тогда скрипт в студию :)

Hubbitus 28.01.2005 00:25
Цитата:
Sheryld:
а что стоит 8 МБ? как параметр называется?
memory_limit

Цитата:
Sheryld:
p.p.p.s. добавил принудителньое закрытие mysql соединения после каждого запроса. Похоже виновата все же mysql. Теперь под php4 также просто останавливается вывод.
Может в данном случае какраз лучше использовать постоянное соединение?

Sheryld 28.01.2005 10:08
вот скрипт:

Код:
class Category
        {
                var $categoryInfo = array(
                "id"=>0,
                "parent_id"=>0,
                "level"=>0,
                "title"=>"",
                "desc"=>"",
                "creation_date"=>"",
                "modify_date"=>"",
                "photo"=>"");
               
                var $categoryInfoCollection = array();
               
                function Category()
                {
                        //default constructor                       
                }

                          ................

                          function GetCategoryByParentID($categoryParentID)
                {
                        $db = new MySql(null,"mport3",null,null);
                        $db->MySql_Connect();
                        $db->MySql_SelectDb();
               
                        $selectQuery = "select * from category where cat_PARENTID = ".
                        $categoryParentID;
                       
                        $db->MySql_QueryDb($selectQuery);
                       
                       
                        //echo $selectQuery;
                       
                        if ($db->dbResult != null)
                        {
                                while($row = mysql_fetch_assoc($db->dbResult))
                                {
                                        $this->categoryInfo['id'] = $row['cat_ID'];                                       
                                        $this->categoryInfo['parent_id'] = $row['cat_PARENTID'];
                                        $this->categoryInfo['level'] = $row['cat_NODELEVEL'];
                                        $this->categoryInfo['title'] = $row['cat_TITLE'];
                                        $this->categoryInfo['desc'] = $row['cat_DESC'];
                                        $this->categoryInfo['creation_date'] = $row['cat_CREATION_DATE'];
                                        $this->categoryInfo['modify_date'] = $row['cat_MODIFY_DATE'];
                                        $this->categoryInfo['photo'] = $row['cat_PHOTO_URL'];
                                       
                                        $this->categoryInfoCollection[] = $this->categoryInfo;                                       
                                }
                                return 0;
                        }
                        return -1;
                }

                          ................

}
"дерево":
Код:
function Tree($categoryParentID)
        {
                $category = new Category();
                if ($category->GetCategoryByParentID($categoryParentID) == 0)
                {                       
                        if (!empty($category->categoryInfoCollection))
                        {                                       
                                foreach($category->categoryInfoCollection as $categoryInfoItem)
                                {
                                                                                echo $categoryInfoItem["title"] . " " . $categoryInfoItem["parent_id"] . "<BR>\r\n";
                                       
                                        Tree($categoryInfoItem["id"]);
                                }
                        }               
                }       
        }
mysql helper class:
Код:
class MySql
        {
                var $dbServer = "";
                var $dbName = "";
                var $dbUser = "";
                var $dbPass = "";
                       
                var $dbConn;
                var $dbResult;
               
                var $dbErrorNumber = 0;
                var $dbErrorMessage = "";
               
                var $debugFromHanlder = "";
               
                /*function MySql()
                {
                        //default constructor
                       
                }*/
               
                function MySql($dbServer = null, $dbName = null, $dbUser = null, $dbPass = null)
                {
                        //default constructor
                        if ($dbServer != null)
                        {
                                $this->dbServer = $dbServer;
                        }
                        if ($dbName != null)
                        {
                                $this->dbName = $dbName;
                        }
                        if ($dbUser != null)
                        {
                                $this->dbUser = $dbUser;
                        }
                        if ($dbPass != null)
                        {
                                $this->dbPass = $dbPass;                                       
                        }
                }
                function MySql_Connect()
                {
                        if (!isset($this->dbConn) || $this->dbConn == null)
                        {
                                $this->dbConn = @mysql_connect(
                                        $this->dbServer,
                                        $this->dbUser,
                                        $this->dbPass);
                                       
                                $this->MySql_ErrorHanlder("connect");
                        }
                }
                function MySql_SelectDb()
                {
                        if (isset($this->dbName) && $this->dbName != null)
                        {
                                @mysql_select_db($this->dbName,$this->dbConn);
                               
                                $this->MySql_ErrorHanlder("select");
                        }
                }
                function MySql_QueryDb($dbQuery)
                {
                        if (isset($dbQuery) && $dbQuery != null)
                        {
                                $this->dbResult = @mysql_query($dbQuery,$this->dbConn);
                                //echo $dbQuery;
                                $this->MySql_ErrorHanlder("query");
                               
                                if (@mysql_num_rows($this->dbResult) == 0)                               
                                {
                                        $this->dbResult=null;
                                }
                        }
                }
                function MySql_Close()
                {
                        if (isset($this->dbConn) || $this->dbConn != null)
                        {
                                @mysql_close($this->dbConn);
                               
                                $this->MySql_ErrorHanlder("close");
                               
                        }
                       
                }
                function MySql_Free()
                {
                        @mysql_free($this->dbResult);
                       
                        $this->MySql_ErrorHanlder("free");
                }
                function MySql_ErrorHanlder($debugFromHanlder)
                {
                        $this->dbErrorNumber = mysql_errno();       
                        $this->dbErrorMessage = mysql_error();
                       
                        if ($this->dbErrorNumber != 0)
                        {
                                echo $this->dbErrorNumber . "    " . $this->dbErrorMessage;
                                echo "    " . $debugFromHanlder . "<BR>\r\n";
                        }
                                               
                        $this->dbErrorNumber = 0;
                        $this->dbErrorMessage = "";
                }       
        }

Sheryld 28.01.2005 12:08
проблема походу точно в mysql, т.к. опытным путем установил, что коннекта не происходит, видимо их слишком много, но что интересно:

mysql_err* пустые:)

dacuan 28.01.2005 16:03
попробуй сделать выборку категорий только первого уровня.
Но, вообще, не стоит не каждый запрос делать новое подключение. Да и в других местах, есть где оптимизировать.

zaartix 28.01.2005 17:47
Вложений: 1
это может помочь (класс для работы с деревьями любой вложенности)

Sheryld 28.01.2005 20:10
мой класс проходит свободно 500 уровней вложенности. потом начинаются проблемы.

про nested sets я знаю. но не хочу его применять, т.к. в этом проекте он не нужен, а там много времени уйдет на реализацию...

а что можно оптимизировать?

мой интерес чисто теоритический, т.к. в реальных приложениях я ограничиваю вложенность до 100 категорий(на данном алгоритме).

p.s. за файлик спасибо...

[stv] 29.01.2005 23:15
zaartix
Спасибо за класс =) Как раз искал что-то подобное.

dacuan 31.01.2005 18:51
2 Sheryld
Я сильно с алгоритмом не разбирался, но вот, что сразу броилось в глаза (оно большого прироста не даст, но так приятнее работать ;) )
Код:
Код:
$this->categoryInfo['id'] = $row['cat_ID'];
$this->categoryInfo['parent_id'] = $row['cat_PARENTID'];
$this->categoryInfo['level'] = $row['cat_NODELEVEL'];
$this->categoryInfo['title'] = $row['cat_TITLE'];
$this->categoryInfo['desc'] = $row['cat_DESC'];
$this->categoryInfo['creation_date'] = $row['cat_CREATION_DATE'];
$this->categoryInfo['modify_date'] = $row['cat_MODIFY_DATE'];
$this->categoryInfo['photo'] = $row['cat_PHOTO_URL'];

$this->categoryInfoCollection[] = $this->categoryInfo;
Можно заменить на
Код:
$this->categoryInfoCollection[] = $row;
Второе, лучше все-таки отказаться от длинных имен переменных. PHP с именами переменных более 8-ми символов медленно обрабатываются.

И, наконец, главное. Учитывая, что допустимы 100 уровней вложенности, я бы все-таки дважды подумал, прежде чем использовать рекурсию для дерева. IMHO Лишняя нагрузка серверу ни к чему.

Sheryld 31.01.2005 20:25
ну а как реализовать дерево на php без рекурсивного алгоритма, но с моей структурой?

dacuan 01.02.2005 14:42
Чтобы не заморачиваться, можно, например, ввести еще одну таблицу следующей структуры:
Код:
treeid INTEGER AUTOINCREMENT
path  TEXT
id      INTEGER
В таблице будут хранится все пути к узлу дерева. В поле path перечислены идентификаторы всех родителей узла через тире, слеш или любой другой разделитель.
Используя такую таблицу можно легко получить любую ветку дерева одним запросом с условием LIKE. Не самый лучший способ, но будет на порядок эффективнее, чем рекурсия.

Sheryld 01.02.2005 22:28
такой алгоритм тоже знаю, но в принципе против него, т.к. нарушаются условия нормализации.

к тому же его следует применять, имхо, только если есть в наличии ms sql server 2K, например. чтобы повесить основные операции по поддержке дерева на триггеры. т.е. получить структуру саму себя поддерживающую.

в принципе уже каркас написал. по первым тестам(искуственным) работает весьма шустро, если скрестить с кешем - то самое оно. ежели на реальном тесте производительность сильно ухудшится, то наверное возьму за основу nested sets.

у меня там каталог полностью "кастомный", т.е. помимо менеджмента категорий там еще предполагается, что каждая единица в категории имеет неограниченное, настраиваемое число параметров определенных заранее типов(joins, joins, joins).

dacuan 02.02.2005 10:06
Цитата:
Сообщение от Sheryld
такой алгоритм тоже знаю, но в принципе против него, т.к. нарушаются условия нормализации.
Иногда, приходится поступиться принципами нормализации, например для уменьшения нагрузки на сервер.

Цитата:
Сообщение от Sheryld
к тому же его следует применять, имхо, только если есть в наличии ms sql server 2K, например. чтобы повесить основные операции по поддержке дерева на триггеры. т.е. получить структуру саму себя поддерживающую.
За отсутствием триггеров, логику поддержания целостности данных с успехом можно вынести из БД, это, конечно, не так надежно/красиво, но при использовании MySQL является обычной практикой.

Цитата:
Сообщение от Sheryld
в принципе уже каркас написал. по первым тестам(искуственным) работает весьма шустро, если скрестить с кешем - то самое оно.
Зачем опираться не кеш, когда можно разгрузить работу с БД?

Цитата:
Сообщение от Sheryld
ежели на реальном тесте производительность сильно ухудшится, то наверное возьму за основу nested sets.
Думаю, лучше с самого начала выбирать архитектуру приложения. Наложение заплаток редко проходит безболезненно и часто влечет за собой кучу проблем.

Цитата:
Сообщение от Sheryld
у меня там каталог полностью "кастомный", т.е. помимо менеджмента категорий там еще предполагается, что каждая единица в категории имеет неограниченное, настраиваемое число параметров определенных заранее типов(joins, joins, joins).
Не вижу, как это может повлиять на выбор алгоритма работы с деревом.

Sheryld 02.02.2005 13:38
nested sets конечно рулит:

~0.001

рекурсия:

~0.1

:)

Sheryld 02.02.2005 17:14
а как скажем сделать такую вещь(при таком классе nested sets): сортировка каждой ветки дерева но с сохранением порядка.

пример:

должно быть:

Код:
аа
бб
вв
  а_в
  б_в
если, я добавлю order by title asc, то будет так:

Код:
аа
    а_в
бб
    б_в
вв
есть идеи как получить валидный лист сразу из базы? или придеться перед выводом еще раз все сортировать?

p.s. при рекурсивном алгоритме можно получить такой список сразу...

Sheryld 02.02.2005 23:06
запросом такую штуку не сделать.

p.s. и это только начало:) попробуйте на досуге сделать методы движения нодов вверх-вниз, полный путь и т.д.

Цитата:
про nested sets я знаю. но не хочу его применять, т.к. в этом проекте он не нужен, а там много времени уйдет на реализацию...

Sheryld 04.02.2005 17:03
начал портировать класс dbtree для своих нужд. если кому интересно:

mysql helper class:
Код:
<?php
///////////////////////////////
// Description: ClassHelper for Mysql
// Author: Denis 'Sherman' Gabaidulin © 2002-2004
// Version: 0.3.3 alpha-test(global version 2)
// Comments: __________________
///////////////////////////////
////////////////////////////////////////////////////////
// +added mysql_num_rows check for result
////////////////////////////////////////////////////////
        class MySql
        {
                var $dbServer = "";
                var $dbName = "";
                var $dbUser = "";
                var $dbPass = "";
                       
                var $dbConn;
                var $dbResult;
               
                var $dbErrorNumber = 0;
                var $dbErrorMessage = "";
               
                var $debugFromHanlder = "";
               
                /*function MySql()
                {
                        //default constructor
                       
                }*/
               
                function MySql($dbServer = null, $dbName = null, $dbUser = null, $dbPass = null)
                {
                        //default constructor
                        if ($dbServer != null)
                        {
                                $this->dbServer = $dbServer;
                        }
                        if ($dbName != null)
                        {
                                $this->dbName = $dbName;
                        }
                        if ($dbUser != null)
                        {
                                $this->dbUser = $dbUser;
                        }
                        if ($dbPass != null)
                        {
                                $this->dbPass = $dbPass;                                       
                        }
                }
                function MySql_Connect()
                {
                        if (!isset($this->dbConn) || $this->dbConn == null)
                        {
                                $this->dbConn = @mysql_connect(
                                        $this->dbServer,
                                        $this->dbUser,
                                        $this->dbPass);
                                       
                                $this->MySql_ErrorHanlder("connect");
                        }
                }
                function MySql_SelectDb()
                {
                        if (isset($this->dbName) && $this->dbName != null)
                        {
                                @mysql_select_db($this->dbName,$this->dbConn);
                               
                                $this->MySql_ErrorHanlder("select");
                        }
                }
                function MySql_QueryDb($dbQuery)
                {
                        if (isset($dbQuery) && $dbQuery != null)
                        {
                                $this->dbResult = @mysql_query($dbQuery,$this->dbConn);
                                //echo $dbQuery;
                                $this->MySql_ErrorHanlder("query");
                               
                                if (@mysql_num_rows($this->dbResult) == 0)                               
                                {
                                        $this->dbResult=null;
                                }
                        }
                }
                function MySql_Close()
                {
                        if (isset($this->dbConn) && $this->dbConn != null)
                        {
                                @mysql_close($this->dbConn);
                               
                                $this->MySql_ErrorHanlder("close");
                               
                        }
                       
                }
                function MySql_Free()
                {
                        @mysql_free($this->dbResult);
                       
                        $this->MySql_ErrorHanlder("free");
                }
                function MySql_ErrorHanlder($debugFromHanlder)
                {
                        $this->dbErrorNumber = mysql_errno();       
                        $this->dbErrorMessage = mysql_error();
                       
                        if ($this->dbErrorNumber != 0)
                        {
                                echo $this->dbErrorNumber . "    " . $this->dbErrorMessage;
                                echo "    " . $debugFromHanlder . "<BR>\r\n";
                                die;
                        }
                        /*if ($this->dbErrorNumber == 2003)
                        {
                                sleep(2);
                        }*/
                       
                        $this->dbErrorNumber = 0;
                        $this->dbErrorMessage = "";
                }       
        }

?>
Table
Код:
CREATE TABLE categories (
  cat_ID int(10) unsigned NOT NULL auto_increment,
  cat_LEFT int(10) unsigned NOT NULL default '0',
  cat_RIGHT int(10) unsigned NOT NULL default '0',
  cat_LEVEL int(10) unsigned NOT NULL default '0',
  cat_TITLE varchar(255) default NULL,
  cat_CREATION_DATE timestamp(14) NOT NULL,
  cat_MODIFY_DATE timestamp(14) NOT NULL,
  cat_DESC text NOT NULL,
  cat_PHOTO_PATH text,
  PRIMARY KEY  (cat_ID),
  KEY cat_left (cat_LEFT,cat_RIGHT,cat_LEVEL)
) TYPE=MyISAM;
Это пока еще рыба:
Код:
require_once $DOCUMENT_ROOT . "/sherman/classes/mysql.inc";
       
        // nested sets implementation(by Sherman)
       
        // based on "dbtree" class
        // Author: Maxim Poltarak  <maxx at e dash taller dot net>
        // WWW: http://dev.e-taller.net/dbtree/
       
        class Category2
        {
                var $nodeInfo = array(
                "id"=>0,
                "left"=>0,
                "right"=>0,
                "level"=>0,
                "data"=>array(
                                        "title"=>"",
                                        "creation_date"=>0,
                                        "modify_date"=>0,
                                        "desc"=>"",
                                        "photo"=>""));
                                       
                var $nodeInfoCollection = array();
                                               
                function getNodeInfo($categoryID)
                {
                        $db = new MySql(null,"mport4",null,null);
                        $db->MySql_Connect();
                        $db->MySql_SelectDb();
                       
                        $selectQuery = "select *
                        from categories where cat_ID = " . $categoryID;
                       
                        $db->MySql_QueryDb($selectQuery);
                       
                        if ($db->dbResult != null)
                        {
                                while($row = mysql_fetch_assoc($db->dbResult))
                                {
                                        $this->nodeInfo["id"] = $row["cat_ID"];
                                        $this->nodeInfo["left"] = $row["cat_LEFT"];
                                        $this->nodeInfo["right"] = $row["cat_RIGHT"];
                                        $this->nodeInfo["level"] = $row["cat_LEVEL"];
                                        $this->nodeInfo["data"]["title"] = $row["cat_TITLE"];
                                        $this->nodeInfo["data"]["creation_date"] = $row["cat_CREATION_DATE"];
                                        $this->nodeInfo["data"]["modify_date"] = $row["cat_MODIFY_DATE"];
                                        $this->nodeInfo["data"]["desc"] = $row["cat_DESC"];
                                        $this->nodeInfo["data"]["photo"] = $row["cat_PHOTO_PATH"];                                                                                                                                       
                                }
                                return 0;
                        }
                        return -1;
                }
                function enumChildren($categoryID, $startLevel=1, $endLevel=1, $order=null)
                {
                        $orderExpression = "";
                       
                        if($startLevel < 0)
                        {
                                return -1;
                        }
                       
                        if ($order != null)
                        {
                                $orderExpression = " order by " . $order;
                        }
                       
                        // We could use sprintf() here, but it'd be too slow
                        $whereSql1 = " and categories.cat_LEVEL";
                        $whereSql2 = '_categories.cat_LEVEL+';
                       
                        if (!$endLevel)
                        {
                                $whereSql = $whereSql1 . ">=" . $whereSql2 . (int)$startLevel;
                        }
                        else
                        {
                                $whereSql = ($endLevel <= $startLevel)
                                ? $whereSql1.'='.$whereSql2.(int)$startLevel
                                : ' and categories.cat_LEVEL between _categories.cat_LEVEL+'.(int)$startLevel
                                        .' and _categories.cat_LEVEL+'.(int)$endLevel;
                        }

                        $selectQuery = "select categories.*
                        from categories _categories, categories
                        where _categories.cat_ID = " . $categoryID .
                        " and categories.cat_LEFT between _categories.cat_LEFT and _categories.cat_RIGHT" .
                        $whereSql . $orderExpression;
                       
                        $db = new MySql(null,"mport4",null,null);
                        $db->MySql_Connect();
                        $db->MySql_SelectDb();
                       
                        $db->MySql_QueryDb($selectQuery);
                       
                        if ($db->dbResult != null)
                        {
                                while($row = mysql_fetch_assoc($db->dbResult))
                                {
                                        $this->nodeInfo["id"] = $row["cat_ID"];
                                        $this->nodeInfo["left"] = $row["cat_LEFT"];
                                        $this->nodeInfo["right"] = $row["cat_RIGHT"];
                                        $this->nodeInfo["level"] = $row["cat_LEVEL"];
                                        $this->nodeInfo["data"]["title"] = $row["cat_TITLE"];
                                        $this->nodeInfo["data"]["creation_date"] = $row["cat_CREATION_DATE"];
                                        $this->nodeInfo["data"]["modify_date"] = $row["cat_MODIFY_DATE"];
                                        $this->nodeInfo["data"]["desc"] = $row["cat_DESC"];
                                        $this->nodeInfo["data"]["photo"] = $row["cat_PHOTO_PATH"];                                                                                                                                       
                                       
                                        $this->nodeInfoCollection[] = $this->nodeInfo;
                                }
                                return 0;
                        }
                        return -1;
                }
                function EnumChildrenAll($categoryParentID)
                {
                        return $this->enumChildren($categoryParentID, 1, 0);
                }
                function insertNode($categoryParentID, $nodeInfoData)
                {
                        //get node info
                        if ($this->getNodeInfo($categoryParentID) != 0)
                        {
                                return -1;
                        }
               
                // creating a place for the record being inserted
                        if($categoryParentID)
                        {
                                $updateQuery = "update categories
                                set cat_LEFT=if(cat_LEFT>" . (int)$this->nodeInfo["right"] . ",cat_LEFT+2,cat_LEFT),"
                                        . "cat_RIGHT=if(cat_RIGHT>=" .(int)$this->nodeInfo["right"] . ",cat_RIGHT+2,cat_RIGHT)"
                                        . "where cat_RIGHT>=" . (int)$this->nodeInfo["right"];
                               
                                $db = new MySql(null, "mport4", null, null);
                                $db->MySql_Connect();
                                $db->MySql_SelectDb();
                               
                                $db->MySql_QueryDb($updateQuery);
                               
                                //echo $updateQuery . "<BR>";
                               
                                if (mysql_affected_rows($db->dbConn) > 0) //need to fix?
                                {
                                        //echo mysql_affected_rows();
                                        // inserting new record
                                        $insertQuery = "insert into categories
                                        (cat_LEFT, cat_RIGHT, cat_LEVEL,
                                        cat_TITLE,  cat_CREATION_DATE,
                                        cat_MODIFY_DATE,  cat_DESC, 
                                        cat_PHOTO_PATH)
                                        values(" .
                                        (int)$this->nodeInfo["right"] . "," .
                                        (int)($this->nodeInfo["right"]+1) . "," .
                                        (int)($this->nodeInfo["level"]+1) . ",'" .
                                        $nodeInfoData["title"] . "'," .
                                        (int)time() . "," .
                                        (int)time() . ",'" .
                                        $nodeInfoData["desc"] . "','" .
                                        $nodeInfoData["photo"] . "')";
                                       
                                        //echo $insertQuery . "<BR>";
                                       
                                        $db = new MySql(null, "mport4", null, null);
                                        $db->MySql_Connect();
                                        $db->MySql_SelectDb();
                               
                                        $db->MySql_QueryDb($insertQuery);
                                       
                                        if (mysql_affected_rows($db->dbConn) > 0)
                                        {
                                                //echo mysql_affected_rows();
                                                return 0;
                                        }
                                }
                        }
                        return -1;
                }
        }
?>
желательно все бы делать в транзакциях, но где их взять-то?:( на mysql 3.23.58 --no-innodb

еще один метод(удаляет ветку):

Код:
function deleteAll($categoryID)
                {
                        //get node info
                        if ($this->getNodeInfo($categoryID) != 0)
                        {
                                return -1;
                        }
                       
                        $db = new MySql(null, "mport4", null, null);
                        $db->MySql_Connect();
                        $db->MySql_SelectDb();
                       
                        // Deleteing record(s)
                        $deleteQuery = "DELETE FROM categories
                        WHERE cat_LEFT BETWEEN "
                        .(int)$this->nodeInfo["left"] .
                        " AND " .(int)$this->nodeInfo["right"];
                       
                        //echo $deleteQuery;
                       
                        $db->MySql_QueryDb($deleteQuery);
                       
                        if (mysql_affected_rows($db->dbConn) > 0)
                        {
                                // Clearing blank spaces in a tree
                                $deltaID = ((int)$this->nodeInfo["right"] - (int)$this->nodeInfo["left"])+1;
                               
                                $updateQuery = 'UPDATE categories SET
                                cat_LEFT=IF(cat_LEFT>'.(int)$this->nodeInfo["left"].',cat_LEFT-'.$deltaID.',cat_LEFT),
                                cat_RIGHT=IF(cat_RIGHT>'.$this->nodeInfo["left"].',cat_RIGHT-'.$deltaID.',cat_RIGHT)
                                WHERE cat_RIGHT>'.(int)$this->nodeInfo["right"];
                               
                                //echo $updateQuery;
                               
                                $db = new MySql(null, "mport4", null, null);
                                $db->MySql_Connect();
                                $db->MySql_SelectDb();
                               
                                $db->MySql_QueryDb($updateQuery);
                               
                                if (mysql_affected_rows($db->dbConn) > 0)
                                {
                                        return 0;
                                }                       
                        }       
                        return -1;                                       
                }

Sheryld 07.02.2005 12:21
метод для нахождения родительской категории:

Код:
function getParent($categoryID, $level=1)
                {
                        if($level < 1)
                        {
                                return -1;
                        }
                       
                        $db = new MySql(null, "mport4", null, null);
                        $db->MySql_Connect();
                        $db->MySql_SelectDb();
                       
                        $selectQuery = "select * from categories  _categories, categories
                                        where _categories.cat_ID=" .$categoryID .
                                        " AND _categories.cat_LEFT BETWEEN categories.cat_LEFT and categories.cat_RIGHT" .
                                        " AND categories.cat_LEVEL=_categories.cat_LEVEL-" . (int)$level;
                       
                        $db->MySql_QueryDb($selectQuery);
                       
                        if ($db->dbResult != null)
                        {
                                while($row = mysql_fetch_assoc($db->dbResult))
                                {
                                        $this->nodeInfo["id"] = $row["cat_ID"];
                                        $this->nodeInfo["left"] = $row["cat_LEFT"];
                                        $this->nodeInfo["right"] = $row["cat_RIGHT"];
                                        $this->nodeInfo["level"] = $row["cat_LEVEL"];
                                        $this->nodeInfo["data"]["title"] = $row["cat_TITLE"];
                                        $this->nodeInfo["data"]["creation_date"] = $row["cat_CREATION_DATE"];
                                        $this->nodeInfo["data"]["modify_date"] = $row["cat_MODIFY_DATE"];
                                        $this->nodeInfo["data"]["desc"] = $row["cat_DESC"];
                                        $this->nodeInfo["data"]["photo"] = $row["cat_PHOTO_PATH"];
                                }
                                return 0;
                        }       
                        return -1;
                }

Sheryld 09.02.2005 12:17
метод переноса ветки(смена родителя).

Код:
function updateNode($categoryID, $newCategoryParentID, $nodeInfoData)
                {
                        $db = new MySql(null,"mport4",null,null);
                        $db->MySql_Connect();
                        $db->MySql_SelectDb();
                       
                        $updateQuery = "update categories
                                        set cat_TITLE='" . $nodeInfoData["title"] . "',
                                        cat_MODIFY_DATE=" . time() . ",
                                        cat_DESC='" . $nodeInfoData["desc"] . "', 
                                        cat_PHOTO_PATH='" .$nodeInfoData["photo"] . "'
                                        where cat_ID = " . $categoryID;
                       
                        $db->MySql_QueryDb($updateQuery);
                       
                        if (mysql_affected_rows() >= 0)
                        {
                                //update tree hierarchy
                                if ($categoryID == $newCategoryParentID)
                                {
                                        //no need update
                                        return 0;
                                }
                               
                                //get nodeInfo
                                if ($this->getNodeInfo($categoryID) != 0)
                                {
                                        return -1;
                                }
                               
                                //get newParentNodeInfo
                                $categoryObj = new Category2();
                                if ($categoryObj->getNodeInfo($newCategoryParentID) != null)
                                {
                                        return -1;
                                }
       
                                //checks
                                //get parentcat for node
                                $parentCategoryObj = new Category2();
                                if ($parentCategoryObj->getParent($this->nodeInfo["id"]) != 0)
                                {
                                        return -1;
                                }
                               
                                //if parentcat = "newparentcat"
                                if ($newCategoryParentID == $parentCategoryObj->nodeInfo["id"])
                                {
                                        //no need update
                                        return 0;
                                }

                                // whether it is being moved upwards along the path
                                if ($categoryObj->nodeInfo["left"] < $this->nodeInfo["left"] && $categoryObj->nodeInfo["right"] > $this->nodeInfo["right"] && $categoryObj->nodeInfo["level"] < $this->nodeInfo["level"] - 1 )
                                {
                                        $updateTreeQuery = 'UPDATE categories SET
                                        cat_LEVEL=IF(cat_LEFT BETWEEN '. $this->nodeInfo["left"] .' AND '.$this->nodeInfo["right"].', cat_LEVEL' . sprintf('%+d', -($this->nodeInfo["level"]-1)+$categoryObj->nodeInfo["level"]).', cat_LEVEL), '
                                        . 'cat_RIGHT=IF(cat_RIGHT BETWEEN '.($this->nodeInfo["right"]+1).' AND '.($categoryObj->nodeInfo["right"]-1).', cat_RIGHT-'.($this->nodeInfo["right"]-$this->nodeInfo["left"]+1).', '
                                        .'IF(cat_LEFT BETWEEN '.($this->nodeInfo["left"]).' AND '.($this->nodeInfo["right"]).', cat_RIGHT+'.((($categoryObj->nodeInfo["right"]-$this->nodeInfo["right"]-$this->nodeInfo["level"]+$categoryObj->nodeInfo["level"])/2)*2 + $this->nodeInfo["level"] - $categoryObj->nodeInfo["level"] - 1).', cat_RIGHT)),  '
                                        . 'cat_LEFT=IF(cat_LEFT BETWEEN '.($this->nodeInfo["right"]+1).' AND '.($categoryObj->nodeInfo["right"]-1).', cat_LEFT-'.($this->nodeInfo["right"]-$this->nodeInfo["left"]+1).', '
                                        .'IF(cat_LEFT BETWEEN '.$this->nodeInfo["left"].' AND '.($this->nodeInfo["right"]).', cat_LEFT+'.((($categoryObj->nodeInfo["right"]-$this->nodeInfo["right"]-$this->nodeInfo["level"]+$categoryObj->nodeInfo["level"])/2)*2 + $this->nodeInfo["level"] - $categoryObj->nodeInfo["level"] - 1).', cat_LEFT)) '
                                        . 'WHERE cat_LEFT BETWEEN '.($categoryObj->nodeInfo["left"]+1).' AND '.($categoryObj->nodeInfo["right"]-1);
                                }
                                elseif($categoryObj->nodeInfo["left"] < $this->nodeInfo["left"])
                                {
                                        $updateTreeQuery = 'UPDATE categories SET '
                                        . 'cat_LEVEL=IF(cat_LEFT BETWEEN '. $this->nodeInfo["left"].' AND '.$this->nodeInfo["right"].', cat_LEVEL'.sprintf('%+d', -((int)$this->nodeInfo["level"]-1)+(int)$categoryObj->nodeInfo["level"]).', cat_LEVEL), '
                                        . 'cat_LEFT=IF(cat_LEFT BETWEEN '.$categoryObj->nodeInfo["right"].' AND '.($this->nodeInfo["left"]-1).', cat_LEFT+'.((int)$this->nodeInfo["right"]-(int)$this->nodeInfo["left"]+1).', '
                                        . 'IF(cat_LEFT BETWEEN '. $this->nodeInfo["left"].' AND '.$this->nodeInfo["right"].', cat_LEFT-'.( $this->nodeInfo["left"]-$categoryObj->nodeInfo["right"]).', cat_LEFT) '
                                        . '), '
                                        . 'cat_RIGHT=IF(cat_RIGHT BETWEEN '.$categoryObj->nodeInfo["right"].' AND '.$this->nodeInfo["left"].', cat_RIGHT+'.($this->nodeInfo["right"]-$this->nodeInfo["left"]+1).', '
                                        . 'IF(cat_RIGHT BETWEEN '.$this->nodeInfo["left"].' AND '.$this->nodeInfo["right"].', cat_RIGHT-'.((int)$this->nodeInfo["left"]-(int)$categoryObj->nodeInfo["right"]).', cat_RIGHT) '
                                        . ') '
                                        . 'WHERE cat_LEFT BETWEEN '.$categoryObj->nodeInfo["left"].' AND '.$this->nodeInfo["right"]
                                        // !!! added this line (Maxim Matyukhin)
                                        .' OR cat_RIGHT BETWEEN '.$categoryObj->nodeInfo["left"].' AND '.$this->nodeInfo["right"];

                                }
                                else
                                {
                                        $updateTreeQuery = 'UPDATE categories SET '
                                        . 'cat_LEVEL=IF(cat_LEFT BETWEEN '.$this->nodeInfo["left"].' AND '.$this->nodeInfo["right"].', cat_LEVEL'.sprintf('%+d', -($this->nodeInfo["level"]-1)+$categoryObj->nodeInfo["level"]).', cat_LEVEL), '
                                        . 'cat_LEFT=IF(cat_LEFT BETWEEN '.$this->nodeInfo["right"].' AND '.$categoryObj->nodeInfo["right"].', cat_LEFT-'.($this->nodeInfo["right"]-$this->nodeInfo["left"]+1).', '
                                        . 'IF(cat_LEFT BETWEEN '.$this->nodeInfo["left"].' AND '.$this->nodeInfo["right"].', cat_LEFT+'.($categoryObj->nodeInfo["right"]-1-$this->nodeInfo["right"]).', cat_LEFT)'
                                        . '), '
                                        . 'cat_RIGHT=IF(cat_RIGHT BETWEEN '.($this->nodeInfo["right"]+1).' AND '.($categoryObj->nodeInfo["right"]-1).', cat_RIGHT-'.($this->nodeInfo["right"]-$this->nodeInfo["left"]+1).', '
                                        . 'IF(cat_RIGHT BETWEEN '.$this->nodeInfo["left"].' AND '.$this->nodeInfo["right"].', cat_RIGHT+'.($categoryObj->nodeInfo["right"]-1-$this->nodeInfo["right"]).', cat_RIGHT) '
                                        . ') '
                                        . 'WHERE cat_LEFT BETWEEN '.$this->nodeInfo["left"].' AND '.$categoryObj->nodeInfo["right"]
                                        // !!! added this line (Maxim Matyukhin)
                                        . ' OR cat_RIGHT BETWEEN '.$this->nodeInfo["left"].' AND '.$categoryObj->nodeInfo["right"]
                                        ;
                                }
                               
                                $db->MySql_QueryDb($updateTreeQuery);
                       
                                if (mysql_affected_rows() > 0)
                                {
                                        return 0;
                                }
                               
                        }
                        return -1;
                                       
                }

Sheryld 10.02.2005 14:50
найти весь путь от корня до категории:
Код:
function enumPath($categoryID, $showRoot=false)
                {
                        $db = new MySql(null, "mport4", null, null);
                        $db->MySql_Connect();
                        $db->MySql_SelectDb();
                       
                        $selectQuery = "select * from categories  _categories, categories
                                        where _categories.cat_ID=" .$categoryID .
                                        " AND _categories.cat_LEFT BETWEEN categories.cat_LEFT and categories.cat_RIGHT";
                                       
                       
                        if ($showRoot == false)
                        {
                                $selectQuery .= ' AND categories.cat_LEVEL>0 order by categories.cat_LEFT';
                        }       
                                       
                        $db->MySql_QueryDb($selectQuery);
                       
                        //echo $selectQuery;
                       
                        if ($db->dbResult != null)
                        {
                                while($row = mysql_fetch_assoc($db->dbResult))
                                {
                                        $this->nodeInfo["id"] = $row["cat_ID"];
                                        $this->nodeInfo["left"] = $row["cat_LEFT"];
                                        $this->nodeInfo["right"] = $row["cat_RIGHT"];
                                        $this->nodeInfo["level"] = $row["cat_LEVEL"];
                                        $this->nodeInfo["data"]["title"] = $row["cat_TITLE"];
                                        $this->nodeInfo["data"]["creation_date"] = $row["cat_CREATION_DATE"];
                                        $this->nodeInfo["data"]["modify_date"] = $row["cat_MODIFY_DATE"];
                                        $this->nodeInfo["data"]["desc"] = $row["cat_DESC"];
                                        $this->nodeInfo["data"]["photo"] = $row["cat_PHOTO_PATH"];
                                       
                                        $this->nodeInfoCollection[] = $this->nodeInfo;
                                }
                                return 0;
                        }       
                        return -1;
                }

Sheryld 11.02.2005 12:39
метод для проверки целостности таблицы дерева(не оптимизирован):

Код:
function checkTree()
                {
                        $db = new MySql(null, "mport4", null, null);
                        $db->MySql_Connect();
                        $db->MySql_SelectDb();
                       
                        //left key always less then right key
                        $selectQuery = "select cat_ID from categories 
                                        where cat_LEFT >= cat_RIGHT";
                       
                        $db->MySql_QueryDb($selectQuery);
                       
                        if ($db->dbResult != null)
                        {
                                $this->errors[] = "Левый ключ всегда меньше правого ключа.";
                                //echo "error 1";
                                //return -1;
                        }
                       
                        //smallest key always equal 1 and biggest key always equal 2*n-elemetns
                        $selectQuery = "SELECT min( cat_LEFT )
                        as minKey, max( cat_RIGHT )
                        as maxKey, count( * )
                        as nElements
                        FROM categories";
                       
                        $db->MySql_QueryDb($selectQuery);
                       
                        if ($db->dbResult != null)
                        {
                                while($row = mysql_fetch_assoc($db->dbResult))
                                {                               
                                        if ($row["minKey"] != 1 || ($row["maxKey"] % $row["nElements"]) != 0)
                                        {
                                                $this->errors[] = "Ключи корневой ветки неправильные.";
                                        }
                                }                               
                        }
                       
                        // cat_RIGHT-cat_LEFT/2 always not equal 0
                        $selectQuery = "SELECT mod(cat_RIGHT-cat_LEFT,2) as os
                        FROM `categories`
                        GROUP BY cat_ID
                        HAVING os = 0";
                       
                        $db->MySql_QueryDb($selectQuery);
                       
                        if ($db->dbResult != null)
                        {
                                $this->errors[] = "Разница между правым и левым ключами должна быть отрицательна.";
                        }
                       
                        //need fix?
                        $selectQuery = "SELECT mod((cat_LEFT-cat_LEVEL+2),2) as os
                        FROM categories
                        HAVING os = 0";
                       
                        $db->MySql_QueryDb($selectQuery);
                       
                        if ($db->dbResult != null)
                        {
                                $this->errors[] = "Ошибка 4.";
                        }
                       
                        //all keys must be unique
                        $keys = array();
                       
                        $selectQuery = "SELECT cat_LEFT, cat_RIGHT
                        FROM categories";

                        $db->MySql_QueryDb($selectQuery);
                       
                        if ($db->dbResult != null)
                        {
                                while($row = mysql_fetch_assoc($db->dbResult))
                                {
                                        $keys[] = $row["cat_LEFT"];
                                        $keys[] = $row["cat_RIGHT"];
                                }
                                //return "error 5";
                        }
                       
                        //$keys[] = 1;
                       
                        if ($keys !== array_unique($keys))
                        {
                                $this->errors[] = "Все ключи должны быть уникальны.";
                        }
                       
                        if (!empty($this->errors))
                        {
                                return -1;
                        }
                        return 0;
                }

Sheryld 16.03.2005 22:26
вобщем, резюмирую.

для реальных приложений база данных mysql версии 3.23.x(в моем случае еще и без innodb) подходит очень плохо.

сейчас почти доделал каталог:

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

т.е. почти везде идет отношение «многие ко многим». а в mysql этой версии(впрочем и в 4.x) невозможно создать струкутру, которая будет поддерживать сама себя.

рассмотрим сценарий удаления категории:

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

если бы имелась в наличии нормальная СУБД, то многие вещи можно было бы сделать автоматически(каскадное удаление+триггеры).

а теперь прикиньте код на php, и причем если что-то где-то пойдет не так, то транзакции нету:)

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

кроме того, объем кода, обслуживающий всю эту систему уже сотни килобайт:) не считая административного интерфейса и вывода:)

p.s. а теперь представьте, что происходит при смене родительской категории:)
p.p.s. а многие вещи, которые задумывались, мне не удалось реализовать в принципе:(

========================================================

Кстати вот еще вопрос. Заказчик хочет, чтобы пути выглядели так:

/catalog/phone/nokia/
/catalog/phone/nokia/7800/ - последнее это уже позиция а не категория
/catalog/food/fastfood/mcdonalds/
/catalog/food/fastfood/mcdonalds/gamburger/ - последнее это уже позиция а не категория

Написал pathFinder. алгоритм(только для категорий):

всю цепочку загоняем в массив.
находим последний элемент в цепочке.
по имени последнего элемента, получаем id(их может быть несколько, т.к. может быть вот так:
/catalog/kpk/rover/
/catalog/phone/rover/
далее находим все пути и в цикле сравниваем, как только нахоим нужный путь, выходим.

вопрос:

можно ли сделать что-то с помощью mode_rewrite?
или может выгоднее завести таблицу aliases и там хранить все привязки, т.к. находить id категории и сразу проверять?

к сожалению такой вариант:

category.html?catid=id

не возможен:(

Hubbitus 17.03.2005 14:11
Цитата:
Sheryld:
можно ли сделать что-то с помощью mode_rewrite?
или может выгоднее завести таблицу aliases и там хранить все привязки, т.к. находить id категории и сразу проверять?

к сожалению такой вариант:

category.html?catid=id

не возможен
Ну можно конечно с помощью mod_rewrite переадресовывать пути вида /catalog/phone/rover/ на category.html?catid=id&subcatid=1

is_absent 18.03.2005 05:27
ну методы доступа мягко говоря не отпимизированы. большинство из них можно свести к двум, максимум трем запросам. Не так давно я этим и занимался. Например поиск пути это всего один запрос... вывод детей - тоже... ну и так далее. Если будет желание - обсудим.
Интересно послушать, какие задачи не реализуются в такой идеологии...

Sheryld 18.03.2005 11:03
а там и есть один запрос:

enumPath, enumChildren.

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

про оптимизацию запросов тоже интересно.

я написал, что задачи не реализуются не в идеологии, а в конкретных инстурментах.

p.s. Celko в своей статье про вложенные множества в sql вовсю пользуется хранимыми процеурами, подзапросами, триггерами и т.д. у нас же(mysql) много до сих пор так и нет:(
я просто написал свои впечатления о использовании этой модели в реальном приложении, на конкретных инструментах.

p.p.s. версия mysql 3.23.58.

is_absent 18.03.2005 11:19
Цитата:
Sheryld:
интересно было бы услышать про сортировку. т.е. как реализовать вывод полностью остортированного дерева, или лучше сразу вставлять категорию на «нужное место»? тогда нужно менять алгоритм по-идее.
так а поле left тебе зачем???? вот она тебе сортировка. сразу. или я что-то не понял.

Sheryld 18.03.2005 11:43
не. попробуй вывести такое дерево в алфавитной сортировке:)

типа:

Код:
аа
  аа
  бб
    аа
    пп
  цц
бб
ии
 пп
кк
тут есть два способа:

1. сортировать при выводе.
2. вставлять в «правильную позицию» сразу.

is_absent 18.03.2005 11:54
это проблема реализации. как правило всегда при выводе списков нужно иметь несколько вариантов сортировке.
решение 1. оставить на совести менеджера контента
решение 2. написать небольшой класс сортировщик. и наследовать от него по мере надобности новые види сортировок. при этом у менеджера будет кнопочка (ссылочка, выпадающий список и т.п.) которая и будет это делать.

имхо полезней второе.

Sheryld 18.03.2005 12:10
а не подскажешь алгоритм сортировки моего списка:

1 узел дерева, сортировка нужна по nodeItem["data"][desc"]:
Код:
var $nodeInfo = array(
                "id"=>0,
                "left"=>0,
                "right"=>0,
                "level"=>0,
                "data"=>array(
                                        "title"=>"",
                                        "creation_date"=>0,
                                        "modify_date"=>0,
                                        "desc"=>"",
                                        "photo"=>""));
коллекция:

массив узлов дерева.

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

а вот как быть тут — хз.

is_absent 18.03.2005 12:18
в твоем случае очень удобно сортировать по полю left. Оно по построению дерева является индексом сортировки. вот его и нужно изменять.

Ну а дальше хоть пузырьком, хоть бинарным )

Базовый алгоритм (который собственно сортирует) один и тот же всегда.
Определись, какой для тебя лучше подходит (в списке альтернатив есть и usort() :-)). Метод сравнения - в зависимости от типа сортировки.

Sheryld 18.03.2005 15:00
по left у меня и так выводится. но если отстортировать все после по desc, то нарушается структура. пока что решения не придумал :(

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

Sheryld 18.03.2005 18:38
можно еще как вариант, просатвить сначала всех родителей, а потом сразу выводить рекусривной функцией. но это решение в лоб. думаю попозже все-таки реализую функцию вставки ветви на в конкретное место, чтобы хранить дерево уже отсортированным.

решение:

Код:
$catObj = new Category2();
       
$catObj->EnumChildrenAll(1,"cat_LEFT");

$startTime = microtime();
       
        $nodes = array();
        $prevID = 0;
        $numElements = count($catObj->nodeInfoCollection);
        for($i<0;$i<$numElements;$i++)
        {
                if ($catObj->nodeInfoCollection[$i]["level"] != $prevLevel)
                {
                        if ($catObj->nodeInfoCollection[$i]["level"] == 1)
                        {
                                $catObj->nodeInfoCollection[$i]["parent_id"] = 1;
                        }
                        else
                        {
                                $catObj->nodeInfoCollection[$i]["parent_id"] = $prevID;
                        }
                        $prevID = $catObj->nodeInfoCollection[$i]["id"];                                       
                }
                else
                {
                       
                        $catObj->nodeInfoCollection[$i]["parent_id"] = $catObj->nodeInfoCollection[$i-1]["parent_id"];
                }
               
                $prevLevel = $catObj->nodeInfoCollection[$i]["level"];               
        }
       
        function cmp($a,$b)
        {
                return strcmp($a["data"]["desc"],$b["data"]["desc"]);
        }
       
        function getChild($parentid, $array)
        {
                $retArray = array();
                foreach($array as $arrayItem)
                {
                        if ($arrayItem["parent_id"] == $parentid)
                        {                               
                                $retArray[] = $arrayItem;
                        }
                }
                usort($retArray, "cmp");       
                return $retArray;
        }
       
        function walk($root, $collection)
        {
                //global $nodes;
                $ret = getChild($root,$collection);
                if (!empty($ret))
                {
                        for($i=0;$i<count($ret);$i++)
                        {
                                echo str_repeat("&nbsp;", 4*$ret[$i]["level"]);
                                echo $ret[$i]["data"]["desc"];
                                echo "  <b>" . $ret[$i]["id"] . "</b>";
                                echo "  <b>" . $ret[$i]["parent_id"] . "</b>";
                                echo "<BR>";
                                walk($ret[$i]["id"],$collection);
                        }
                }
        }
       
        walk(1,$catObj->nodeInfoCollection);
       
        echo number_format(microtime() - $startTime,4);
оговорки, работает довольно медленно на больших объемах. не оптимизировано.

is_absent 19.03.2005 08:11
Цитата:
Sheryld:
по left у меня и так выводится. но если отстортировать все после по desc, то нарушается структура. пока что решения не придумал

все что у меня получилось это отсортировать ноды на каждом уровне, но собрать их снова в дерево не получается.
ты должен изменять left и right при сортировке. То есть дерево сортируется сразу. когда ты это будешь делать - при вставке или потом отдельным методом дело десятое. главное правило в этом случае -- любая сортиврока основана на том, что нужно менять left и right поля узла.
Понятно что это довольно утомительный процесс.. хотя после некоторых размышлений, можно увидеть, что достаточно будет N запросов при сортировке. можно конечно один с кучей if-ов, но на мой взгляд это будет медленней.
Теперь второй момент. кто тебе мешает при выводе дерева пересортировать его как тебе нужно? тогда не нужно будет никаких доп. запросов. но в этом случае пропадает т.н. обобщенность, то есть нужно будет писать кучу классов-сортировщиков (для каждой отдельной сортировки)... но не будет большого количества запросов.

Sheryld 19.03.2005 13:01
в моем случае целесообразнее хранить отсортированное дерево, т.к. запросов на добавление и изменение категорий в разы меньше, чем запросов на вывод.

про left и right понятно:) но алгоритм пока еще мне в голову не пришел.

в моем примере сортировка организована как раз после запроса. т.е. сначала идет выборка всего дерева, отсортированного по left. затем идет простановка цепочки parent-child. и затем уже на каждом уровне идет сортировка(рекурсия) по алфавиту.

имхо, если делать возможность хранения отсортированного дерева по n-полям(т.е. по любому полю), тогда нужно просто завести отдельную таблицу(или даже n-таблиц) и в ней хранить порядок. а запросы будут вида:

Код:
select t.* from myOrderTable as o inner join myTreeTable as t in
o.id = t.id
order by o.order
а каждый раз менять left и right это накладно.

is_absent 19.03.2005 22:53
1. order by left, o.order (иначе стуктура слетит)
2. а если нужно по нескольким полям сортировать?


Часовой пояс GMT +4, время: 14:01.
Страница 1 из 2 1 2
Показывать 40 сообщений этой темы на одной странице

Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.