`
hudeyong926
  • 浏览: 2034837 次
  • 来自: 武汉
社区版块
存档分类
最新评论

左右值无限级分类

MySQLPHP算法 
阅读更多

什么是左右值无限级分类：

左右值无限级分类，也称为预排序树无限级分类，是一种有序的树状结构，位于这些树状结构中的每一个节点都有一个“左值”和“右值”，其规则是：每一个后代节 点的左值总是大于父类，右值总是小于父级，右值总是小于左值。处于这些结 构中的每一个节点，都可以轻易的算出其祖先或后代节点。因此，可以用它来实现无限分类。优点：通过一条SQL就可以获取所有的祖先或后代，这在复杂的分类中非常必要，通过简单的四则运算就可以得到后代的数量.由于这种方法不使用递归查询算法，有更高的查询效率,采用左右值编码的设计方案，在进行类别树的遍历时，由于只需进行2次查询，消除了递归，再加上查询条件都为数字比较，效率极高。这种算法比较高端，是mysql官方推荐的算法
1. 测试数据准备
CREATE TABLE `tree` (
  `id` int(10) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `lft` int(10) NOT NULL DEFAULT '0' COMMENT '左节点',
  `rgt` int(10) NOT NULL DEFAULT '0' COMMENT '右节点',
  `status` int(1) NOT NULL DEFAULT '0' COMMENT '逻辑删除 1是 0否',
  PRIMARY KEY (`id`),
  KEY `lft` (`lft`),
  KEY `rgt` (`rgt`),
  KEY `status` (`status`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

insert into tree value (null,'Food',1,18,0);
insert into tree value (null,'Fruit',2,11,0);
insert into tree value (null,'Red',3,6,0);
insert into tree value (null,'Cherry',4,5,0);
insert into tree value (null,'Yellow',7,10,0);
insert into tree value (null,'Banana',8,9,0);
insert into tree value (null,'Meat',12,17,0);
insert into tree value (null,'Beef',13,14,0);
insert into tree value (null,'Pork',15,16,0);

我们首先将多级数据按照下面的方式画在纸上

                         1 Food 18 
                             |
            +------------------------------+
            |                              |
        2 Fruit 11                     12 Meat 17 
            |                              |
    +-------------+                 +------------+
    |             |                 |            |
 3 Red 6      7 Yellow 10       13 Beef 14   15 Pork 16 
    |             |
4 Cherry 5    8 Banana 9

2. 插入分类思路

两种情况：
插入最顶级节点：它的左右值与该树中最大的右值有关：左值=1，右值=最大右值+2
插入子节点：它的左右值与它的父级有关：左值=父级的右值，右值=当前的左值+1，这时要更新的数据有：父级的右值，所有左值大于父级左级，右值大于低级右值的节点左右值都应该+2；

3. 获取所有的后代节点

从图中可以看出找出某个节点的所有子节点，lft 大于左值 rgt 小于右值 
SELECT * FROM tree WHERE lft>2 AND rgt<11;

这个查询得到了以下的结果。

+------------+-----+-----+
|    name    | lft | rgt |
+------------+-----+-----+
|    Red     | 3   |  6  |
|    Cherry  | 4   |  5  |
|    Yellow  | 7   | 10  |
|    Banana  | 8   |  9  |
+------------+-----+-----+

4. 计算所有子类的数量

每有子类节点中每个节点占用两个值，而这些值都是不一样且连续的，那些就可以计算出子代的数量=(右值-左值-1)/2。减少1的原因是排除该节点，你可以想像一个，一个单节点，左值是1，右值是2，没有子类节点，而这时它的右值-左值=1.

5. 检索单一路径

如果我们想知道Cherry 的路径就利用它的左右值4和5来做一个查询。反向也是一样的唯一的区别就是排序是反向的就行了。

SELECT name FROM tree WHERE lft < 4 AND rgt >5 ORDER BY lft ASC;
6. 检索所有叶子节点

要检索出叶子节点（一棵树当中没有子结点的结点，称为叶子结点），我们只要查找满足rgt=lft+1的节点

select * from tree where rgt = lft + 1;
7. 获取分类的深度 
SELECT node.*, (count(parent.name) - 1) AS deep 
FROM tree AS node,tree AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt 
GROUP BY node.name ORDER BY node.lft
8. 检索节点的直接子节点
可以想象一下，你在零售网站上呈现电子产品的分类。当用户点击分类后，你将要呈现该分类下的产品，同时也需列出该分类下的直接子分类，而不是该分类下的全部分类。为此，我们只呈现该节点及其直接子节点，不再呈现更深层次的节点.如上述获取深度的例子，可以根椐深度来小于等于1获得直接子节点 
SELECT * FROM (sql7) AS a WHERE a.deep<= 1;
拿到Fruit的指定一级深度的子分类
SELECT * FROM (sql7) AS tt WHERE tt.lft>2 AND tt.rgt<11 AND tt.deep=2 ORDER BY lft
移动节点及其子节点至节点A下？

设该节点左值$lft , 右值$rgt,其子节点的数目为$count = ($rgt - $lft -1 )/2 , 节点A左值为$A_lft ,

UPDATE `tree` SET `rgt`=`rgt`-$rgt-$lft-1 WHERE `rgt`>$rgt AND `rgt`<$A_lft
UPDATE `tree` SET `lft`=`lft`-$rgt-$lft-1 WHERE `lft`>$rgt AND `lft`<=$A_lft
UPDATE `tree` SET `lft`=`lft`+$A_lft-$rgt , `rgt`=`rgt`+$A_lft-$rgt WHERE `lft`>=$lft AND `rgt`<=$rgt

移动多个节点；移动单个节点；删除多个节点；删除单个节点；新增节点

<?php

/**
 *用于移动一个节点（包括子节点）
 * @param array $pdata = array('id'=>主键,'root'=>名称) 二选一 父节点(为空时插入最大的父节点)
 * @param array $ndata = array('id'=>主键,'root'=>名称) 二选一 下一个兄弟节点（没有兄弟的时候就不用）
 * @param array $cdata = array('id'=>主键,'root'=>名称) 二选一 当前待移动的节点
 */
function move_tree_all($pdata = array(), $ndata = array(), $cdata = array())
{
    $cid = $cdata['id'] ? intval($cdata['id']) : '';
    $croot = $cdata['root'];
    if (!$cid && !$croot) return;

    //需自加判断
    //1、cdata不能为顶级
    //2、cdata不能比$pdata等级高

    $adata = get_tree_all($cdata); //获取当前移动节点的所有节点
    delete_tree_all($cdata, 1); //逻辑删除当前移动节点的所有节点

    foreach ($adata as $k => $val) {
        if ($k != 0) {
            $pdata = array('root' => $val['parent']);
            insert_tree($pdata, '', $val['name'], 1);
        } else { //first
            insert_tree($pdata, $ndata, $val['name'], 1);
        }
    }
}

/**
 *用于移动一个节点（不包括子节点）
 * @param array $pdata = array('id'=>主键,'root'=>名称) 二选一 父节点(为空时插入最大的父节点)
 * @param array $ndata = array('id'=>主键,'root'=>名称) 二选一 下一个兄弟节点（没有兄弟的时候就不用）
 * @param array $cdata = array('id'=>主键,'root'=>名称) 二选一 当前待移动的节点
 */
function move_tree_item($pdata = array(), $ndata = array(), $cdata = array())
{
    $cid = $cdata['id'] ? intval($cdata['id']) : '';
    $croot = $cdata['root'];
    if (!$cid && !$croot) return;

    //需自加判断
    //1、cdata不能为顶级

    if (!$croot) {
        $sql = "SELECT name from tree where id = $cid";
        $result = mysql_query($sql);
        $row = mysql_fetch_assoc($result);
        $croot = $row['name'];
        unset($sql);
    }

    delete_tree_item($cdata, 1);
    insert_tree($pdata, $ndata, $croot, 1);
}

/**
 *用于插入一个节点
 * @param array $pdata = array('id'=>主键,'root'=>名称) 二选一 父节点(为空时插入最大的父节点)
 * @param array $ndata = array('id'=>主键,'root'=>名称) 二选一 下一个兄弟节点（没有兄弟的时候就不用）
 * @param string $name string 新插入的名称
 * @param int $update 默认为空，为1时更新插入
 */
function insert_tree($pdata = array(), $ndata = array(), $name, $update = '')
{
    if (!$name) return;

    $pid = $pdata['id'] ? intval($pdata['id']) : '';
    $proot = $pdata['root'];

    $nid = $ndata['id'] ? intval($ndata['id']) : '';
    $nroot = $ndata['root'];

    //有父无兄（最小的子节点，父节点的最后一个儿子）
    if (($pid || $proot) && !($nid || $nroot)) {
        $sql = $pid ? "SELECT lft, rgt FROM tree WHERE id = '{$pid}';" : "SELECT lft, rgt FROM tree WHERE name = '{$proot}';";
        $result = mysql_query($sql);
        $row = mysql_fetch_assoc($result);
        unset($sql);

        //新节点
        $lft = $row['rgt'];
        $rgt = $lft + 1;
        if (!$update) {
            $sql = "insert into tree values (null,'{$name}',$lft,$rgt,0);";
            $sql1 = "update tree set rgt = rgt+2 where rgt >= {$row['rgt']}";
            $sql2 = "update tree set lft = lft+2 where lft >= {$row['rgt']}";
        } else {
            $sql = "update tree set lft=$lft,rgt=$rgt,status=0 where name ='{$name}';";
            $sql1 = "update tree set rgt = rgt+2 where status =0 and rgt >= {$row['rgt']}";
            $sql2 = "update tree set lft = lft+2 where status =0 and lft >= {$row['rgt']}";
        }

        mysql_query($sql1);
        mysql_query($sql2);
        mysql_query($sql); //last add new data
    }

    //有父有兄
    if (($pid || $proot) && ($nid || $nroot)) {
        $sql = $nid ? "SELECT lft, rgt FROM tree WHERE id = '{$nid}';" : "SELECT lft, rgt FROM tree WHERE name = '{$nroot}';";
        $result = mysql_query($sql);
        $row = mysql_fetch_assoc($result);
        unset($sql);

        //新节点
        $lft = $row['lft'];
        $rgt = $lft + 1;
        if (!$update) {
            $sql = "insert into tree values (null,'{$name}',$lft,$rgt,0);";
            $sql1 = "update tree set rgt = rgt+2 where rgt >= {$row['lft']};";
            $sql2 = "update tree set lft = lft+2 where lft >= {$row['lft']};";
        } else {
            $sql = "update tree set lft=$lft,rgt=$rgt,status=0 where name ='{$name}';";
            $sql1 = "update tree set rgt = rgt+2 where status = 0 and rgt >= {$row['lft']};";
            $sql2 = "update tree set lft = lft+2 where status = 0 and lft >= {$row['lft']};";
        }
        mysql_query($sql1);
        mysql_query($sql2);
        mysql_query($sql); //last add new data
    }

    //无父无兄(大佬)
    if (!($pid || $proot) && !($nid || $nroot)) {
        $sql = "SELECT max(`rgt`) as rgt FROM tree;";
        $result = mysql_query($sql);
        $row = mysql_fetch_assoc($result);
        unset($sql);

        //新节点
        $lft = 1;
        $rgt = $row['rgt'] + 2;
        if (!$update) {
            $sql = "insert into tree values (null,'{$name}',$lft,$rgt,0);";
            $sql1 = "update tree set rgt = rgt+1";
            $sql2 = "update tree set lft = lft+1";
        } else {
            $sql = "update tree set lft=$lft,rgt=$rgt,status=0 where name ='{$name}';";
            $sql1 = "update tree set rgt = rgt+1 where status = 0";
            $sql2 = "update tree set lft = lft+1 where status = 0";
        }

        mysql_query($sql1);
        mysql_query($sql2);
        mysql_query($sql); //last add new data
    }

}

/**
 *用于删除一个节点(包括子节点)
 * @param array $data = array('id'=>主键,'root'=>名称) 二选一
 * @param int $update 默认为空，为1时逻辑删除
 */
function delete_tree_all($data, $update = '')
{
    $id = $data['id'] ? intval($data['id']) : '';
    $root = $data['root'];
    if (!$id && !$root) return;

    $sql = $id ? "SELECT lft, rgt FROM tree WHERE id = '{$id}';" : "SELECT lft, rgt FROM tree WHERE name = '{$root}';";
    $result = mysql_query($sql);
    $row = mysql_fetch_assoc($result);
    unset($sql);

    $middle = $row['rgt'] - $row['lft'] + 1;
    if (!$update) {
        $sql = "delete from tree where lft BETWEEN '" . $row['lft'] . "' AND '" . $row['rgt'] . "'";
        $sql1 = "update tree set rgt = rgt-{$middle} where rgt > {$row['rgt']}";
        $sql2 = "update tree set lft = lft-{$middle} where lft > {$row['rgt']}";
    } else {
        $sql = "update tree set status = 1 where lft BETWEEN '" . $row['lft'] . "' AND '" . $row['rgt'] . "'";
        $sql1 = "update tree set rgt = rgt-{$middle} where status=0 and rgt > {$row['rgt']}";
        $sql2 = "update tree set lft = lft-{$middle} where status=0 and lft > {$row['rgt']}";
    }

    mysql_query($sql);
    mysql_query($sql1);
    mysql_query($sql2);
}

/**
 *用于删除一个节点(不包括子节点)
 * @param array $data = array('id'=>主键,'root'=>名称) 二选一
 * @param int $update 默认为空，为1时逻辑删除
 */
function delete_tree_item($data, $update = '')
{
    $id = $data['id'] ? intval($data['id']) : '';
    $root = $data['root'];
    if (!$id && !$root) return;

    $sql = $id ? "SELECT id,lft, rgt FROM tree WHERE id = '{$id}';" : "SELECT id,lft, rgt FROM tree WHERE name = '{$root}';";
    $result = mysql_query($sql);
    $row = mysql_fetch_assoc($result);
    unset($sql);

    if (!$update) {
        $sql = "delete from tree where id = {$row['id']};";
        $sql1 = "update tree set rgt = rgt-1,lft = lft -1 where lft > {$row['lft']} and rgt < {$row['rgt']}";
        $sql2 = "update tree set lft = lft-2 where lft > {$row['rgt']}";
        $sql3 = "update tree set rgt = rgt-2 where rgt > {$row['rgt']}";
    } else {
        $sql = "update tree set status = 1 where id = {$row['id']};";
        $sql1 = "update tree set rgt = rgt-1,lft = lft -1 where status = 0 and lft > {$row['lft']} and rgt < {$row['rgt']}";
        $sql2 = "update tree set lft = lft-2 where status = 0 and lft > {$row['rgt']}";
        $sql3 = "update tree set rgt = rgt-2 where status = 0 and rgt > {$row['rgt']}";
    }

    mysql_query($sql);
    mysql_query($sql1);
    //can do or not do just right,but not do load empty 2 number in middle
    mysql_query($sql2);
    mysql_query($sql3);
}

/**
 *用于获取所有的节点
 * @param array $data = array('id'=>主键,'root'=>名称) 二选一
 */
function get_tree_all($data)
{
    $id = $data['id'] ? intval($data['id']) : '';
    $root = $data['root'];
    if (!$id && !$root) return;

    $sql = $id ? "SELECT lft, rgt FROM tree WHERE id = '{$id}';" : "SELECT lft, rgt FROM tree WHERE name = '{$root}';";
    $result = mysql_query($sql);
    $row = mysql_fetch_assoc($result);

    $adata = array(); //所有数据
    $right = array(); //计数
    $prev = array();
    $result = mysql_query("SELECT id,name, lft, rgt FROM tree WHERE lft BETWEEN '" . $row['lft'] . "' AND '" . $row['rgt'] . "' ORDER BY lft ASC ;");
    while ($row = mysql_fetch_assoc($result)) {
        if (count($right) > 0) {
            while ($right[count($right) - 1] < $row['rgt']) { // 检查我们是否应该将节点移出堆栈
                array_pop($right);
                array_pop($prev);
            }
        }

        $parent = $prev ? end($prev) : '';
        $adata[] = array('id' => $row['id'], 'name' => $row['name'], 'level' => count($right), 'parent' => $parent);

        $right[] = $row['rgt'];
        $prev[] = $row['name'];
    }
    return $adata;
}

/**
 *用于展示分类
 * @param array $data = array('id'=>主键,'root'=>名称) 二选一
 */
function display_tree($data)
{
    $id = $data['id'] ? intval($data['id']) : '';
    $root = $data['root'];
    if (!$id && !$root) return;

    $sql = $id ? "SELECT lft, rgt FROM tree WHERE id = '{$id}';" : "SELECT lft, rgt FROM tree WHERE name = '{$root}';";
    $result = mysql_query($sql);
    $row = mysql_fetch_assoc($result);

    $right = array();
    $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_assoc($result)) {
        if (count($right) > 0) { // 检查我们是否应该将节点移出堆栈
            while ($right[count($right) - 1] < $row['rgt']) {
                array_pop($right);
            }
        }
        echo str_repeat('--', count($right)) . $row['name'] . "<br/>";
        $right[] = $row['rgt'];
    }
}

mysql_connect('localhost', 'root', 'orbit') or die('connect error');
mysql_select_db('test') or die('database error');
mysql_query('set names utf8');

//display_tree(array('root' => 'Food'));
//display_tree(array('root'=>'bigboss'));

//move_tree_all($pdata=array('root'=>'Fruit'),$ndata=array('root'=>'Red'),$cdata=array('root'=>'Meat'));
//move_tree_all('','',$cdata=array('root'=>'Meat'));
//move_tree_item('','',array('root'=>'Red'));
//move_tree_item(array('root'=>'Red'),array('root'=>'Cherry'),array('root'=>'Fruit'));

//delete_tree_all(array('root'=>'Yellow'));
//delete_tree_all(array('root'=>'Meat'));
//delete_tree_item(array('root'=>'Meat'));

//insert_tree('','','bigboss');
//insert_tree(array('root'=>'Red'),'','dalao');
//insert_tree(array('root'=>'Red'),array('root'=>'Cherry'),'baddalao');
//insert_tree(array('root'=>'Fruit'),array('root'=>'Red'),'Redbother');

 

分享到：
| 周排行、月排行榜开发总结
评论
1 楼 小胖vs小猪 2011-12-27  
第2种方法还需要对每个数据排序号，会不会太麻烦了...
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    ASP+ACCESS二叉树左右值无限级分类,支持增,删,改,查,排序

    无限级分类通常使用左值右值法（也称为闭包表法），通过两个字段来记录每个节点的左右边界。新增节点时，可以在适当的位置插入新的左值和右值；删除节点时，需要更新受影响的节点的左值和右值；修改节点位置时，同样...

    无限级分类/多级分类【左右值方式实现】

    左右值法（Left-Right Value）是实现无限级分类的一种高效策略，它通过为每个节点分配两个数值（左值和右值）来表示节点在整个树中的位置。 首先，我们需要理解基本概念。在左右值法中，每个分类都有一个左值和一个...

    无限级树形结构（增、删、改、排序+TreeView显示）

    在IT领域，无限级树形结构是一种常见的数据组织方式，特别是在构建层次化数据展示或管理的系统时。本文将深入探讨无限级树形结构的概念、实现方式，以及如何结合Asp.Net技术，利用TreeView控件进行展示，并涵盖增、...

    无限级别树形结构类别编辑ASP+ACCESS完美版

    标题中的“无限级别树形结构类别编辑ASP+ACCESS完美版”指的是一个基于ASP（Active Server Pages）编程语言和ACCESS数据库的程序，它能够创建和管理具有无限层级的分类树状结构。这种结构常用于网站导航、目录管理...

    SQL Server 存储层级数据实现无限级分类,左右值分类

    ### SQL Server 存储层级数据实现无限级分类与左右值分类 #### 一、背景介绍 在处理具有层级关系的数据时，例如商品分类、组织架构等，传统的递归方法虽然直观，但在层级较深的情况下会导致性能问题。为解决这一...

    ASP+ACCESS动态二级树形产品导航菜单(黄生原创作品)

    这个系统由黄生原创设计，旨在提供一种高效、直观的产品分类展示方式，帮助用户快速找到所需产品。 ASP（Active Server Pages）是微软开发的一种服务器端脚本语言，用于生成动态网页。在ASP中，开发者可以使用...

    解析左右值无限分类的实现算法

    一、引言产品分类，多级的树状结构的论坛，邮件列表等许多地方我们都会遇到这样的问题：如何存储多级结构的数据？在PHP的应用中，提供后台数据存储的通常是关系型数据库，它能够保存大量的数据，提供高效的数据检索...

    无限级分类的非递归实现(存储过程版）

    Nested Set Model 则通过左右值系统来表示分类的嵌套关系，适合频繁的插入、删除和查询操作。 总结来说，非递归实现的无限级分类存储过程版提供了一种高效、灵活的方法来处理多层次的分类数据，尤其在大数据量和...

    php+mysql实现无限级分类

    在实现无限级分类的核心逻辑中，需要编写基础函数来递归或通过LIKE查询获取所有分类数据，并返回一个排序后的分类数组。这里提供一个使用递归实现的函数`ReadClass`： ```php function ReadClass($datatable, $...

    php通过前序遍历树实现无需递归的无限极分类

    这里的`lft`和`rgt`字段是用于存储树结构的左右值，它们是实现无限级分类的关键。左右值法（也称为Materialized Path）是一种有效的方法，可以快速地进行分类操作，比如查找子节点或同级节点。 在前序遍历中，我们...

    Ajax 四级导航菜单ASP+Access动态版

    文字从左边移动到右边，JS循环控制 JavaScript使用indexOf搜索字符串并返回位置 Javascript文字左右反弹的效果代码 CSS最简单的阴影文字特效 JavaScript隐藏显示文字 JavaScript控制字符大小写转换 JS逐字变化文字...

Magicbox
Global site tag (gtag.js) - Google Analytics