首页 后端开发 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脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

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

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 Dec 24, 2024 pm 04:42 PM

PHP 8.4 带来了多项新功能、安全性改进和性能改进,同时弃用和删除了大量功能。 本指南介绍了如何在 Ubuntu、Debian 或其衍生版本上安装 PHP 8.4 或升级到 PHP 8.4

讨论 CakePHP 讨论 CakePHP Sep 10, 2024 pm 05:28 PM

CakePHP 是 PHP 的开源框架。它的目的是使应用程序的开发、部署和维护变得更加容易。 CakePHP 基于类似 MVC 的架构,功能强大且易于掌握。模型、视图和控制器 gu

如何修复 MySQL 8.4 上的 mysql_native_password 未加载错误 如何修复 MySQL 8.4 上的 mysql_native_password 未加载错误 Dec 09, 2024 am 11:42 AM

MySQL 8.4(截至 2024 年的最新 LTS 版本)中引入的主要变化之一是默认情况下不再启用“MySQL 本机密码”插件。此外,MySQL 9.0完全删除了这个插件。 此更改会影响 PHP 和其他应用程序

如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 Dec 20, 2024 am 11:31 AM

Visual Studio Code,也称为 VS Code,是一个免费的源代码编辑器 - 或集成开发环境 (IDE) - 可用于所有主要操作系统。 VS Code 拥有针对多种编程语言的大量扩展,可以轻松编写

CakePHP 快速指南 CakePHP 快速指南 Sep 10, 2024 pm 05:27 PM

CakePHP 是一个开源MVC 框架。它使开发、部署和维护应用程序变得更加容易。 CakePHP 有许多库可以减少大多数常见任务的过载。

您如何在PHP中解析和处理HTML/XML? 您如何在PHP中解析和处理HTML/XML? Feb 07, 2025 am 11:57 AM

本教程演示了如何使用PHP有效地处理XML文档。 XML(可扩展的标记语言)是一种用于人类可读性和机器解析的多功能文本标记语言。它通常用于数据存储

CakePHP 有用资源 CakePHP 有用资源 Sep 10, 2024 pm 05:27 PM

以下资源包含有关 CakePHP 的其他信息。请使用它们来获得更深入的知识。

php程序在字符串中计数元音 php程序在字符串中计数元音 Feb 07, 2025 pm 12:12 PM

字符串是由字符组成的序列,包括字母、数字和符号。本教程将学习如何使用不同的方法在PHP中计算给定字符串中元音的数量。英语中的元音是a、e、i、o、u,它们可以是大写或小写。 什么是元音? 元音是代表特定语音的字母字符。英语中共有五个元音,包括大写和小写: a, e, i, o, u 示例 1 输入:字符串 = "Tutorialspoint" 输出:6 解释 字符串 "Tutorialspoint" 中的元音是 u、o、i、a、o、i。总共有 6 个元

See all articles