如何有效地在数据库中保存树结构？

Question

我对 NoSQL 和关系数据库持开放态度。这个问题已经被问过几次了，但我的转折如下。

我希望能够快速找到并识别重复的子树。

例如，如果树是索引用户硬盘上的文件（和文件夹），我可能会这样：

    /   <-- root
  /      \
...        home
      /          \
   ugrad        course
    /          /    |    \
  ...        cs101 cs112 cs113

这可能适用于 User1

我希望能够在所有其他用户中找到 course > cs101、cs112、cs113 子树。

构建这个的有效方法是什么？

Answer 1

看起来这对 hash table 来说是个不错的工作。如果您认为需要，也应该可以在数据库中创建一个。要找到相似的子树，您只需检查与要比较的子树具有相同哈希值的桶，这应该会提高速度。

你的问题不清楚你是否也对目录结构中的（常规）files 相等感兴趣，或者只是目录 names 的子目录。您可以设计您的 哈希函数 来尊重或不尊重它们。文件系统属性也是如此，例如权限。如果相等包括权限，您可能不会在不同用户的主目录中找到相等的子树，因为通常用户目录中的文件属于该用户。

可能有更好的方法。