Поиск всех детей по дереву

niko42 · 25 Июн 2014

Мой алгоритма на примере объекта Категории:

PHP:

    /**
     * @see Возвращает ID всех детей родительской категории
     * @param array(application\lib\Category) $category //массив категорий
     * @param int $point //ID категории у которой требуется найти всех детей
     * @return array(int)
     */
    public static function childrenIdByCategory(array $category, $point){
        $arr = array();
        foreach($category as $v){/** @var \application\lib\Category $v */
            $arr[$v->getParentId()][] = $v;
        }

        if(empty($arr[$point]))
            return array($point);

        $value = array($point);
        $tmp = array($point);
        $tmps = array();
        for(;;){
            if(!empty($tmp))
                foreach($tmp as $t){
                    if(!empty($arr[$t])){
                        foreach($arr[$t] as $v){
                            $tmps[] = $v->getId();
                            $value[] = $v->getId();
                        }
                    } 
                    $tmp = $tmps;
                    $tmps = null;
                }
            else{
                break;
            }
        }

        return $value;
    }

c0dex · 25 Июн 2014

Что это?

niko42 · 25 Июн 2014

c0dex написал(а):
Что это?

Обход дерево

c0dex · 25 Июн 2014

Мой алгоритма на примере объекта Категории:

Обход дерево

Ну так а вопрос то где? Я не понимаю зачем перебирать все данные в цикле, если это можно сделать на SQL 1 запросом, у тебя данные то в нем ведь лежат?

niko42 · 25 Июн 2014

c0dex написал(а):
Ну так а вопрос то где? Я не понимаю зачем перебирать все данные в цикле, если это можно сделать на SQL 1 запросом, у тебя данные то в нем ведь лежат?

Нет, у меня один запрос на все категории SQLCategory->getAll();
SELECT * FROM `category`;
fetchAll(PDO::FETCH_CLASS, 'Category');
И уже на основание этого мне приходится плясать

Я все операцию выполняю в один раз и кладу всё в memceshe на сутки. Мне выгоднее хранить все категории в памяти и потом с ними работать.

Ибо их 1 тысяча=))

AnrDaemon · 26 Июн 2014

Активист · 26 Июн 2014

c0dex написал(а):
Ну так а вопрос то где? Я не понимаю зачем перебирать все данные в цикле, если это можно сделать на SQL 1 запросом, у тебя данные то в нем ведь лежат?

Ух ты , расскажи как вытащить поддерево (subtree) одним SQL запросом в дереве "список смежности" (Adjacency List, т.е. общепринятое хранение id, parent_id)

Активист · 26 Июн 2014

niko42 написал(а):
Нет, у меня один запрос на все категории SQLCategory->getAll();
SELECT * FROM `category`;
fetchAll(PDO::FETCH_CLASS, 'Category');
И уже на основание этого мне приходится плясать

Я все операцию выполняю в один раз и кладу всё в memceshe на сутки. Мне выгоднее хранить все категории в памяти и потом с ними работать.

Ибо их 1 тысяча=))

Добавьте глобальную позицию (order) типа int unsigned в категорию, это снизит количество интераций в цикле (количество будет стремиться к количеству объектов в БД). Можно и кешировать при изменении дерева (в конце поста). В результате этих двух механизмов у вас отвалится необходимость в memcached из-за крайне низкого потребления CPU и снижении нагрузки на SQL до 0 без каких либо рекурсий. Кеширование же позволяет вытягивать все id дочерних элементов, что бы использовать их в SQL выражениях IN ('1', '2'), без построения всего дерева.

// SELECT * FROM `category` order by `global_order`;

PHP:

<?php
class app_models
{
   /**
    * Построение дерева объектов
    * @param array $objects
    * @return app_models
    */
    public function buildTree(array &$objects)
    {
        $index = array();
        $relations = array();
 
        foreach($objects as $key => $object)
        {
            $index[$object->getId()] = $object->setChildren(array());
             
            if (isset($index[$object->getParentId()]) && $object->getParentId())
            {
                $index[$object->getParentId()]->addChild($object);
            }
            else
            {
                $relations[$object->getParentId()][] = $object;
            }
             
            if ($object->getParentId())
            {
                unset($objects[$key]);
            }
        }
         
        foreach ($relations as $parent => $children)
        {
            foreach ($children as $_children)
            {
                if ($parent && isset($index[$parent]))
                {
                    $index[$parent]->addChildren($_children->setParent($index[$parent]));                 
                }
            }
        }
        return $this;
    }
}

..В свою очередь контроллеры крайне просты

PHP:

<?php
class app_catalog_controllers_admin extends app_controllers_admin implements app_controllers_interface
{
   /**
    * Контроллер главной страницы каталога
    * @return app_catalog_controllers_admin
    */
    public function index()
    {
        $tree = (new app_catalog_categories())->getCategoriesAdminTree();
     
        (new app_catalog_items())->cacheItemsByCategoryAndOppendThreads($tree);
             
        $this->view()
        ->setTitle('Каталог товаров')
        ->setTemplate("admin/index.tpl.php")
        ->assign("objects", $tree)
        ->fetch();
 
        return $this;
    }
}

Модели для древовидных объектов такие:

PHP:

<?php
class app_catalog_categories extends app_models
{
    //...
    public function getCategoriesAdminTree()
    {
        $objects = $this->getAllCategories4AdminTree();
        $this->buildTree($objects);
        return $objects;
    } 
 
    public function getAllCategories4AdminTree()
    {
        $db = new app_db;
        $db->query("select * from `app_catalog_category` order by `position`");
 
        $objects = array();
        while ($row = $db->fetch())
        {
            $objects[] = (new app_catalog_category())->setAttributes($row);
        }
 
        return $objects;
    }
}

В свою очередь древовидные объекты содержат специальный трейт

PHP:

<?php
class app_catalog_category
{
    use app_object_errors, app_object_route, app_object_tree, app_object_images, app_object_sql;
    ...
}

Сам трейт древовидного объекта

PHP:

<?php
trait app_object_tree
{
    /**
    * Объект родителя
    * @var app_object_tree
    */
    protected $_parent;
 
    /**
    * Содержит всех родителей
    * @var array
    */
    protected $_parents;
 
    /**
    * Содержит дочерние объекты
    * @var array
    */
    protected $_children;
 
    /**
    * Содержит массив всех владельцев (для SQL трейта)
    * @var unknown
    */
    protected $allChildrenIds;
 
    /**
    * Устанавливает всех владельцев (используется для кеширования)
    * @param string $allChildrenIds
    * @return app_object_tree
    */
    public function createAllChildrenIds($allChildrenIds = null)
    {
     
        if (!isset($allChildrenIds))
        {
            $allChildrenIds = array();
         
            foreach ($this->getAllChildren() as $child)
            {
                $allChildrenIds[] = $child->getId();
            }
         
            $allChildrenIds = serialize($allChildrenIds);
        }
     
        $this->allChildrenIds = $allChildrenIds;
        return $this;
    }
 
    /**
    * Возвращает все дочерние элементы
    * @return array
    */
    public function getAllChildrenIds()
    {
        if (!trim($this->allChildrenIds))
        {
            return array();
        }
        return explode(",", $this->allChildrenIds);
    }
 
    /**
    * Устанавливает родителя
    * @param object $object
    */
    public function setParent($object)
    {
        $this->_parent = $object;
        return $this;
    }
 
    /**
    * Возвращает родительский объект
    */
    abstract public function getParent();
 
    /**
    * Вовращает всех родителей
    */
    public function getParents()
    {
        if (!$this->getParentId()) {
            return array();
        }
     
        if (!isset($this->_parents)) {
            $this->_parents = array();
 
            $object = $this;
 
            do {
                $object = $object->getParent();
                if ($object)
                {
                    array_unshift($this->_parents, $object);
                }
                 
            } while ($object);
        }
         
        return $this->_parents;
    } 
 
    /**
    * Вершину 0-го уровня
    * @return $this
    */
    public function getRootObjectForTheread()
    {
        if (!$this->getParent())
        {
            return $this;
        }
     
        if (sizeof($this->getParents()))
        {
            return $this->getParents()[0];
        }
     
        return false;
    }
 
    /**
    * Устанавливает детей
    * @param array $children
    */
    public function setChildren(array $children)
    {
        $this->_children = $children;
        return $this;
    }
 
    /**
    * Добавляет ребенка
    * @param object $children
    */
    public function addChildren($children)
    {
        $this->getChildren();
        $this->_children[] = $children;
        return $this;
    }
 
    /**
    * Возвращает обекты детей
    */
    abstract public function getChildren();
 
    /**
    * Возвращает всех детей от текущей вершины
    * @param string $return
    */
    public function getAllChildren(&$return = null)
    {
        if (!isset($return))
        {
            $return = array();
        }
       
        if ($this->getChildren())
        {
            foreach ($this->getChildren() as $children)
            {
                $return[] = $children;
                $children->getAllChildren($return);
            }
        }
       
        return $return;
    }
 
    /**
    * Возвращает уровень объекта
    * @return integer
    */
    public function getLevel()
    {
        return sizeof($this->getParents());
    }
 
    /**
    * Проверяет наличие строки, в списки кук (исользуется в админке)
    * @return boolean
    */
    public function isThreadOpened()
    {
        return app_request::inCookieList(constant(get_class($this)."::COOKIE_LIST"), $this->getId());
    }
 
    /**
    * Проверяет наличие объекта в текущей ветке дерева
    * @param self $object
    */
    public function hasObjectInThread(self $object = null)
    {
        if (!isset($object))
        {
            return false;
        }
 
        if ($this->getId() == $object->getId())
        {
            return true;
        }
 
        foreach ($this->getParents() as $_parent)
        {
            if ($_parent->getId() == $object->getId())
            {
                return true;
            }
        }
 
        return false;
 
    }
}

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

PHP:

<?php
trait app_object_sql
{
// ...
    /**
    * Сохраниение объекта в СУБД
    * @return self
    */
    public function save()
    {
        if (!method_exists($this, "getId")) {
            trigger_error("getId() method missing", E_USER_ERROR);
        }
     
        if (method_exists($this, "preSQLSave"))
        {
            $this->preSQLSave();
        }

        // Кеширование того, что вам нужно
        if (array_key_exists("app_object_tree", class_uses($this)) && array_search("allChildrenIds", $this->getSQLAttributes()) !== false)
        {
            $this->createAllChildrenIds();
        }
         
        if (!$this->getId())
        {
            $this->insert();
        }
        else
        {
            $this->update();
        }
 
        if (array_key_exists("app_object_route", class_uses($this)))
        {
            $this->registerRoute();
        }
     
        if (array_key_exists("app_object_images", class_uses($this)))
        {
            $this->storeAndSaveImages();
        }
     
        // Обновление кеш данных по дочерним элементам
        if (array_key_exists("app_object_tree", class_uses($this)) && array_search("allChildrenIds", $this->getSQLAttributes()) && $this->getParent())
        {
            $this->getParent()->save();
        }

        if (method_exists($this, "postSQLSave"))
        {
            $this->postSQLSave();
        }     
     
        return $this;
    }

niko42 · 26 Июн 2014

Активист:

По сути для моего варианта достаточно из функции вынести

PHP:

 foreach($category as $v){/** @var \application\lib\Category $v */
            $arr[$v->getParentId()][] = $v;
        }

и сохранить в кеш. В итоге мы получим полное дерево массивом. И далее его уже передавать в функцию

c0dex · 26 Июн 2014

[URL='http://phpclub.ru/talk/members/%D0%90%D0%BA%D1%82%D0%B8%D0%B2%D0%B8%D1%81%D1%82.4637/']Активист, [/URL]ну зачем флудить то, юзай тогда nested sets и будет тебе счастье.

Активист · 26 Июн 2014

c0dex написал(а):
Активист, ну зачем флудить то, юзай тогда nested sets и будет тебе счастье.

Не вариант. Много минусов: http://phpclub.ru/faq/Tree/NsFaq?v=xoz#WhereToUse

c0dex · 26 Июн 2014

Активист, для тебя да, не вариант, для меня - вариант. Особенно при наличии кеширования и прочих плюшек, которые сводят на нет недостатки обоих методов хранения.

Поиск всех детей по дереву

niko42

Новичок

c0dex

web.dev 2002-...

niko42

Новичок

c0dex

web.dev 2002-...

niko42

Новичок

AnrDaemon

Продвинутый новичок

Активист

Активист

Активист

Активист

niko42

Новичок

c0dex

web.dev 2002-...

Активист

Активист

c0dex

web.dev 2002-...