SQL中的分层标记

Question

我有一个PHP Web应用程序,它使用MySQL数据库进行对象标记,其中我使用了标记结构作为此SO问题的答案.

我想实现一个标记层次结构,其中每个标记都可以有一个唯一的父标记.然后搜索父标签T将匹配T的所有后代(即T,父母为T的标签(T的子女),T的孙子等).

最简单的方法是在标签表中添加一个ParentID字段,其中包含标签父标签的ID,如果标签没有父标签则添加一些幻数.然而,搜索后代然后需要重复完整搜索数据库以找到每个"代"中的标记,我想避免这些标记.

一个(可能)更快,但更少规范化的方法是使用一个包含每个标记的所有子项的表,甚至每个标记的所有后代.然而,这会冒数据库中数据不一致的风险(例如,标签是多个父项的子项).

是否有一种很好的方法可以使查询快速查找后代,同时尽可能保持数据的标准化？

Answer 1

我用两列实现了它.我在这里简化一下,因为我必须将标签名称保存在单独的字段/表中,因为我必须将其本地化为不同的语言:

• 标签
• 路径

例如,查看这些行:

tag            path
---            ----
database       database/
mysql          database/mysql/
mysql4         database/mysql/mysql4/
mysql4-1       database/mysql/mysql4-1/
oracle         database/oracle/
sqlserver      database/sqlserver/
sqlserver2005  database/sqlserver/sqlserver2005/
sqlserver2005  database/sqlserver/sqlserver2008/

等等

使用like路径字段上的运算符,您可以轻松获得所有需要的标记行:

SELECT * FROM tags WHERE path LIKE 'database/%'

有一些实现细节,比如当您在层次结构中移动节点时,您还必须更改所有子节点等,但这并不难.

还要确保路径的长度足够长 - 在我的情况下,我没有使用路径的标记名称,而是使用另一个字段来确保我没有太长的路径.

Answer 2

Ali 的答案有一个链接到Joe Celko 的 Trees and Hierarchies in SQL for Smarties，这证实了我的怀疑 - 没有一个简单的数据库结构可以提供世界上最好的。最适合我的目的似乎是本书中详细介绍的“频繁插入树”，它类似于阿里链接的“嵌套集模型”，但具有非连续索引。这允许 O(1) 插入（非结构化BASIC 行编号），并在需要时偶尔进行索引重组。