2009年11月09日
广告投放★自助友情CMS落伍广告联盟晒乐广告联盟脉动广告联盟品味广告联盟
广告位可自定样式联系QQ:4285248个文字广告月20元广告联系QQ:428524广告位可自定样式
8个文字广告月20元黄金广告位每月20元广告位可自定样式联系QQ:428524广告位可自定样式
左旋肉碱、全国包邮
买二送一、无效退款

文章浏览→编程相关Mysql→2009年11月09日

2009年11月09日
2009年11月09日

一、引言
产品分类,多级的树状结构的论坛,邮件列表等许多地方我们都会遇到这样的问题:如何存储多级结构的数据?在PHP的应用中,提供后台数据存储的通常是关系型数据库,它能够保存大量的数据,提供高效的数据检索和更新服务。然而关系型数据的基本形式是纵横交错的表,是一个平面的结构,如果要将多级树状结构存储在关系型数据库里就需要进行合理的翻译工作。接下来我会将自己的所见所闻和一些实用的经验和大家探讨一下:
层级结构的数据保存在平面的数据库中基本上有两种常用设计方法

毗邻目录模式(adjacency list model)

预排序遍历树算法(modified preorder tree traversalalgorithm)
二、模型
这里我用一个简单食品目录作为我们的示例数据。我们的数据结构是这样的,以下是代码

  1. Food
    |
  2. |---Fruit
  3.   |
  4.   |---Red
  5.    |
  6.    |--Cherry
  7.   |
  8.   +---Yellow
  9.        |
  10.       +--Banana
  11. |
  12. +---Meat
  13.      |--Beef
  14.      +--Pork
三、实现

1、毗邻目录模式(adjacency list model)

这种模式我们经常用到,很多的教程和书中也介绍过。我们通过给每个节点增加一个属性 parent来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原则,例子中的数据可以转化成如下的表:
以下是代码:
  1. +-----------------------+
  2.  parent|    name   |
  3. +-----------------------+
  4.          Food   |
  5.  Food   Fruit   |
  6.  Fruit    Green  |
  7.  Green    Pear   |
  8.  Fruit    Red    |
  9.  Red    Cherry  |
  10.  Fruit   Yellow  |
  11.  Yellow|   Banana  |
  12.  Food    Meat    |
  13.  Meat    Beef    |
  14.  Meat    Pork    |
  15. +-----------------------+

我们看到 Pear 是Green的一个子节点,Green是Fruit的一个子节点。而根节点'Food'没有父节点。为了简单地描述这个问题, 这个例子中只用了name来表示一个记录。在实际的数据库中,你需要用数字的id来标示每个节点,数据库的表结构大概应该像这样:id, parent_id, name,descrīption。
有了这样的表我们就可以通过数据库保存整个多级树状结构了。
显示多级树,如果我们需要显示这样的一个多级结构需要一个递归函数
以下是代码:


<?php
function display_children($parent$level
{
    
// 获得一个 父节点 $parent 的所有子节点
    
$result mysql_query(
"SELECT name FROM tree WHERE parent '" $parent "';");
    
// 显示每个子节点
    
while ($row mysql_fetch_array($result
)) {
        
// 缩进显示节点名称
        echo str_repeat( '$level$row['name'"\n";
        
//再次调用这个函数显示子节点的子节点
        
display_children($row['name'], $level+1
);
    }
}
?>
对整个结构的根节点(Food)使用这个函数就可以打印出整个多级树结构,由于Food是根节点它的父节点是空的,所以这样调用:display_children('',0)。将显示整个树的内容:
  1. Food
  2.     Fruit
  3.        Red
  4.           Cherry
  5.        Yellow
  6.           Banana
  7.     Meat
  8.        Beef
  9.        Pork
如果你只想显示整个结构中的一部分,比如说水果部分,就可以这样调用:display_children('Fruit',0);
几乎使用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是 "Food >;Fruit >; Red"。 为了得到这样的一个路径我们需要从最深的一级"Cherry"开始,查询得到它的父节点"Red"把它添加到路径中,然后我们再查询Red的父节点并把它也添加到路径中,以此类推直到最高层的"Food",以下是代码:

<?php
// $node 是那个最深的节点
function get_path($node
{
    
// 查询这个节点的父节点
    
$result mysql_query(
"SELECT parent  FROM tree WHERE name '" $node ."';");
    
$row mysql_fetch_array($result
);
    
// 用一个数组保存路径
    
$path 
array();
    
// 如果不是根节点则继续向上查询
    // (根节点没有父节点)
    
if ($row['parent'!= ''
{
        
// the last part of the path to $node, is the name
        // of the parent of $node
        
$path[] $row['parent'
];
        
// we should add the path to the parent of this node
        // to the path
        
$path array_merge(get_path($row['parent']), $path
);
    }
    
// return the path
    
return $path
;
}
?>;

复制代码

如果对"Cherry"使用这个函数:print_r(get_path('Cherry')),就会得到这样的一个数组了:

   Array (

  1.     [0] =>Food
  2.     [1] =>Fruit
  3.     [2] =>Red
  4. )

接下来如何把它打印成你希望的格式,就是你的事情了。
缺点:
这种方法很简单,容易理解,好上手。但是也有一些缺点。主要是因为运行速度很慢,由于得到每个节点都需要进行数据库查询,数据量大的时候要进行很多查询才能完成一个树。另外由于要进行递归运算,递归的每一级都需要占用一些内存所以在空间利用上效率也比较低。

所属分类:编程相关Mysql    作者:新浪博客    时间:2010-11-20 0:00:00

文章导航