邻接表与嵌套集模型

Question

我一直在研究邻接表和嵌套集模型以找到最佳的树解决方案。

到目前为止，我认为嵌套集模型的主要优点之一是我可以使用一个 SQL 查询和一些代码来获得一棵完整的树。但更新/插入节点很复杂，并且整个树很容易被损坏。

然后我偶然发现了这两篇文章：

具有单个查询的递归类别？

< a href="http://www.sitepoint.com/forums/showthread.php?t=570360" rel="nofollow noreferrer">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');

Answer 1

代码似乎相当不错，并且给定合理的行数（不是数百万行）不会对性能造成太大影响。

但我认为你问了错误的问题：

当你需要遍历层次结构时，嵌套集就会发挥作用，并且按顺序获取整个表的成本太高查找某个节点的父节点的父节点。对于邻接列表，您需要多个查询来实现此目的，或者让 PHP 使用嵌套循环来完成工作（这意味着最坏情况为 O(n^2)）。

无论哪种方式，当您的目标是查找祖先时，嵌套集通常会表现得更好（例如，在嵌套类别的层次结构中查找产品）。

请参阅这篇文章：管理 MySQL 中的分层数据。它将为您提供如何实现各种查询/更新/插入/删除的良好起点。

Answer 2

您的观察非常正确，过去 2 天我一直在寻找层次结构数据集的良好实现。
我发现人们更喜欢嵌套数据模型而不是相邻数据列表。

我个人更喜欢相邻数据列表的实现，因为它很容易理解，而且直观；创建、更新和删除操作在父数据和子数据上实现起来非常简单，我可以说的唯一缺点是您需要编写一个丑陋的 SQL 查询来从父代码获取所有子列表。

您可以使用此视频来更多地了解该主题。
Phil Waclawski：在 MySQL 树与嵌套中使用分层数据