您的位置:澳门402永利com > 关于计算机 > 极致分类

极致分类

发布时间:2019-09-23 20:45编辑:关于计算机浏览(86)

    大家平常须求在关系型数据库中保留一些树状结构数据,举个例子分类、菜单、论坛帖子树状回复等。常用的法子有三种:

    1. 领接表的秘技;

    2. 预排序遍历树格局;

    一经树状结构如下图:

    图片 1

    领接表方式

    第一依赖于一个 parent 字段,用于指向上级节点,将紧邻的上下级节点连接起来,id 为自发性递增自动,parent_id 为上级节点的 id。一清二楚, Java 是 Language 的子节点。

    作者们要显得树,PHP 代码也能够很直观,代码如下:

    复制代码 代码如下:

    <?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 '<div style="margin-left:' . ($level * 12) . 'px">' . $row['name'] . '</div>';
    // 递归调用当下函数,显示再下拔尖的子节点
    show_children($row['id'], $level + 1);
    }
    }
    ?>

    想要展现全数树结构,调用 show_children()。想要展现 Database 子树,则调用 show_children(2),因为 Database 的 id 是 2。

    再有一个时时利用的成效是获取节点路线,即给出一个节点,再次来到从根节点到近些日子节点的路线。用函数实现如下:

    复制代码 代码如下:

    <?php
    /**
    * @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)。此算法是在首先种方法的基本功之上,给每种节点增添一个左、右数字,用于标记节点的遍历顺序,如下图所示:

    图片 2

    从根节点开始侧面为 1,然后下叁个节点的左侧为 2,依此类推,到最低层节点之后,最低层节点的左边手为其右边手的数字加 1。顺着那么些节点,我们得以很轻便地遍历完整个树。根据上图,我们对数据表做一些改观,扩展五个字段,lft 和 rgt 用于存款和储蓄左右数字(由于 left 和 right 是 MySQL 的保留字,所以大家改用简写)。表中各行的内容也就改为了:

    图片 3

    接下去看看展现树/子树是何其轻巧,只供给一条 SQL 语句就可以,举个例子显示Database 子树,则要求得到到 Database 的左右数字,左为 2,右为 11,那么 SQL 语句是:

    复制代码 代码如下:

    SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

    SQL 语句是总结了,但大家所期望的缩进展现却是个难题。哪一天应该展现缩进?缩进多少单位?消除那一个标题,须要选取仓库,即后进先出(LIFO),每到二个节点,将其左侧的数字压入仓库中。大家掌握,全数节点侧面的值都比其父节点右侧的值小,那么将日前节点左边的值和储藏室最顶上部分的左侧值举办比较,要是当前节点比货仓最下边包车型客车值小,表示最近仓库里边剩下的都以父节点了,那时能够显示缩进,酒馆的元素数量正是缩进深度。PHP 代码实现如下:

    复制代码 代码如下:

    <?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 '<div style="margin-left:'.(count($stack)*12).'px">'.$row['name'].'</div>';
    // 将这几天的节点压入仓库里边,为循环后面的节点缩进展现做好计划
    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;

    图片 4

    PHP 函数完结如下:

    复制代码 代码如下:

    <?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。

    本文由澳门402永利com发布于关于计算机,转载请注明出处:极致分类

    关键词: