我正在编写一个数据树结构，它由Tree和TreeNode组合而成。Tree将包含根以及对数据的顶层操作。
我正在使用一个UI库在Windows窗体中呈现树形结构，可以将树绑定到TreeView。
我需要将这棵树和节点保存在数据库中。最好的保存方式是什么，并具备以下功能：
我有两个想法。第一个是将数据序列化为一行，并存储在表格中。第二个是在表格中保存，但是当移动到数据实体时，我会丢失更改节点的行状态。
有什么想法吗？
我已经收藏了这个关于SQL反模式的Slidshare，其中讨论了几种替代方案：http://www.slideshare.net/billkarwin/sql-antipatterns-strike-back?src=embed
推荐使用闭包表（在幻灯片中有解释）。
以下是总结（第77页）：
| Query Child | Query Subtree | Modify Tree | Ref. Integrity
Adjacency List | Easy | Hard | Easy | Yes
Path Enumeration | Easy | Easy | Hard | No
Nested Sets | Hard | Easy | Hard | No
Closure Table | Easy | Easy | Easy | Yes
最简单的实现是使用邻接表结构：
id parent_id data
然而，一些数据库，特别是 MySQL，在处理这种模型时存在问题，因为它需要能够运行递归查询，而 MySQL 缺乏这种能力。
另一个模型是嵌套集：
id lft rgt data
其中lft和rgt是任意值，用于定义层次结构（任何子级的lft、rgt都应在任何父级的lft、rgt内）。
这不需要递归查询，但速度较慢且难以维护。
然而，在MySQL中可以使用SPATIAL功能来改进此方法。
请参阅我的博客中的这些文章：
以获取更详细的解释。
我很惊讶没有人提到物化路径解决方案，这可能是使用标准SQL处理树形结构的最快方法。
在这种方法中，树中的每个节点都有一个列path，其中存储从根节点到该节点的完整路径。这涉及非常简单和快速的查询。
请查看示例表格node：
+---------+-------+
| node_id | path |
+---------+-------+
| 0 | |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 1.4 |
| 5 | 2.5 |
| 6 | 2.6 |
| 7 | 2.6.7 |
| 8 | 2.6.8 |
| 9 | 2.6.9 |
+---------+-------+
要获取节点x的子节点，您可以编写以下查询:
SELECT * FROM node WHERE path LIKE CONCAT((SELECT path FROM node WHERE node_id = x), '.%')
请记住，path列应该创建索引，以便在使用LIKE子句时能够快速执行。
如果您正在使用PostgreSQL，可以使用ltree，这是一个在contrib扩展中的软件包（默认存在），可实现树形数据结构。
从文档中可以了解到：
CREATE TABLE test (path ltree);
INSERT INTO test VALUES ('Top');
INSERT INTO test VALUES ('Top.Science');
INSERT INTO test VALUES ('Top.Science.Astronomy');
INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics');
INSERT INTO test VALUES ('Top.Science.Astronomy.Cosmology');
INSERT INTO test VALUES ('Top.Hobbies');
INSERT INTO test VALUES ('Top.Hobbies.Amateurs_Astronomy');
INSERT INTO test VALUES ('Top.Collections');
INSERT INTO test VALUES ('Top.Collections.Pictures');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Stars');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts');
CREATE INDEX path_gist_idx ON test USING GIST (path);
CREATE INDEX path_idx ON test USING BTREE (path);
您可以执行如下查询：
ltreetest=> SELECT path FROM test WHERE path <@ 'Top.Science';
path
------------------------------------
Top.Science
Top.Science.Astronomy
Top.Science.Astronomy.Astrophysics
Top.Science.Astronomy.Cosmology
(4 rows)
SELECT * WHERE head_id = @id并在一个非递归查询中获取整个树，但它会使数据库去规范化。由于在Google搜索中查询“sql trees”时，此答案位居榜首，因此我将尝试从今天（2018年12月）的角度进行更新。
大多数答案都暗示使用邻接列表既简单又慢，因此推荐其他方法。
自版本8（发布于2018年4月）以来，MySQL支持递归公共表达式（CTE）。 MySQL有点晚入局，但这开辟了一种新选项。
这里有一个教程链接，介绍了使用递归查询管理邻接列表的用法。
由于递归现在完全在数据库引擎内运行，因此比过去（必须在脚本引擎中运行）快得多。
该博客链接提供了一些测量数据（它们是偏见的且适用于Postgres而不是MySQL），但仍然显示邻接列表不必慢。
所以我的结论是：
你好，我最近在项目中接触到这个，想分享一下我的总结。希望对你有所帮助。首先，我们需要了解一些前提知识。
本质上，这是使用递归调用的闭包表解决方案。感谢那些幻灯片，它们非常有用。我希望在写这篇文章之前能看到它们 :)
这些是调用自身的函数，例如：
function factorial(n) {
if (n = 0) return 1; //base case
return n * factorial(n - 1); // recursive call
}
WITH RECURSIVE t(n) AS (
VALUES (1) -- nonrecusive term
UNION ALL
SELECT n+1 FROM t WHERE n < 100 -- recusive term
--continues until union adds nothing
)
SELECT sum(n) FROM t;
ALTER FUNCTION dbo.fnGetFactorial (@num int)
RETURNS INT
AS
BEGIN
DECLARE @n int
IF @num <= 1 SET @n = 1
ELSE SET @n = @num * dbo.fnGetFactorial(@num - 1)
RETURN @n
END
GO
需要注意的是，树是图形的子集，这可以通过每个节点仅有一个父节点来简单地实现其关系。
我认为，在我们转向sql之前，更理论化地解决问题会更容易。
表示具有无需数据重复的图形关系的简单方法是将nodes(id, data)与边界分开。
然后，我们可以限制edges(parent_id, child_id)表以强制执行我们的约束条件。通过要求parent_id、child_id以及仅仅是child id唯一即可实现。
create table nodes (
id uuid default uuid_generate_v4() not null unique ,
name varchar(255) not null,
json json default '{}'::json not null,
remarks varchar(255),
);
create table edges (
id uuid default uuid_generate_v4() not null,
parent_id uuid not null,
child_id uuid not null,
meta json default '{}'::json,
constraint group_group_id_key
primary key (id),
constraint group_group_unique_combo
unique (parent_id, child_id),
constraint group_group_unique_child
unique (child_id),
foreign key (parent_id) references nodes
on update cascade on delete cascade,
foreign key (child_id) references nodes
on update cascade on delete cascade
);
CREATE VIEW v_edges as (SELECT id as child_id, parent_id FROM nodes)
但是为了提出灵活性的建议，以便我们可以将其他图形结构纳入此框架，我将使用常见的多对多关系结构。这将理想地使这项研究扩展到其他图形算法。
让我们从一个样本数据结构开始。
INSERT (id, my_data) VALUES ('alpha', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('bravo', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('charly', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('berry', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('zeta', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('yank', 'my big data') INTO nodes
INSERT (parent_id, child_id) VALUES ('alpha', 'bravo') INTO edges
INSERT (parent_id, child_id) VALUES ('alpha', 'berry') INTO edges
INSERT (parent_id, child_id) VALUES ('bravo', 'charly') INTO edges
INSERT (parent_id, child_id) VALUES ('yank', 'zeta') INTO edges
-- rank0 Alpha Yank
-- rank1 Bravo Berry Zeta
-- rank2 Charly
（边数e）=（节点数n）-1，每个子节点都只有一个父节点。let n = node
let p = parent
let c = child
let ns = nodes = groups
let es = edges = group_group // because this is a relationship of a group entity to another group entity
现在我们需要问什么样的问题。
"假设有一个任意的组集合's'，假设节点继承它们的子节点，那么图形的覆盖率是多少？"
这是一个棘手的问题，需要我们遍历图形并找到s中每个节点的所有子节点。
这是基于此堆栈溢出帖子的继续。
-- some DBMS (e.g. Postgres) require the word "recursive"
-- some others (Oracle, SQL-Server) require omitting the "recursive"
-- and some (e.g. SQLite) don't bother, i.e. they accept both
-- drop view v_group_descendant;
create view v_group_descendant as
with recursive descendants -- name for accumulating table
(parent_id, descendant_id, lvl) -- output columns
as
( select parent_id, child_id, 1
from group_group -- starting point, we start with each base group
union all
select d.parent_id, s.child_id, d.lvl + 1
from descendants d -- get the n-1 th level of descendants/ children
join group_group s -- and join it to find the nth level
on d.descendant_id = s.parent_id -- the trick is that the output of this query becomes the input
-- Im not sure when it stops but probably when there is no change
)
select * from descendants;
comment on view v_group_descendant is 'This aggregates the children of each group RECURSIVELY WOO ALL THE WAY DOWN THE TREE :)';
有了这个视图之后，我们可以与我们的节点/组合并以获取数据，对于大部分步骤，我不会为每个单独的步骤提供这些示例，我们将只使用ID。
select d.*, g1.group_name as parent, g2.group_name as decendent --then we join it with groups to add names
from v_group_descendant d, groups g1, groups g2
WHERE g1.id = d.parent_id and g2.id = d.descendant_id
order by parent_id, lvl, descendant_id;
样本输出
+------------------------------------+------------------------------------+---+----------+---------+
|parent_id |descendant_id |lvl|parent |decendent|
+------------------------------------+------------------------------------+---+----------+---------+
|3ef7050f-2f90-444a-a20d-c5cbac91c978|6c758087-a158-43ff-92d6-9f922699f319|1 |bravo |charly |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|3ef7050f-2f90-444a-a20d-c5cbac91c978|1 |alpha |bravo |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|7135b0c6-d59c-4c27-9617-ddcf3bc79419|1 |alpha |berry |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|6c758087-a158-43ff-92d6-9f922699f319|2 |alpha |charly |
|42529e8a-75b0-4242-a51a-ac60a0e48868|44758087-a158-43ff-92d6-9f922699f319|1 |yank |zeta |
+------------------------------------+------------------------------------+---+----------+---------+
create view v_group_descendant_all as (
select * from v_group_descendant gd
UNION ALL
select null::uuid as parent_id,id as descendant_id, 0 as lvl from groups g
where not exists (select * from v_group_descendant gd where gd.descendant_id = g.id )
);
comment on view v_group_descendant is 'complete list of descendants including rank 0 root nodes descendant - parent relationship is duplicated for all levels / ranks';
preview
+------------------------------------+------------------------------------+---+----------+---------+
|parent_id |descendant_id |lvl|parent |decendent|
+------------------------------------+------------------------------------+---+----------+---------+
|3ef7050f-2f90-444a-a20d-c5cbac91c978|6c758087-a158-43ff-92d6-9f922699f319|1 |bravo |charly |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|3ef7050f-2f90-444a-a20d-c5cbac91c978|1 |alpha |bravo |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|7135b0c6-d59c-4c27-9617-ddcf3bc79419|1 |alpha |berry |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|6c758087-a158-43ff-92d6-9f922699f319|2 |alpha |charly |
|42529e8a-75b0-4242-a51a-ac60a0e48868|44758087-a158-43ff-92d6-9f922699f319|1 |yank |zeta |
|null |c1529e8a-75b0-4242-a51a-ac60a0e48868|0 |null |alpha |
|null |42529e8a-75b0-4242-a51a-ac60a0e48868|0 |null |yank |
+------------------------------------+------------------------------------+---+----------+---------+
users(id, data)的表和一个user_group(user_id, group_id)关系来获取我们的一组群组基础，我们可以将其与另一个表连接起来，去除重复项，因为我们的用户组关系集合s可能会导致重复，例如如果一个用户被分配给alpha和charly两个群组。+------+--------+
| user | group |
+------+--------+
| jane | alpha |
| jane | charly |
| kier | yank |
| kier | bravo |
+------+--------+
--drop view v_user_group_recursive;
CREATE VIEW v_user_group_recursive AS (
SELECT DISTINCT dd.descendant_id AS group_id, ug.user_id
FROM v_group_descendant_all dd , user_group ug
WHERE (ug.group_id = dd.descendant_id
OR ug.group_id = dd.parent_id) -- should gic
);
SELECT * FROM v_user_group_recursive;
+------+--------+
| user | group |
+------+--------+
| jane | alpha |
| jane | bravo |
| jane | berry |
| jane | charly |
-- | jane | charly | Removed by DISTINCT
| kier | yank |
| kier | zeta |
| kier | bravo |
| kier | charly |
+------+--------+
CREATE VIEW v_user_groups_recursive AS (
SELECT user_id, json_agg(json_build_object('id', id,'parent_id',parent_id, 'group_name', group_name, 'org_id', org_id, 'json', json, 'remarks', remarks)) as groups
FROM v_user_group_recursive ug, v_groups_parent g
WHERE ug.group_id = g.id GROUP BY user_id
);
comment on view v_user_group_recursive is 'This aggregates the groups for each user recursively ';
+------+-------------------------------+
| user | groups |
+------+-------------------------------+
| jane | [alpha, bravo, berry, charly] |
| kier | [yank, zeta, bravo, charly] |
+------+-------------------------------+
这太棒了，我们已经回答了这个问题。现在我们只需要询问这个用户继承了哪些组。
SELECT * from v_user_groups_recursive where user_id = 'kier
此外，我们可以使用类似jstree.com这样的工具来展示我们的结构。
async function getProjectTree(user_id) {
let res = await table.query(format('SELECT * from v_user_groups_recursive ug WHERE ug.user_id = %L', user_id));
if (res.success) {
let rows = res.data[0].groups.map(r => {
return {
id: r.id, // required
parent: r.parent_id==null?'#':r.parent_id,// required
text: r.group_name,// node text
icon: 'P', // string for custom
state: {
opened: true, // is the node open
disabled: false, // is the node disabled
selected: false, // is the node selected
},
li_attr: {}, // attributes for the generated LI node
a_attr: {} // attributes for the generated A node
}
})
return {success: true, data: rows, msg: 'Got all projects'}
} else return res;
}
<div id="v_project_tree" class="row col-10 mx-auto" style="height: 25vh"></div>
<script>
function buildTree() {
bs.sendJson('get', "/api/projects/getProjectTree").then(res => {
bs.resNotify(res);
if (!res.success) {
//:(
console.error(':(');
return
}
console.log(res.data);
$('#v_project_tree').jstree({
'core': {
'data': res.data
}
});
})
}
window.addEventListener('load', buildTree);
</script>
我认为最好的方法是给每个节点一个id和parent_id，其中parent_id是父节点的id。这有几个好处：
类似于名为"nodes"的表，其中每个节点行包含父级ID（除了普通的节点数据）。对于根节点，父级ID为NULL。
当然，这样做会使查找子节点变得稍微耗时，但是这样数据库本身会相当简单。
