首页 后端开发 php教程 PHP Mysql树型结构(无限分类)数据库设计的2种方式实例_php技巧

PHP Mysql树型结构(无限分类)数据库设计的2种方式实例_php技巧

May 16, 2016 pm 08:40 PM
mysql php 数据库设计

我们经常需要在关系型数据库中保存一些树状结构数据,比如分类、菜单、论坛帖子树状回复等。常用的方法有两种:

1. 领接表的方式;

2. 预排序遍历树方式;

假设树状结构如下图:

领接表方式

主要依赖于一个 parent 字段,用于指向上级节点,将相邻的上下级节点连接起来,id 为自动递增自动,parent_id 为上级节点的 id。一目了然,“Java”是“Language”的子节点。

我们要显示树,PHP 代码也可以很直观,代码如下:

复制代码 代码如下:

/**
 * 获取父节点下的所有子节点
 *
 * @since 2011-05-18
 *
 * @param $parent_id 父节点 id,0 则显示整个树结构。
 * @param $level 当前节点所处的层级,用于缩进显示节点。
 * @return void
 */
function show_children ($parent_id = 0, $level = 0)
{
    // 获取父节点下的所有子节点
    $result = mysql_query('SELECT id, name FROM tree WHERE parent_id=' . intval($parent_id));
    // 显示每个子节点
    while ($row = mysql_fetch_array($result)) {
        // 缩进显示
        echo '
' . $row['name'] . '
';
        // 递归调用当前函数,显示再下一级的子节点
        show_children($row['id'], $level 1);
    }
}
?>

想要显示整个树结构,调用 show_children()。想要显示“Database”子树,则调用 show_children(2),因为“Database”的 id 是 2。

还有一个经常用到的功能是获取节点路径,即给出一个节点,返回从根节点到当前节点的路径。用函数实现如下:

复制代码 代码如下:

/**
 * @param $id 需要获取路径的当前节点的 id。
 * @return array
 */
function get_path($id)
{
    // 获取当前节点的父节点 id 和当前节点名
    $result = mysql_query('SELECT parent_id, name FROM tree WHERE id='.intval($id));
    $row = mysql_fetch_array($result);
    // 使用此数组保存路径
    $path = array();
    // 将当前节点名保存进路径数组中
    $path[] = $row['name'];
    // 如果父节点非 0,即非根节点,则进行递归调用获取父节点的路径
    if ($row['parent_id']) {
        // 递归调用,获取父节点的路径,并且合并到当前路径数组的其它元素前边
        $path = array_merge(get_path($row['parent_id']), $path);
    }
    return $path;
}
?>

想要获取“MySQL 5.0”的路径,调用 get_path(4),4 即是这个节点的 id。

领接表方式的优点在于容易理解,代码也比较简单明了。缺点则是递归中的 SQL 查询会导致负载变大,特别是需要处理比较大型的树状结构的时候,查询语句会随着层级的增加而增加,WEB 应用的瓶颈基本都在数据库方面,所以这是一个比较致命的缺点,直接导致树结构的扩展困难重重。

排序遍历树方式

现在我们来聊聊第二种方式─预排序遍历树方式(即通常所说的 MPTT,Modified Preorder Tree Traversal)。此算法是在第一种方式的基础之上,给每个节点增加一个左、右数字,用于标识节点的遍历顺序,如下图所示:

从根节点开始左边为 1,然后下一个节点的左边为 2,以此类推,到最低层节点之后,最低层节点的右边为其左边的数字加 1。顺着这些节点,我们可以很容易地遍历完整个树。根据上图,我们对数据表做一些改变,增加两个字段,lft 和 rgt 用于存储左右数字(由于 left 和 right 是 MySQL 的保留字,所以我们改用简写)。表中各行的内容也就变成了:

接下来看看显示树/子树是多么简单,只需要一条 SQL 语句即可,比如显示“Database”子树,则需要获取到“Database”的左右数字,左为 2,右为 11,那么 SQL 语句是:

复制代码 代码如下:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

SQL 语句是简单了,但我们所希望的缩进显示却是个问题。什么时候应该显示缩进?缩进多少单位?解决这个问题,需要使用堆栈,即后进先出(LIFO),每到一个节点,将其右边的数字压入堆栈中。我们知道,所有节点右边的值都比其父节点右边的值小,那么将当前节点右边的值和堆栈最上边的右边值进行比较,如果当前节点比堆栈最上边的值小,表示当前堆栈里边剩下的都是父节点了,这时可以显示缩进,堆栈的元素数量即是缩进深度。PHP 代码实现如下:

复制代码 代码如下:

/**
 * @param $root_id 需要显示的树/子树根节点 id。
 */
function show_tree($root_id = 1)
{
    // 获取当前根节点的左右数值
    $result = mysql_query('SELECT lft, rgt FROM tree WHERE id='.intval($root_id));
    $row = mysql_fetch_array($result);
    // 堆栈,存储节点右边的值,用于显示缩进
    $stack = array();
    // 获取 $root_id 节点的所有子孙节点
    $result = mysql_query('SELECT name, lft, rgt FROM tree WHERE lft BETWEEN '.$row['lft'].' AND '.$row['rgt'].' ORDER BY lft ASC');
    // 显示树的每个节点
    while ($row = mysql_fetch_array($result)) {
        if (count($stack)>0) { //仅当堆栈非空的时候检测
            // 如果当前节点右边的值比堆栈最上边的值大,则移除堆栈最上边的值,因为这个值对应的节点不是当前节点的父节点
            while ($row['rgt'] > $stack[count($stack)-1]) {
                array_pop($stack);
            } //while 循环结束之后,堆栈里边只剩下当前节点的父节点了
        }
        // 现在可以显示缩进了
        echo '
'.$row['name'].'
';
        // 将当前的节点压入堆栈里边,为循环后边的节点缩进显示做好准备
        array_push($stack, $row['rgt']);
    }
}
?>


获取整个树调用 show_tree(),获取“Database”子树调用show_tree(2)。在这个函数中,我们总算不需要用到递归了,呵呵。

接下来是显示从根节点到某节点的路径,这比起领接表方式来说也简单了很多,只需要一句 SQL 就行,不用递归  比如获取“ORACLE”这个节点的路径,其左右值分别是 7 和 10,则 SQL 语句为:

复制代码 代码如下:

SELECT name FROM tree WHERE lft <= 7 AND rgt >= 10 ORDER BY lft ASC;

PHP 函数实现如下:

复制代码 代码如下:

/**
 * @param $node_id 需要获取路径的节点 id
 */
function get_path2($node_id) {
    // 获取当前节点的左右值
    $result = mysql_query('SELECT lft, rgt FROM tree WHERE id='.intval($node_id));
    $row = mysql_fetch_array($result);
    // 获取路径中的所有节点
    $result = mysql_query('SELECT name FROM tree WHERE lft <= '.$row['lft'].' AND rgt >= '.$row['rgt'].' ORDER BY lft ASC');
    $path = array();
    while ($row = mysql_fetch_array($result)) {
        $path[] = $row['name'];
    }
    return $path;
}
?>

显示树和路径都没问题了,现在需要了解一下如何插入一个节点。插入新节点之前,首先要给这个节点腾出空位来,假设我们现在要在“ORACLE 9i”这个节点右边增加一个“ORACLE 10”,则腾位的 SQL 语句如下(“ORACLE 9i”的右边值为 9):

复制代码 代码如下:

UPDATE tree SET rgt=rgt 2 WHERE rgt>9;
UPDATE tree SET lft=lft 2 WHERE lft>9;

位置空出来了,开始插入新节点吧:

复制代码 代码如下:

INSERT INTO tree SET lft=10, rgt=11, name='ORACLE 10';

调用 show_tree() 看看结果对不对  具体的 PHP 实现代码这里就不写了。

现在总结一下预排序遍历树方式的优缺点。缺点是算法比较抽象,不容易理解,增加节点的时候虽然只用了几条 SQL 语句,但可能会需要更新很多记录,从而造成阻塞。优点是树的构造,路径获取方面性能都比领接表方式好很多。也就是说,这个算法牺牲了一些写的性能来换取读的性能,在 WEB 应用中,读数据库的比例远大于写数据库的比例,所以预排序遍历树方式比领接表方式更加受欢迎,更加实用,很多应用中都能看到 MPTT 的影子,通常所用的表里都有字段 lft 和 rgt。

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

PHP和Python:比较两种流行的编程语言 PHP和Python:比较两种流行的编程语言 Apr 14, 2025 am 12:13 AM

PHP和Python各有优势,选择依据项目需求。1.PHP适合web开发,尤其快速开发和维护网站。2.Python适用于数据科学、机器学习和人工智能,语法简洁,适合初学者。

PHP的当前状态:查看网络开发趋势 PHP的当前状态:查看网络开发趋势 Apr 13, 2025 am 12:20 AM

PHP在现代Web开发中仍然重要,尤其在内容管理和电子商务平台。1)PHP拥有丰富的生态系统和强大框架支持,如Laravel和Symfony。2)性能优化可通过OPcache和Nginx实现。3)PHP8.0引入JIT编译器,提升性能。4)云原生应用通过Docker和Kubernetes部署,提高灵活性和可扩展性。

PHP:网络开发的关键语言 PHP:网络开发的关键语言 Apr 13, 2025 am 12:08 AM

PHP是一种广泛应用于服务器端的脚本语言,特别适合web开发。1.PHP可以嵌入HTML,处理HTTP请求和响应,支持多种数据库。2.PHP用于生成动态网页内容,处理表单数据,访问数据库等,具有强大的社区支持和开源资源。3.PHP是解释型语言,执行过程包括词法分析、语法分析、编译和执行。4.PHP可以与MySQL结合用于用户注册系统等高级应用。5.调试PHP时,可使用error_reporting()和var_dump()等函数。6.优化PHP代码可通过缓存机制、优化数据库查询和使用内置函数。7

PHP与其他语言:比较 PHP与其他语言:比较 Apr 13, 2025 am 12:19 AM

PHP适合web开发,特别是在快速开发和处理动态内容方面表现出色,但不擅长数据科学和企业级应用。与Python相比,PHP在web开发中更具优势,但在数据科学领域不如Python;与Java相比,PHP在企业级应用中表现较差,但在web开发中更灵活;与JavaScript相比,PHP在后端开发中更简洁,但在前端开发中不如JavaScript。

MySQL的位置:数据库和编程 MySQL的位置:数据库和编程 Apr 13, 2025 am 12:18 AM

MySQL在数据库和编程中的地位非常重要,它是一个开源的关系型数据库管理系统,广泛应用于各种应用场景。1)MySQL提供高效的数据存储、组织和检索功能,支持Web、移动和企业级系统。2)它使用客户端-服务器架构,支持多种存储引擎和索引优化。3)基本用法包括创建表和插入数据,高级用法涉及多表JOIN和复杂查询。4)常见问题如SQL语法错误和性能问题可以通过EXPLAIN命令和慢查询日志调试。5)性能优化方法包括合理使用索引、优化查询和使用缓存,最佳实践包括使用事务和PreparedStatemen

PHP的持久相关性:它还活着吗? PHP的持久相关性:它还活着吗? Apr 14, 2025 am 12:12 AM

PHP仍然具有活力,其在现代编程领域中依然占据重要地位。1)PHP的简单易学和强大社区支持使其在Web开发中广泛应用;2)其灵活性和稳定性使其在处理Web表单、数据库操作和文件处理等方面表现出色;3)PHP不断进化和优化,适用于初学者和经验丰富的开发者。

PHP:许多网站的基础 PHP:许多网站的基础 Apr 13, 2025 am 12:07 AM

PHP成为许多网站首选技术栈的原因包括其易用性、强大社区支持和广泛应用。1)易于学习和使用,适合初学者。2)拥有庞大的开发者社区,资源丰富。3)广泛应用于WordPress、Drupal等平台。4)与Web服务器紧密集成,简化开发部署。

PHP与Python:核心功能 PHP与Python:核心功能 Apr 13, 2025 am 12:16 AM

PHP和Python各有优势,适合不同场景。1.PHP适用于web开发,提供内置web服务器和丰富函数库。2.Python适合数据科学和机器学习,语法简洁且有强大标准库。选择时应根据项目需求决定。

See all articles