JustQyx

大道至简

Tree Data

| Comments

对于树形结构的数据存储,schema 的设计通常很简单,难的是其查询是否简单、方便。
这里我所选用的数据库为:PostgreSQL,版本为:9.3.5

数据结构设计

对于树形结构数据的存储,如一个企业的部门,schema 通常设计成这样子:

1
2
3
4
5
   Column   |            Type             |                        Modifiers
------------+-----------------------------+----------------------------------------------------------
 id         | integer                     | not null default nextval('departments_id_seq'::regclass)
 name       | character varying(255)      |
 parent_id  | integer                     |

理论上,这样的设计可以支持无限级,但,这里我不针对这种设计做讨论。

ancestry,a rails gem

官方的一句话介绍

Organise ActiveRecord model into a tree structure

RUBY 有几个专门处理树形结构的 GEM,上 RUBY TOOLBOX 一搜就可知道有哪些。
因为公司项目里采用了 ancestry,所以这里也只是分享在这方面的实践。

采用 ancestry 后,我们的表 schema 变成:

1
2
3
4
5
6
7
8
   Column   |            Type             |                        Modifiers
------------+-----------------------------+----------------------------------------------------------
 id         | integer                     | not null default nextval('departments_id_seq'::regclass)
 name       | character varying(255)      |
 ancestry   | character varying(255)      |
Indexes:
    "departments_id_pkey" PRIMARY KEY, btree (id)
    "departments_ancestry" btree (ancestry)

这是一些 Demo Data:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  id  |     name     | ancestry
------+--------------+----------
    1 | root        |
    2 | 产品研发中心  | 1
    5 | 研发部       | 1/2
    6 | 产品部       | 1/2
   11 | 运营部       | 1/2
   12 | 内容开发中心  | 1
   13 | 内容部       | 1/12
   15 | 视频部       | 1/12
   16 | 行政中心     | 1
   19 | 财务部       | 1/16
   21 | 人力资源部   | 1/16
   25 | 行政部      | 1/16
    8 | 品牌市场中心 | 1

用字符串类型的 ancestry 字段类替代常用的 parent_id,用以说明它从根结点到它的直接父结点的路径。
例如:id 为 11 的记录,ancestry 的值为 1/2,它的父结点的路径为:root/产品研发中心

使用这种规则,你可以很方便地查询一些数据,如产品研发中心这个节点下面的所有子结点:

1
SELECT id, name FROM departments WHERE ancestry LIKE '1/%'

ancestry 提供了一些好用的函数,让你能够直接做一些数据查询。乖,点这里

arrange_serializable

ancestry 提供的 arrange_serializable 方法,可以将查询出来的数据,转换成数据结构的数据。

1
Department.where(client_id: 1).arrange_serializable
1
2
3
4
5
6
7
8
9
10
11
12
[{
    id: 1,
    name: "root",
    children: [
        { id: 2, name: "产品研发中心", children: [{...},{...}] },
        { id: 12, name: "内容开发中心", children: [{...},{...}] }
    ]
},
{
  #...
}
]

使用数据库函数实现

除了上面 ancestry 所提供的方法,我们还可以在数据库里创建 FUNCTION,让其能够去收集一个结点的子结点的数据。
使用 PL/pgSQL 脚本,代码如下:

(select_subtree.sql) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
-- 创建获取子节点的函数
CREATE OR REPLACE FUNCTION collect_childs_func(dept_id INTEGER, ancestry CHARACTER VARYING(255)) RETURNS TEXT AS $$
DECLARE
  -- 初始化变量
  child_ancestry CHARACTER VARYING(255);
  dept RECORD;
  children TEXT;
  childs TEXT[] = '{}';
BEGIN
  -- 得到查子节点的 ancestry 变量
  IF ancestry IS NULL THEN
    child_ancestry := dept_id;
  ELSE
    child_ancestry := (ancestry || '/' || dept_id);
  END IF;

  -- 查询其子部门
  FOR dept IN SELECT * FROM departments WHERE departments.ancestry = child_ancestry ORDER BY departments.id LOOP
    IF dept.ancestry IS NULL THEN
      childs := ARRAY_APPEND(childs, '{ "id": ' || dept.id || ', "name": "' || dept.name || '", "children": []}');
    ELSE
      childs := ARRAY_APPEND(childs, '{ "id": ' || dept.id || ', "name": "' || dept.name || '", "children":' || collect_childs_func(dept.id, dept.ancestry) || '}');
    END IF;
  END LOOP;

  children := ARRAY_TO_STRING(childs, ',');
  children := '[' || children || ']';

  RETURN children;
END;
$$ LANGUAGE plpgsql

通过 psql -d dbname 打开一个会话(即连接到数据库),执行上面的代码,然后就可以使用我们刚创建的 FUNCTION 了 如下(项目里的 departments 表实际还有一个 client_id 字段):

1
SELECT id, name, collect_childs_func(id, NULL) AS children FROM departments WHERE client_id = 1 AND ancestry IS NULL;

出来的结果大概是这样子的:

1
2
3
id       | 1
name     | root
children | [{ "id": 2, "name": "产品研发中心", "children":[{ "id": 5, "name": "研发部", "children":[]},{ "id": 6, "name": "产品部", "children":[]},{ "id": 11, "name": "运营部", "children":[]}]},{ "id": 8, "name": "品牌市场中心", "children":[]},{ "id": 12, "name": "内容开发中心", "children":[{ "id": 13, "name": "内容部", "children":[]},{ "id": 15, "name": "视频部", "children":[]}]},{ "id": 16, "name": "行政中心", "children":[{ "id": 19, "name": "财务部", "children":[]},{ "id": 21, "name": "人力资源部", "children":[]},{ "id": 25, "name": "行政部", "children":[]},{ "id": 6237, "name": "新增部门", "children":[]},{ "id": 6238, "name": "新增部门", "children":[]}]},{ "id": 31, "name": "体验客户", "children":[]},{ "id": 2597, "name": "专家组", "children":[]},{ "id": 5846, "name": "测试部门", "children":[]},{ "id": 6390, "name": "质检部门", "children":[{ "id": 6391, "name": "质检一组", "children":[]}]}]

得到的 children 是一个字符串类型,只需要简单 parse 一下,或者直接返回给客户端即可。

删除

1
DROP FUNCTION collect_childs_func(dept_id INTEGER, ancestry CHARACTER VARYING(255))

应用到 production

因为创建函数需要较高的权限,所以为避免错误,直接在线上的数据库跑一下代码即可,而不要写在 migration 里,然后在项目文档里写一下说明即可。 如果你的项目的数据库有很多台,就再去考虑自动化的事情就好了。

References

Comments