How to find the absolute path of a node (file or directory) in this file system model

This was actually a question asked to me during a recent interview and I was clean bowled.

The question was to design a database to represent a file system where -

• there is a root directory and many files/directories are present inside it.
• there can be any number of directories/files inside a directory.

Requirements

• find all the files present in the same directory of a given a file.
• given a file/directory, find its path from the root.

Condition - There has to be one database table for the model. Not mandatory, but good to have as the Interview question had this condition.

I did not know that making a tree and numbering it as shown in the following diagram makes it so much more optimized -

The useful property of the above tree structure is that -

• Considering any two subtrees, e.g. Subtree A (dir2 and its children) and Subtree B (dir3 and its children), the numbers of all the nodes in Subtree A will be lesser than the Next_Subtree_First_Node, which is dir3 in this case.

Then if we store the info in a database structure like this -

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

________________________________________________________________________

NOTE - The above structure is what I remember during the discussion. This may not be the best structure to solve the problem. Please let me know if some change is needed.

The first query will be like this -

Find all files in the same directory

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

My Questions

• The above query开发者_JAVA技巧 will return all the required files, but how do I know the Next_Subtree_First_Node and Previous_Subtree_Last_Node beforehand.

E.g. for file4,

Next_Subtree_First_Node = 7 and Previous_Subtree_Last_Node = 4.

• I am not sure what should be the logic of the absolute path finding query. Please give some ideas.

E.g. given file7, the result should be -

Parent Directory / dir3 / dir4 / file7.

---

If the filesystem has one name per file (as in Windows; so no hard links, as in Unix) then you can store the containing directory with each file and trace the path back to the root in a bottom-up fashion.

In database terms, you'd have a one-to-many relation between directories and the files they contain and iteratively SELECT the parent until you're at the root.

---

I think you need to create tables where.

1: root_table: Where there is childes (include: directories, and files).

2: childe_table: Now here you specify each with type of each and Id of root.

3: directory_table: where directory name and parent id.

4: file_table: Where file name, parent directory id.

So then you create the relation...

And for query you will need join so to find all childes and absolute path.