database-design - 如何在此文件系统模型中找到节点(文件或目录)的绝对路径

Question

这实际上是在最近的一次采访中问我的一个问题，我很清楚。

问题是设计一个数据库来表示文件系统，其中 -

• 有一个根目录，里面有很多文件/目录。
• 目录中可以有任意数量的目录/文件。

要求

• 找到给定文件的同一目录中存在的所有文件。
• 给定一个文件/目录，从根目录找到它的路径。

条件 - 模型必须有一个数据库表。不是强制性的，但很好，因为面试问题有这个条件。

我不知道制作一棵树并如下图所示对其进行编号会使它更加优化 -

上述树结构的有用属性是 -

• 考虑任意两个子树，例如子树A(dir2及其子树)和子树B(dir3及其子树)，子树A中所有节点的个数都会小于Next_Subtree_First_Node，在本例中为dir3。

然后如果我们将信息存储在这样的数据库结构中 -

_______________________________________________________________________
Sequence_Number    Name                 type   
-----------------------------------------------------------------------
0                  Parent Directory     Dir  
1                  dir1                 Dir  
2                  file1                File  
3                  file2                File  
4                  file3                File  
5                  dir2                 Dir  
...

________________________________________________________________________

注意 - 以上结构是我在讨论中记得的。这可能不是解决问题的最佳结构。如果需要更改，请告诉我。

第一个查询将是这样的 -

查找同一目录下的所有文件

Select Name From File_System 
  where Sequence_Number Between Next_Subtree_First_Node 
    and Previous_Subtree_Last_Node 
    and type = "File";

我的问题

• 上面的查询将返回所有需要的文件，但我如何事先知道 Next_Subtree_First_Node 和 Previous_Subtree_Last_Node。

例如对于文件 4，

Next_Subtree_First_Node = 7 和 Previous_Subtree_Last_Node = 4.

• 我不确定绝对路径查找查询的逻辑应该是什么。请给出一些想法。

例如给定 file7，结果应该是 -

父目录/dir3/dir4/file7.

Answer 1

如果文件系统的每个文件都有一个名称(如在 Windows 中；因此没有硬链接(hard link)，如在 Unix 中)，那么您可以将包含的目录与每个文件一起存储，并以自下而上的方式将路径追溯到根目录。

在数据库术语中，您将在目录和它们包含的文件之间建立一对多关系，并迭代地SELECT 父级，直到您位于根目录。