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，来提高性能。