PHP Mysql树形结构(无限分类)数据库设计的两个例子

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

1.收到手表的方式；

2.预排序遍历树模式；

假设树结构如下：

接收方法和接收表

主要依赖于一个父字段，用于指向上级节点，连接相邻的上级节点和下级节点。id是自动递增的，parent_id是上级节点的id。一眼看去，“Java”是“语言”的子节点。

我们想要显示树，PHP代码也可以非常直观。代码如下：复制代码如下：Php/***获取父节点下的所有子节点* * @自2011-05-18 * * @ param $ parent _ id，0显示整个树结构。* @ param $ levelThe当前节点的级别，用于缩进显示节点。* @ return void */function show _ children($ parent _ id=0，$ level=0){//获取父节点$ result=MySQL _ query下的所有子节点(' select id，name from tree where parent _ id=')。int val($ parent _ id))；//显示每个子节点while($ row=MySQL _ fetch _ array($ result)){//缩进显示echo ' div style=' margin-left : '。($ level * 12)。'px ' '。$ row ['name']。/div '；//递归调用当前函数，显示下一个子节点show _ children ($ row ['id']，$ level 1)；}}?

要显示整个树结构，请调用show_children()。要显示“数据库”子树，请调用show_children(2)，因为“数据库”的id是2。

另一个常用的函数是获取节点路径，即给定一个节点，返回从根节点到当前节点的路径。功能实现如下：复制代码如下：Php/*** @param $id需要获取路径当前节点的id。* @ return array */function get _ path($ id){//获取父节点id和当前节点名$ result=MySQL _ query(' select parent _ id，name from tree，其中id=')。int val($ 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}?

要获取MySQL 5.0的路径，调用get_path(4)，其中4是这个节点的id。

收表的好处是容易理解，代码简单明了。缺点是递归中的SQL查询会导致负载过重，尤其是需要处理相对较大的树结构时，查询语句会随着层次的增加而增加，WEB应用的瓶颈基本都在数据库中，所以这是一个致命的缺点，直接导致树结构扩展困难。

排序遍历树模式

现在我们来谈谈第二种方式——预排序遍历树的方式(俗称MPTT，修改过的预排序树遍历)。在第一种方法的基础上，该算法在每个节点上添加一个左右数字来标识节点的遍历顺序，如下图所示：

从根节点开始，左侧是1，然后下一个节点的左侧是2，以此类推。在最低级别节点之后，最低级别节点的右侧会在其左侧的数字上加上1。沿着这些节点，我们可以很容易地遍历整棵树。根据上图，我们对数据表做了一些修改，增加了两个字段，lft和rgt用来存储左右数字(因为左右是MySQL的保留字，我们用缩写代替)。表中行的内容变为：

接下来，让我们看看显示树/子树有多简单，只需要一条SQL语句。例如，要显示“数据库”子树，需要得到“数据库”的左右编号，左边是2，右边是11。那么这个SQL语句就是：

复制代码如下：从树中选择*其中lft介于2和11之间；

SQL语句很简单，但是我们想要的缩进显示是个问题。缩进应该在什么时候显示？缩进多少个单位？要解决这个问题，需要使用栈，也就是LIFO，把每个节点右边的数字按进栈。我们知道，所有节点右侧的值都小于其父节点右侧的值，因此请将当前节点右侧的值与堆栈顶部的值进行比较。如果当前节点小于堆栈的顶值，则意味着当前堆栈中剩余的所有节点都是父节点。此时可以显示缩进，堆栈中的元素数量就是缩进深度。PHP代码实现如下：复制代码代码如下：Php/*** @param $root_id要显示的树/子树的根节点id。*/函数show _ tree($ root _ id=1){//获取当前根节点的左右值$ result=MySQL _ query('从树中选择lft，rgt，其中id=')。int val($ root _ id))；$ row=MySQL _ fetch _ array($ result)；//Stack，存储节点右侧的值，用于显示缩进$ Stack=array()；//获取$root_id节点$ result=MySQL _ query的所有子节点('从树中选择名称、lft、rgt，其中lft介于两者之间'。$ row ['lft']。和。$ row ['rgt']。lftasc '订购；//显示树的每个节点while($ row=MySQL _ fetch _ array($ result)){ If(count($ stack)0){//仅在堆栈不为空时检测//如果当前节点右侧的值大于堆栈的顶值，则移除堆栈的顶值。因为此值对应的节点不是当前节点的父节点，而$(row[' rgt ']$ stack[count($ stack)-1]){ array _ pop($ stack)；while循环结束后，堆栈中只剩下当前节点的父节点}//现在可以显示echo ' div style=' margin-left : '。(计数($ stack) * 12)。”px。$ row ['name']'/div '；//将当前节点按入堆栈，为循环后节点的缩进显示做准备。array_push($stack，$ row[' rgt '])；}}?

获取整个树并调用show_tree()，获取“数据库”子树并调用show_tree(2)。在这个函数中，我们终于不需要递归了，呵呵。

下一步是显示从根节点到某个节点的路径，这比接收表的方式简单得多。它只需要一个SQL语句，不需要递归，比如得到节点“ORACLE”的路径，其左右值分别为7和10，那么SQL语句如下：复制代码代码如下：从树中选择名称，其中lft=7，RGT=10按lftasc排序；

PHP函数的实现如下：

复制代码代码如下：Php/*** @param $node_id需要获取路径的节点id */函数get _ path 2($ node _ id){//获取当前节点的左右值$ result=MySQL _ query('从树中选择lft，rgt，其中id=')。int val($ node _ id))；$ row=MySQL _ fetch _ array($ result)；//获取路径$ result=MySQL _ query('从树中选择名称，其中lft=')中的所有节点。$ row ['lft']。和rgt='。$ row ['rgt']。lftasc '订购；$ path=array()；while($ row=MySQL _ fetch _ array($ result)){ $ path[]=$ row[' name ']；}返回$ path}?

显示树和路径都没问题。现在我们需要知道如何插入节点。在插入新节点之前，我们必须首先为该节点腾出空间。假设我们现在想在“ORACLE 9i”节点的右边添加一个“ORACLE 10”，那么空出的SQL语句如下(ORACLE 9i的正确值是9):

复制代码如下：更新树集rgt=rgt2其中rgt 9；更新树集lft=lft 2，其中lft 9；

位置为空，开始插入新节点：复制代码如下：插入到树集中lft=10，rgt=11，name=' oracle10

调用show_tree()查看结果是否正确。具体的PHP实现代码这里就不写了。

现在，我们将总结预排序遍历树方法的优缺点。缺点是算法抽象，难以理解。虽然在添加节点时只使用了几条SQL语句，但许多记录可能需要更新，从而导致阻塞。优点是树构造和路径获取，比接收表的方式好很多。也就是说，这个算法牺牲了一些写性能来换取读性能。在WEB应用中，读取数据库的比例远远大于写入数据库，因此预排序遍历树的方式比接收表的方式更受欢迎，也更实用。MPTT可以在许多应用中看到，lft和rgt字段通常可以在表中找到。