• 技术文章 >后端开发 >php教程

    树状数据结构存储方式(查询篇)

    藏色散人藏色散人2019-09-07 11:05:30转载276
    邻接列表模型

    在日常业务开发中,我们常常会碰见一些具有层次结构的树状数据。而在用关系型数据库存储时,往往将这种数据结构以一种称为邻接列表的模型进行存储,像这样:

    CREATE TABLE `categories` (
      `id` int(11) NOT NULL AUTO_INCREMENT,
      `title` char(100) NOT NULL,
      `pid` int(11) DEFAULT 0,
      PRIMARY KEY (`id`)
    ) ENGINE=InnoDB;

    9d5f19b07b3048ef83d3aff343f5362.png

    这个模型表现的图为:

    e2aa18e5a20bb294b6035d31138101e.png

    这种数据模型相信很多人已经很熟悉了,这里就不作过多的赘述。我们重点来说说下面这种数据模型

    嵌套集模型

    而表示树的另一种方式,是将它作为一个集合进行存储。我们重新定义下表结构:

    CREATE TABLE `categories` (
      `id` int(11) NOT NULL AUTO_INCREMENT,
      `title` char(100) NOT NULL,
      `lft` int(11) NOT NULL UNIQUE CHECK (lft> 0),
      `rgt` int(11) NOT NULL UNIQUE CHECK (rgt> 1),
      PRIMARY KEY (`id`)
    ) ENGINE=InnoDB;

    c9480ba6f6328d9404c8540364b6041.png

    而这个模型的图就是会像下面:

    8426f06de80f225f7dec4f4a5a0037d.png

    lft 和 rgt 是作为集合的边界,两者差值越大,则集合越大,里面的元素就越多。

    根据子集,查找父级的分类

    SELECT c2.* 
      FROM categories as c1, categories as c2
      WHERE c1.lft BETWEEN c2.lft and c2.rgt 
          AND c1.title = '华为';
    +----+-------------+-----+-----+
    | id | title       | lft | rgt |
    +----+-------------+-----+-----+
    |  1 | Smartphones |   1 |  14 |
    |  5 | Harmony OS  |  10 |  13 |
    |  8 | 华为        |  11 |  12 |
    +----+-------------+-----+-----+

    根据父级,查找其底下所有的子集

    SELECT c1.*
       FROM categories AS c1, categories AS c2
      WHERE c1.lft BETWEEN c2.lft AND c2.rgt
        AND c2.title = 'Smartphones';
    +----+-------------+-----+-----+
    | id | title       | lft | rgt |
    +----+-------------+-----+-----+
    |  1 | Smartphones |   1 |  14 |
    |  3 | Android     |   2 |   5 |
    |  4 | iOS         |   6 |   9 |
    |  5 | Harmony OS  |  10 |  13 |
    |  6 | 小米        |   3 |   4 |
    |  7 | iPhone      |   7 |   8 |
    |  8 | 华为        |  11 |  12 |
    +----+-------------+-----+-----+

    查看各个分类的级别

     SELECT COUNT(c2.id) AS indentation, c1.title
      FROM categories AS c1, categories AS c2下周三we'fv
      WHERE c1.lft BETWEEN c2.lft AND c2.rgt
      GROUP BY c1.title
      ORDER BY c1.lft;
    +-------------+-------------+
    | indentation | title       |
    +-------------+-------------+
    |           1 | Smartphones |
    |           2 | Android     |
    |           3 | 小米        |
    |           2 | iOS         |
    |           3 | iPhone      |
    |           2 | Harmony OS  |
    |           3 | 华为        |
    +-------------+-------------+

    优缺

    邻接列表模型

    邻接列表模型很容易理解,我们需要的代码也很简单。

    但是在大多数编程语言中,它是缓慢而低效的。这主要是由递归引起的。我们需要为树中的每个节点进行一次数据库查询。

    由于每个查询都需要一些时间,因此在处理大型树时这会使函数变得非常慢。因为对于每个函数来说,是需要以一种递归的算法来实现数的获取。

    当然,如果用 List 这种对递归亲和的语言来说,可以忽略这种数据模型的缺点。但是对 PHP 来说,却会使得整个在处理这种数据模型的时候,变得特别慢。

    嵌套集模型

    相较于邻接列表模型,这种数据模型显然并不是那么好理解。并且不能那么简单的添加数据,它需要在添加的时候计算左右两边的数值,并挪动以后的数值,这增加了添加数据的压力。

    同样,它带来的好处是,可以让你以一条简单的查询,就完成一个树的查询,可以根据 lft 和 rgt 两个参数就算出其有多少个子元素。

    总结

    两种模型各有优劣,一种优于插入,一种优于查询。虽然我偏向于嵌套集模型,但是还是需要根据特定业务来选用。

    以上就是树状数据结构存储方式(查询篇)的详细内容,更多请关注php中文网其它相关文章!

    phpstudy集成环境下载
    本文转载于:learnku,如有侵犯,请联系a@php.cn删除
    专题推荐:数据结构
    上一篇:php实现进度条原理 下一篇:在 PHP 中格式化并高亮 SQL 语句

    相关文章推荐

    • mysql索引的数据结构是什么• navicat怎么导出数据结构• 程序员,你应该知道的数据结构之栈• 什么是数据结构Hash表(哈希表)?又有哪些具体操作呢?

    全部评论我要评论

  • 取消发布评论发送
  • 1/1

    PHP中文网