Список смежности и модель вложенного множества - PullRequest
Новая
       28

Список смежности и модель вложенного множества

6 голосов
/ 13 ноября 2010

Я искал Список смежности и Модель вложенного набора, чтобы найти оптимальное древовидное решение.

До сих пор я думал, что одним из главных преимуществ Модели вложенного набора является то, что я могу использовать один запрос SQL инекоторый код, чтобы получить полное дерево.Но обновлять / вставлять узлы сложно, и все дерево легко может быть повреждено.

Тогда я наткнулся на эти два сообщения:

Рекурсивные категории с одним запросом?

http://www.sitepoint.com/forums/showthread.php?t=570360

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

Что вы думаете об этом коде?

Создание многомерногомассив для отражения древовидной структуры 

    $nodeList = array();
    $tree = array();

    $query = mysql_query("SELECT id, title, page_parent FROM categories ORDER BY page_parent");
    while($row = mysql_fetch_assoc($query)){
        $nodeList[$row['id']] = array_merge($row, array('children' => array()));
    }
    mysql_free_result($query);

    foreach($query AS $row){
        $nodeList[$row['id']] = array_merge($row, array('children' => array()));
    }

    foreach ($nodeList as $nodeId => &$node) {
        if (!$node['page_parent'] || !array_key_exists($node['page_parent'], $nodeList)) {
            $tree[] = &$node;
        } else {
            $nodeList[$node['page_parent']]['children'][] = &$node;
        }
    }

    unset($node);
    unset($nodeList);

Подготовить неупорядоченный список с вложенными узлами 

function printMenu ($arrTreeToTraverse, $ext = '.html', $breadcrumb = '') {

// Pre loop stuff
echo "<ul class=\"sf-menu\">\r\n";

foreach ($arrTreeToTraverse as $objItem) {

    // Stuff relevant to the item, before looping over its children
    if ($objItem['page_parent'] != 0) {
        $breadcrumb .= '/'.$objItem['uri'];
    }
    else
    {
        $breadcrumb .= $objItem['uri'];
    }

    if ($objItem['uri'] == 'index') {
        echo '<li><a href="/">'.$objItem['title'].'</a>';
    } else {
        echo '<li><a href="'$_SERVER['SERVER_NAME'].'/'.$breadcrumb.$ext.'">'.$objItem['title'].'</a>';
    }

    if ($objItem['children']) {
    echo "\r\n";

        // Call the function again on the children
        printMenu($objItem['children'], $ext, $breadcrumb);
    }// if

    // Extend breadcrumb if it is a child or
    // reset breadcrumb if first level of tree
    $parent = explode('/', $breadcrumb);
    if ($objItem['page_parent'] != 0) {
        $breadcrumb = $parent[0];
    } else {
        $breadcrumb = '';
    }

    echo "</li>\r\n";
}// foreach

// Post loop stuff
echo "</ul>\r\n";

}// function

printMenu($navigation, '.html');

1 Ответ

7 голосов
/ 13 ноября 2010

Код выглядит вполне нормально, и при наличии разумного количества строк (миллионы строк нет) это не сильно ударит по производительности.

Но я думаю, что вы задали неправильный вопрос:

Вложенные наборы вступают в игру, когда вам нужно пройти иерархии , и было бы слишком дорого извлекать всю таблицу, чтобы найти родителя родителя определенного узел. При наличии списков смежности вам потребуется несколько запросов для достижения этого или позволить PHP выполнять работу с вложенными циклами (что означает наихудший случай O (n ^ 2)).

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

См. Эту статью: Управление иерархическими данными в MySQL . Это даст вам хорошую отправную точку для реализации различных запросов / обновлений / вставок / удалений.

...