6

最適なツリー ソリューションを見つけるために、Adjacency List と Nested Set Model を調べています。

これまで、ネストされたセット モデルの主な利点の 1 つは、1 つの SQL クエリといくつかのコードを使用して完全なツリーを取得できることだと考えていました。ただし、ノードの更新/挿入は複雑で、ツリー全体が簡単に破損する可能性があります。

その後、次の 2 つの投稿に出くわしました。

単一のクエリで再帰カテゴリ?

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

次のコードにより、1 つの SQL クエリで Adjacency List を使用できるようになります。Adjacency List は更新が簡単で、ツリー全体が破損する可能性が低いように思えます。

このコードについてどう思いますか?

ツリー構造を反映する多次元配列を生成する

    $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');
4

1 に答える 1

8

コードはまったく問題ないようで、適切な数の行 (数百万行ではありません) が与えられれば、パフォーマンスの点でそれほど大きな打撃を受けることはありません。

しかし、あなたは間違った質問をしたと思います：

ネストされたセットは、階層をトラバースする必要があり、特定のノードの親の親を見つけるためにテーブル全体をフェッチするのはコストがかかりすぎる場合に役立ちます。隣接リストを使用すると、これを達成するために複数のクエリが必要になるか、PHP にネストされたループ (最悪の場合 O(n^2) を意味する) を処理させる必要があります。

いずれにせよ、先祖を見つけることが目的の場合 (たとえば、入れ子になったカテゴリの階層で製品を見つける場合) は、通常、入れ子になったセットのパフォーマンスが大幅に向上します。

この記事を参照してください: MySQL での階層データの管理。さまざまなクエリ/更新/挿入/削除を実装する方法についての良い出発点を提供します。

于 2010-11-13T18:01:26.263 に答える