树状数据结构存储方式（查询篇）-php教程

正在一样平常营业开发中，咱们经常会遇见一些具备条理构造的树状数据。而正在用关系型数据库存储时，往往将这类数据构造以一种称为邻接列表的模子进行存储，像这样：

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;

这个模子体现的图为：

这类数据模子置信不少人曾经很相熟了，这里就没有作过多的赘述。咱们重点来讲说上面这类数据模子

嵌套集模子

而示意树的另外一种形式，是将它作为一个荟萃进行存储。咱们从新界说下表构造：

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;

而这个模子的图就是会像上面：

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 两个参数就算出其有几何个子元素。

总结

两种模子各有好坏，一种优于拔出，一种优于查问。尽管我倾向于嵌套集模子，然而仍是需求依据特定营业来选用。

以上就是树状数据构造存储形式（查问篇）的具体内容，更多请存眷资源魔其它相干文章！