PHP和MySQL处理树状、分级、无限分类、分层数据的方法

文章标题中的多个词语表达的其实是一个意思，就是递归分类数据，分级数据非常类似数据结构中的树状结构，即每个节点有自己的孩子节点，孩子结点本身也是父亲节点。这是一个递归、分层形式。可以称之为树形层级数据。

层级数据结构是编程语言中非常普通的一种数据结构，它代表一系列的数据每一项都有一个父亲节点（除了根节点）和其他多个孩子结点。WEB开发人员使用层级数据结构用于非常多的场景，包括内容管理系统CMS、论坛主题、邮件列表，还有电子商务网站的产品分类等。

本文章主要介绍了使用PHP和MYSQL来管理分级数据的方法，在其中将给出两种最流行的分级数据模型：

• 邻接表模型
• 嵌套集合模型

邻接表模型用于分层数据

邻接表模型是一种分级数据模型，其中每个节点有一个指向其父亲的指针（根节点该指针为空值），使用下面的SQL语句将建立该结构并插入测试数据：

-- --------------------------------------------------------

--
-- 表的结构 `category`
--

CREATE TABLE IF NOT EXISTS `category` (
  `category_id` int(10) NOT NULL AUTO_INCREMENT,
  `category_name` varchar(50) NOT NULL,
  `parent_id` int(10) DEFAULT NULL,
  PRIMARY KEY (`category_id`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 AUTO_INCREMENT=15 ;

--
-- 转存表中的数据 `category`
--

INSERT INTO `category` (`category_id`, `category_name`, `parent_id`) VALUES
(1, 'A', NULL),
(2, 'B', 1),
(3, 'C', 1),
(4, 'D', 1),
(5, 'E', 2),
(6, 'F', 2),
(7, 'I', 4),
(8, 'G', 5),
(9, 'H', 5),
(10, 'J', 7),
(11, 'K', 10),
(12, 'L', 10);

<?php

function get_path($category_id) 
{
    $con = mysql_connect("localhost","root","123456");
    if (!$con) {
        die('数据库连接失败: ' . mysql_error());
    }

    mysql_select_db('test', $con); 

    // 查找当前节点的父节点的ID，这里使用表自身与自身连接实现
    $sql = "
        SELECT c1.parent_id, c2.category_name AS parent_name 
        FROM category AS c1

        LEFT JOIN category AS c2 
        ON c1.parent_id=c2.category_id 

        WHERE c1.category_id='$category_id' ";
    //echo $sql."<br>";//测试把SQL打印出来，拿到数据库执行一下看看结果
    $result = mysql_query($sql);
    $row = mysql_fetch_array($result);//现在$row数组存了父亲节点的ID和名称信息

    // 将树状路径保存在数组里面
    $path = array();

    //如果父亲节点不为空（根节点），就把父节点加到路径里面
    if ($row['parent_id']!=NULL) 
    {
        //将父节点信息存入一个数组元素
        $parent[0]['category_id'] = $row['parent_id'];
        $parent[0]['category_name'] = $row['parent_name'];

        //递归的将父节点加到路径中
        $path = array_merge(get_path($row['parent_id']), $parent);
    }

   return $path;
}

//根据上面的图可以看出，K的ID是11，我们就用它来测试路径
$path =  get_path(11);
echo "<h2>路径数组：</h2>";
echo "<pre>";
print_r($path);
echo "</pre>";
//将路径到根节点的路径打印出来
//打印结果：J>I>D>A>
echo "<h2>向根节点打印路径：</h2>";

for ($i=count($path)-1; $i>=0; $i--)
{
     echo $path[$i]['category_name']. '>';
}

?>

<?php
function display_children($category_id, $level) 
{
    $con = mysql_connect("localhost","root","123456");
    if (!$con) {
        die('数据库连接失败: ' . mysql_error());
    }

    mysql_select_db('test', $con); 
    // 获得当前节点的所有孩子节点（直接孩子，没有孙子）
    $result = mysql_query("SELECT * FROM category WHERE parent_id='$category_id'");

    // 遍历孩子节点，打印节点
    while ($row = mysql_fetch_array($result)) 
    {
        // 根据层级，按照缩进格式打印节点的名字
        // 这里只是打印，你可以将以下代码改成其他，比如把节点信息存储起来
        echo str_repeat('--',$level) . $row['category_name'] . "<br/>";

       // 递归的打印所有的孩子节点
       display_children($row['category_id'], $level+1);
    }
}

//根节点是A:1我们就用它来打印所有的节点
display_children(1, 0);
?>

然而，邻接表模型（每个节点存储父亲节点信息）有它的劣势，首先使用数据库的查询语句很难直接实现它，需要借助PHP代码实现。SQL语句需要你知道节点位于哪一个层级。并且每个树层是使用SQL的自我表连接实现的，这意味着树的每一层处理都会降低数据库的性能。

删除节点的过程也会导致一些问题，如果只删除了某个节点它却有孩子，结果是它的孩子成了孤儿（就是没有父亲了），真正的体现就是，这些孩子节点从树中相当于“消失了”。

嵌套集合模型用于树形分层结构数据

嵌套集合模型，也叫做先根遍历树算法，也是一种处理树形层级数据的方法。代替节点间的父子关系，层级使用嵌套的容器的集合来表示，其中每个节点具有两个值，一个left，一个right。

决定left和right的值的过程是从左到右进行的，首先给left赋值，让后向下遍历节点的孩子们，最后才能得到节点的right的值。SQL语句如下所示：

CREATE TABLE category (
        category_id INT(10) AUTO_INCREMENT PRIMARY KEY,
        category_name VARCHAR(50) NOT NULL,
        lft INT(10) NOT NULL,
        rgt INT(10) NOT NULL
);

现在可以用一句SQL查询得到整个树的节点：

SELECT * FROM category WHERE lft BETWEEN 1 AND 14 ORDER BY lft ASC

在本SQL中的两个数字值1和14就是根节点的left和right值。类似的如果想得到某个节点的所有孩子节点，只需要将该SQL语句的1和14替换成本节点的left和right值就可以了。例如，如果想得到所有男人的衣服，可以用下面的SQL语句：

SELECT * FROM category WHERE lft BETWEEN 2 AND 7 ORDER BY lft ASC

想找到一条到某个节点的路径，用一条SQL语句就可以搞定：

SELECT * FROM category WHERE lft < 9 AND rgt > 10 ORDER BY lft ASC

请仔细观察一下一些叶子节点到根节点的路径。就会发现所有的祖先都有更小的左值和更大的右值。本例子中一条到裙子分类的路径被取出。观察一下裙子的所有left值都小于9，right值都大于10，其他的非祖先节点都不满足该要求。

尽管嵌套集合模型更加复杂并且有些难以理解，它有非常多的优势。它不需要依赖其他资源（比如PHP代码），也不需要递归。同时，数据库查询语句非常的简单，大多数用一条SQL语句就可以搞定。这些特性都能够显著的增加应用程序的性能，使得它能够用可接受的速度来处理复杂的层级结构。

然而万事皆无完美，更新该层级结构（增加或删除节点）却更加的复杂，并且可能会非常慢。

增加一个节点到层级结构的方法：

将一个节点插入到层级数据中，需要整个树很多节点的left和right值的更新。例如，如果你想将一个男士运动鞋的分类插入到男性衣服的短裤后面。那么所有你必须将大于6的所有left和right值都增加2。为什么呢？因为短裤的right值是6，那你就必须将你的新分类的left和right值设定为7和8，当然，以下两条SQL就可以解决：

UPDATE category SET rgt=rgt+2 WHERE rgt>6