树状数据结构存储方式（查询篇）

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

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

总结

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

以上就是树状数据结构存储方式（查询篇）的详细内容，更多请关注教程集其它相关文章！

您可能感兴趣的文章：
树状数据结构存储方式（查询篇）
php与mysql实现的无限级分类
golang key map 所有_golang系列——高级语法之map
数据结构与算法–四叉树（javascript实现）
数据结构-树和二叉树(Golang)
浅谈MySQL索引 实用又方便的方法
树状数据结构存储方式（CUD 篇）
数据结构中树与二叉树基础算法的比较
数据结构和算法(Golang实现)(29)查找算法-2-3树和左倾红黑树
深入分析MySQL数据库索引