6

这是对以下内容的跟进：
MySQL - 是否可以获取层次结构中的所有子项？

我有一个任意深度的邻接列表模型表（我可以将它转换为嵌套集模型。

我阅读了有关如何使用嵌套集合模型的 MySQL 数据，尽管执行插入、更新和删除等基本功能似乎变得越来越复杂和非常复杂。

另一个博客展示了如何使用带有邻接列表模型的触发系统来保存将每个对象与其祖先相关联的祖先表。

现在我需要能够返回给定节点的所有子节点的列表，以更改或删除它们。这种层次结构一旦创建就不会一直在变化，但是会有大量的层次结构。

我看到的三种方法是：

  1. 创建了一个存储过程，它将执行返回所有子级的递归查询。

  2. 转换为嵌套集模型，这需要处理复杂性并可能创建一个存储过程来添加、编辑和删除。

  3. 在插入/删除触发器上创建上述祖先表以处理所有数据。

如果还有其他方法我没有探索，请告诉我，我会更新这个列表。

4

5 回答 5

4

Quassnoi对嵌套集模型和邻接表模型进行了一些性能测试，并在他的博客文章邻接表与嵌套集：MySQL中记录了结果和建议。执行摘要如下：

  • 对于获取所有子节点或所有父节点，嵌套集更快。
  • 如果您经常需要更新表，嵌套集是个坏主意。

以下是他文章的结论：

在 MySQL 中，如果对层次结构的更新不频繁，并且在更新期间锁定表是可以承受的（在长表上可能需要几分钟），则应该首选嵌套集模型。

这意味着使用 MyISAM 存储引擎创建表，如上所述创建 GEOMETRY 类型的边界框，使用 SPATIAL 索引对其进行索引并将级别持久保存在表中。

如果表的更新很频繁，或者更新隐含的长时间锁定表是负担不起的，那么应该使用邻接表模型来存储分层数据。

这需要创建一个函数来查询表。

本文的其余部分展示了如何定义表、实现查询并给出性能测量。空间索引的使用是提高嵌套集模型性能的一个聪明想法，这对您来说可能是新的。

如果您还在考虑不使用 MySQL 的方法，那么您可能需要查看PostgreSQL，它是另一个免费的开源数据库。PostgreSQL 支持递归公用表表达式形式的递归查询，这使得查询层次结构数据比 MySQL 更容易，也提供更好的性能。Quassnoi 还写了一篇文章Adjacency list vs. nested sets: PostgreSQL显示了细节。

在我们讨论其他方法的同时，Oracle 的数据库也值得一提。Oracle 也有一个自定义扩展CONNECT BY，它使查询层次结构数据变得非常容易和快速。Quassnoi 的文章Adjacency list vs. nested sets：Oracle再次涵盖了性能细节。在这种情况下，您需要获取所有孩子的查询非常简单：

SELECT *
FROM yourtable
START WITH id = 42
CONNECT BY parent = PRIOR id
于 2010-07-01T23:38:24.780 回答
2

为了简单和方便，我总是使用嵌套集。我总是建议这篇文章。它显示了处理此类分层数据所需的出色查询。我在这里看到的唯一缺点是，当层次结构达到一定程度的复杂性时，插入/更新新记录会变慢，但读取速度比我见过的许多其他解决方案要快。

只是给你一个上面文章的例子：

SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS';

+-------------+----------------------+--------------+-------+
| lev1        | lev2                 | lev3         | lev4  |
+-------------+----------------------+--------------+-------+
| ELECTRONICS | TELEVISIONS          | TUBE         | NULL  |
| ELECTRONICS | TELEVISIONS          | LCD          | NULL  |
| ELECTRONICS | TELEVISIONS          | PLASMA       | NULL  |
| ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS  | FLASH |
| ELECTRONICS | PORTABLE ELECTRONICS | CD PLAYERS   | NULL  |
| ELECTRONICS | PORTABLE ELECTRONICS | 2 WAY RADIOS | NULL  |
+-------------+----------------------+--------------+-------+
6 rows in set (0.00 sec)

SQL 方面，我认为它不会变得更漂亮和更简单；）

我不知道存储过程的方式。但由于它涉及递归（在你的情况下），我不知道它是否会在层次结构中的许多级别上很快。我想你可以试一试。

于 2010-06-29T05:56:35.467 回答
1

在处理分层数据集时，我发现最好考虑缓存。以这种方式处理此问题的主要好处之一是它不需要将您的数据库反规范化为可能更难以变异的东西。

由于内存堆的（memcache、redis 等）查找比 SQL 快得多id -> data，因此我将使用它们来缓存每个节点的直接子节点的 id 列表。这样，您可以通过递归算法为任何节点构建完整的列表来获得不错的性能。

要添加/删除一个新节点，您只需要使其'直接父缓存无效O(1)。

如果这还不够快，您可以在每个节点的节点的所有子节点列表中添加另一层缓存。为了使它能够与一个相当可变的数据集一起工作，您应该记录每个节点的缓存性能（新/缓存命中的比率），并为何时存储缓存设置一个容差级别。这也可以存储在内存堆中，因为它是非重要数据。

如果您使用这种更高级的缓存模型，您需要注意这些完整的子节点列表在其任何子节点发生更改时都需要失效O(log n)。

获得子 ID 列表后，您可以使用 SQL 的WHERE id IN( id1, id2, .... )语法来查询您想要的内容。

于 2010-07-07T00:29:17.167 回答
1

也许你应该考虑使用像MongoDB这样的面向文档的数据库。它可以让你的生活更轻松。

于 2010-07-02T00:01:32.267 回答
0

我曾经不得不将一个复杂的分层任意深度的物料清单系统存储在一个类似 SQL 的数据库管理器中，但它并不能真正胜任这项任务，它最终导致了混乱和棘手的索引、数据定义、查询等. 重新启动后，使用 db manager 只提供一个 API 用于对简单索引键的记录读取和写入，并在外部代码中完成所有实际输入/操作/报告，最终结果实现更快，更容易理解，并且更易于维护和增强。需要的最复杂的查询本质上是 SELECT A FROM B。

因此，与其在 MySQL 的限制中嵌入逻辑和操作，不如考虑敲出代码来做你想做的事，并且只依赖 MySQL 进行最低级别的 get/puts。

于 2010-07-02T01:23:56.623 回答