如何在SQL中表示数据树？

Question

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

我需要在DB中保存这个树和节点.保存树并获得以下功能的最佳方法是什么:

1. 直观的实施.
2. 轻松绑定.很容易从树移动到DB结构并返回(如果有的话)

我有两个想法.第一种是将数据序列化为表格中的单行.第二种是保存在表中,但是当移动到数据实体时,我将在更改的节点上松开表上的行状态.

有任何想法吗？

Answer 1

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

id  parent_id  data

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

另一个模型是嵌套集:

id lft rgt data

其中,lft和rgt是定义层次任意值(任何孩子的lft,rgt应在任何父母的lft,rgt)

这不需要递归查询,但它更慢,更难维护.

但是,MySQL使用SPATIALabitilies 可以改善这一点.

请参阅我的博客中的这些文章:

• 邻接列表与嵌套集:PostgreSQL
• 邻接列表与嵌套集:SQL Server
• 邻接列表与嵌套集:Oracle
• 邻接列表与嵌套集:MySQL

有关更详细的解释.

Answer 2

我已经为这个关于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

Answer 3

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

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

看一下示例表节点:

+---------+-------+
| 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子句快速执行.

Answer 4

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

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

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

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

Answer 5

如果您使用的是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)

Answer 6

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

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

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

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

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

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

所以我今天的结论是：

• 如果数据库引擎支持递归，简单邻接表可能足够快。
• 使用您自己的数据和您自己的引擎进行基准测试。
• 不要相信过时的建议来指出“最佳”方法。