我有一个PHP Web应用程序,该应用程序使用MySQL数据库进行对象标记,在该应用程序中,我使用了可接受的标记结构作为此SO问题的答案。
我想实现一个标签层次结构,其中每个标签可以有一个唯一的父标签。然后,搜索父标签T将匹配T的所有后代(即T,其父母是T的标签(T的孩子),T的孙子等)。
最简单的方法似乎是在标签表中添加一个ParentID字段,其中包含标签的父标签的ID,如果标签没有父标签,则包含一些魔术数字。但是,要搜索后代,则需要重复完整搜索数据库以在每个“世代”中找到标签,我想避免这种情况。
一种(大概)更快但标准化程度较低的方法是使表包含每个标签的所有子代,甚至每个标签的所有后代。但是,这冒着数据库中数据不一致的风险(例如,标签是多个父级的子级)。
有什么好方法可以使查询快速找到后代,同时又要保持数据尽可能的规范化?
Ali的答案有一个链接,其中链接到Joe Celko的《用于Smarties的SQL中的树和层次结构》,这证实了我的怀疑- 没有一个简单的数据库结构可以提供世界上最好的。对我而言,最好的方法似乎是本书中详述的“频繁插入树”,它类似于Ali链接的“嵌套集模型”,但具有非连续索引。这允许O(1)的插入( 一拉 非结构化BASIC行号),偶尔索引重组作为并在需要时。