mysql-处理分层数据的最佳方法?

Quassnoi 在嵌套集模型和邻接列表模型上运行了一些性能测试,并在他的博客文章中记录了结果和建议。 Adjacency list vs. nested sets: MySQL . 执行摘要是:

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

这意味着使用myisam存储引擎创建表,如上所述创建几何类型的边界框,使用空间索引对其进行索引,并将级别保持在表中。

如果表的更新频繁,或者更新所暗示的长时间锁定表是不经济的,那么应该使用邻接列表模型来存储分层数据。

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

本文的其余部分将展示如何定义表、实现查询并给出性能度量。使用空间索引是一个聪明的主意,它可以提高嵌套集模型的性能,而嵌套集模型对您来说可能是新的。

如果你也在考虑不使用MySQL的方法,那么你可能想看看 PostgreSQL 这是另一个免费的开源数据库。PostgreSQL支持以下形式的递归查询: recursive common table expressions 这使得查询继承数据比在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

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

举个例子:

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方面,我认为它不能得到任何更漂亮、更简单的东西;)

我不知道 存储过程 方式。但是,由于它涉及递归(在您的情况下),我不知道它在层次结构中的许多级别上是否会很快。I assume you can give it a try.

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

在处理分层数据集时,我发现最好考虑缓存。以这种方式处理这个问题的主要好处之一是不需要将数据库反规范化为可能难以改变的内容。

由于内存堆(memcache、redis等)的查找速度比简单的SQL快得多。 id -> data 解决方案,我将使用它们缓存每个节点的直接子节点的ID列表。通过这种方式,您可以通过递归算法获得良好的性能,从而为任何节点构建一个完整的列表。

若要添加/删除新节点,只需使其“直接父缓存”无效。 O(1) .

如果速度不够快,可以将另一层缓存添加到每个节点的所有子节点的列表中。为了使用适当可变的数据集,您应该记录每个节点的缓存性能(刷新/缓存命中率),并为何时存储缓存设置一个公差级别。这也可以存储在内存堆中,因为它是非重要数据。

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

WHERE id IN( id1, id2, .... )

I once had to store a complex hierarchical arbitrary-depth bill-of-material system in a SQL-like database manager that wasn't really up to the task, and it ended up forcing messy and tricky indicies, data definitions, queries, etc. After restarting from scratch, using the db manager to provide only an API for record reads and writes on simple indexed keys, and doing all of the actual input/manipulation/reporting in external code, the final result was quicker to implement, easier to understand, and simpler to maintain and enhance. The most complex query needed was essentially SELECT A FROM B.

因此,不要将逻辑和操作嵌入到MySQL的限制中,而是考虑使用代码来做您想要做的事情,并且仅依赖于最低级别的get/put。