59

我正在编写一个由 Tree 和 TreeNode 组合而成的数据树结构。树将包含对数据的根和顶级操作。我正在使用 UI 库以 Windows 形式呈现树，我可以将树绑定到 TreeView。

我需要将这棵树和节点保存在数据库中。保存树并获得以下功能的最佳方法是什么：

  1. 直观的实施。
  2. 易于绑定。将很容易从树移动到数据库结构并返回（如果有的话）

我有2个想法。第一个是将数据序列化到表中的一个行中。第二个是保存在表中，但是当移动到数据实体时，我会在更改的节点上松开表上的行状态。

有任何想法吗？

4

8 回答 8

52

我已经为这个关于 SQL-Antipatterns 的幻灯片添加了书签，其中讨论了几种替代方案：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
于 2010-11-28T16:43:44.590 回答
41

最简单的实现是邻接表结构：

id  parent_id  data

但是，某些数据库，尤其是MySQL.，在处理此模型时存在一些问题，因为它需要运行递归查询的能力，而这是MySQL缺乏的。

另一种模型是嵌套集：

id lft rgt data

其中lft和rgt是定义层次结构的任意值（任何孩子的lft,rgt应该在任何父母的lft,内rgt）

这不需要递归查询，但它更慢且更难维护。

但是，在MySQL这方面可以使用SPATIALabitities 进行改进。

在我的博客中查看这些文章：

以获得更详细的解释。

于 2010-02-01T10:21:01.750 回答
11

我很惊讶没有人提到物化路径解决方案，这可能是在标准 SQL 中使用树的最快方法。

在这种方法中，树中的每个节点都有一个列path，其中存储了从根到节点的完整路径。这涉及非常简单和快速的查询。

看看示例表节点：

+---------+-------+
| 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), '.%')

请记住，应该为列路径编制索引，以便使用LIKE子句快速执行。

于 2012-11-02T21:21:06.773 回答
8

如果你使用的是 PostgreSQL，你可以使用ltreecontrib 扩展中的一个包（默认提供），它实现了树数据结构。

从文档：

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)
于 2016-09-23T14:56:12.443 回答
6

这取决于您将如何查询和更新数据。如果您将所有数据存储在一行中，则它基本上是一个单元，您无法在不重写所有数据的情况下查询或部分更新。

如果要将每个元素存储为一行，则应首先阅读在 MySQL 中管理分层数据（特定于 MySQL，但该建议也适用于许多其他数据库）。

如果您只访问一整棵树，则邻接表模型使得在不使用递归查询的情况下很难检索根下的所有节点。如果您添加一个链接回头部的额外列，那么您可以SELECT * WHERE head_id = @id在一个非递归查询中获取整个树，但它会使数据库非规范化。

一些数据库具有自定义扩展，可以更轻松地存储和检索层次结构数据，例如 Oracle 有CONNECT BY。

于 2010-02-01T10:19:03.013 回答
3

由于这是在谷歌搜索中询问“sql 树”时的最佳答案，我将尝试从今天（2018 年 12 月）的角度来更新它。

大多数答案暗示使用邻接列表既简单又慢，因此推荐其他方法。

自版本 8（2018 年 4 月发布）以来，MySQL 支持递归公用表表达式 (CTE)。MySQL 有点晚了，但这开辟了一个新的选择。

这里有一个教程，解释了使用递归查询来管理邻接列表。

由于递归现在完全在数据库引擎中运行，它比过去快得多（当它必须在脚本引擎中运行时）。

此处的博客给出了一些测量值（这些测量值都是有偏差的，并且是针对 postgres 而不是 MySQL），但它表明邻接列表不必很慢。

所以我今天的结论是：

  • 如果数据库引擎支持递归，简单的邻接表可能足够快。
  • 用你自己的数据和你自己的引擎做一个基准测试。
  • 不要相信过时的建议来指出“最佳”方法。
于 2018-12-12T20:02:23.300 回答
0

最好的方法，我认为确实是给每个节点一个id和一个parent_id，其中父id是父节点的id。这有几个好处

  1. 当你想更新一个节点时，你只需要重写那个节点的数据。
  2. 当您只想查询某个节点时，您可以准确地获得您想要的信息，从而减少数据库连接的开销
  3. 许多编程语言都具有将 mysql 数据转换为 XML 或 json 的功能，这将使使用 api 打开应用程序变得更加容易。
于 2011-04-06T16:29:40.480 回答
0

类似于表“节点”的东西，其中每个节点行都包含父 ID（除了普通节点数据）。对于 root，父级为 NULL。

当然，这会使查找子节点更加耗时，但这样实际的数据库将非常简单。

于 2010-02-01T10:21:45.773 回答