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

【虚拟资源买卖网www.cnused.com】源码虚拟资源交易平台,免费开通VIP商户!
吆喝资源网官方客服QQ:787749153官方唯一QQ号码
文字广告位招租      好位置不等人!200元/月

邻接列表模型

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

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中文网,吆喝网(http://yaoohe.com)搜集整理,如有疑问请联系本站客服!

本文由 吆喝资源网 作者:shijian 发表,其版权均为 吆喝资源网 所有,文章内容系作者个人观点,不代表 吆喝资源网 对观点赞同或支持。如需转载,请注明文章来源。

0

发表评论