Hierarchical Data Pattern

Tree Structure 是一种很常见的需求(像分类,目录等),关系数据库中,有几种经典模式:

  • Adjacency List Model
  • Nested Set Model
  • Nested Interval Model
  • Materialized Path Model

关于这几种模式的一些通用介绍,参考:

Ruby Toolbox 中一些对 Tree 的通用库:


1. Adjacency List Model

Use ancestry. It has more powerful query capabilities as it implements the materialized path pattern, as opposed to acts_as_tree that implements adjacency list.

父节点引用的方式(也称父节点引用模式),将树形结构中的每个节点单独存放到一个文档中,并在每个文档中保存节点的父节点引用。 考虑以下数据结构:

id type(*optional) parent_id depth
1 course 1
5 section 1 1
7 courseware 5 2
8 courseware 5 2

查询出该课程:

1
2
3
4
5
6
7
8
9
10
11
12
13
SELECT t1.type AS lev1, t2.type as lev2, t3.type as lev3
FROM structs AS t1
LEFT JOIN structs AS t2 ON t2.parent_id = t1.id
LEFT JOIN structs AS t3 ON t3.parent_id = t2.id
WHERE t1.id = 1;
+-------------+----------------------+-----------------+
| lev1 | lev2 | lev3 |
+-------------+----------------------+-----------------+
| course(1) | section(5) | courseware(7) |
| course(1) | section(5) | courseware(8) |
+-------------+----------------------+-----------------+

.1 优势

实现起来特别简单,因为只是存储 parent_id,没有多余的算法。

.2 不足

如果想构造一根树,在 DB 查询时,需要太多次循环调用。产生性能问题。

Recursive CTEs

Generating Depth based tree from Hierarchical Data in MySQL (no CTEs)

.3 Rails 实现

Organise ActiveRecord model into a tree structure

.4 REF


2. Nested Set Model

.1 Nested Set (前置树)领域模型模式

对应到的 DB Scheme 如下(p_id 非必须,depth 也非必须):

id type(*optional) parent_id lft rgt depth
1 course 1 8 0
5 section 1 2 7 1
7 courseware 5 3 4 2
8 courseware 5 5 6 2

如果只是这样看的话,lft, rgt 很难看明白,但换成下面的图,就立即清晰了。

.2 原理

它构建了一个森林(整体),而不是一棵棵的树。

读时,是通过一个条件,将大于根左并且小于根右的全读出即可。

写时,因为整体的原因,在第一颗树上的任意修改,都会反应到后面的树上。

查询该课程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
SELECT structs.id
FROM structs AS node,
structs AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND parent.id = 1
ORDER BY node.lft;
+-------------+
| id |
+-------------+
| 1 |
| 5 |
| 7 |
| 8 |
+-------------+

查询出所有的叶节点:

1
2
3
4
5
6
7
8
SELECT id FROM structs WHERE rgt = lft + 1;
+--------------+
| id |
+--------------+
| 7 |
| 8 |
+--------------+

.3 明测

480W 条数据,在最前部加入一个新节点(对 DB 所有记录 lft rft 进行 +2 的方式,全局更新),耗费 97s。😂

可见,这个将会是很严重的性能问题。

不过有种办法可以 fix 这个问题,就是在将森林还原为一棵棵树,每次操作只对树进行,不会影响到其它的树。

这样的话,每颗树的的 lft rgt 0 开始,看起来也清楚点。只是不能跨树进行移动。

.4 REF

.5 Rails 实现


3. Nested Interval Model

跟 Nested Set 差不多,也是有左右的。

.4 Rails 实现


4. Materialized Path Model

Materialized Path(物化路径)通过在数据中加入它的一个路径,来实现层级关系。

DB Scheme

id type(*optional) path depth(*optional)
1 course / 1
5 section /1/ 2
7 courseware /1/5/ 3
8 courseware /1/5/ 3

找到所有的 Root

1
2
-- find all ROOT
SELECT * FROM structures WHERE path="/"

找到课程1下的所有章节或课件

1
2
3
4
5
-- find all sections
SELECT * FROM structs WHERE path="/1/%" AND deep=2
-- find all coursewares in the course
SELECT * FROM structs WHERE path="/1/%" AND deep=3

性能

可能在 path 上加上 Index,来提高性能。